Untitled

 avatar
unknown
plain_text
2 years ago
1.8 kB
3
Indexable
Turn off the lights
Cho N chiếc bóng đèn ( 10 ≤ N ≤ 100) và K chiếc công tắc (3 ≤ K ≤ 10). 
Mỗi chiếc khóa được nối với các bóng đèn theo quy luật như sau: 
-	Khóa 1 nối với các đèn: 1, 3, 5, 7, 9,…
-	Khóa 2 nối với các đèn: 2, 5, 8, 11, 14,…
-	Khóa 3 nối với các đèn: 3, 7, 11, 15, 19,…
Hãy xác định số bóng đèn tối đa được tắt sau tối đa 3 lần bật/tắt các công tắc. 


Input
Input sẽ chứa một hoặc nhiều test cases 
Dòng đầu là số lượng test case T (T ≤ 50)
Dòng đầu tiên của mỗi test cases là kích thước hình vuông N (5 ≤ N ≤ 9)
N dòng tiếp theo lần lượt là giá trị trong các ô nhỏ của hình vuông lớn. 
 
Output
Với mỗi test case, in ra tổng số lớn nhất thu được 

Sample
Input
2
5
1 0 3 5 6
4 5 3 7 9
7 2 2 6 7
3 4 7 8 8
9 5 1 6 3
6
3 4 5 6 8 6
3 5 6 7 7 8
3 3 3 3 3 5
1 2 5 6 4 2
3 3 5 5 5 7
8 5 3 6 9 9

Output
#1 35000
#2 72000


Code:

#include<iostream>
using namespace std;
int SoBong, SoKhoa;
int den[105];
int ans; 
int dem(){
	int cnt =0;
	for(int i = 1; i <= SoBong; i++){
		if(den[i] == 0) cnt ++;
	}
	return cnt;
}
void dao(int k){
	for(int i = k; i <= SoBong; i +=k+1){
		den[i] = 1 - den[i];
	}
}

void backtrack(int i){
	int cnt = dem();
	if(ans < cnt ) ans = cnt;
	if( i == 4 ) return;
	for(int k = 1; k <= SoKhoa; k++){
		dao(k);
		backtrack(i+1);
		dao(k);
	}
}


int main(){
	//freopen("text.txt", "r", stdin);
	int test;
	cin >> test;
	for(int tc = 1; tc <= test; tc++){
		cin >> SoBong >> SoKhoa;
		for(int i = 1; i <= SoBong; i++){
			cin >> den[i];
		}
		ans = 0;
		backtrack(1);
		cout << "#" << tc << " " << ans << endl;
	 }
	 return 0;
}
Editor is loading...