Untitled
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...