Turn off the lights

 avatar
Ann
c_cpp
a year ago
1.7 kB
1
Indexable
Never
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



#include<iostream>
using namespace std;
int N,M;// N bong M khoa
int ans;
int A[102];
void Thaydoi(int vt){
	for(int i=0;vt+i*(vt+1)<=N;i++){
		A[vt+i*(vt+1)]=1-A[vt+i*(vt+1)];
	}
}
void backtrack(int vt,int solan){
	if(vt>M||solan==3){
		int res=0;
		for(int i=1;i<=N;i++){
			if(A[i]==0){res++;}
		}
		if(res>ans){
			ans=res;
		}return;
	}
	Thaydoi(vt);
	backtrack(vt+1,solan+1);
	Thaydoi(vt);
	backtrack(vt+1,solan);
}


int main(){
	int T;
	cin>>T;
	for(int tc=1;tc<=T;tc++){
		cin>>N>>M;
		for(int i=1;i<=N;i++){
			cin>>A[i];
		}
		ans=0;
		backtrack(1,0);
		cout<<"#"<<tc<<" "<<ans<<endl;
	}
	return 0;
}