Giả sử có một căn phòng ban đầu bật n đèn và trên tường có 4 nút. Sau khi thực hiện chính xác m thao tác chưa biết đối với các nút, chúng ta cần trả về có bao nhiêu loại trạng thái khác nhau của n đèn. Vậy coi n đèn được đánh dấu là số [1, 2, 3 ..., n], chức năng của 4 nút này như sau -
- Lật tất cả các đèn.
- Đèn lật có số chẵn.
- Đèn lật có số lẻ.
- Đèn lật có số (3k + 1), k =0, 1, 2, ...
Bây giờ nếu n =3 và m =1, thì sẽ có 4 hoạt động, đó là, [tắt, bật, tắt], [bật, tắt, bật], [tắt, tắt, tắt], [tắt, bật, bật ]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- nếu n là 0 hoặc m là 0, thì trả về 1
- nếu n là 1, thì trả về 2
- nếu n là 2 thì trả về 3, khi m là 1, ngược lại trả về 4
- nếu m là 1, thì trả về 4
- nếu m là 2 thì trả về 7, ngược lại thì trả về 8.
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int flipLights(int n, int m) {
if (m == 0 || n == 0) return 1;
if (n == 1) return 2;
if (n == 2) return m == 1? 3:4;
if (m == 1) return 4;
return m == 2? 7:8;
}
};
main(){
Solution ob;
cout << (ob.flipLights(3, 1));
} Đầu vào
3 1
Đầu ra
4