Bản giao hưởng ấm nước
Đề bài
Mô tả
Henya là một thiên tài. Mọi người yêu quý Henya không chỉ vì cô có chỉ số IQ , mà còn vì cô có thể tạo ra âm thanh của những chiếc ấm đun nước đang sôi bằng giọng nói đáng yêu của mình, nghe rất dễ chịu.
Với trí thông minh của mình, Henya có nhiều ý tưởng kỳ quặc nhưng thú vị. Vào một ngày buồn chán, Henya lập ra một ban nhạc chỉ gồm các ấm nước! Henya có chiếc ấm, một số đang bật và một số đang tắt. Henya nói rằng khi tất cả các ấm đều được bật, chúng sẽ sôi cùng lúc và một bản giao hưởng hoàn hảo sẽ vang lên.
Là một người hâm mộ Henya, bạn rất muốn nghe bản giao hưởng này. Vì vậy, Henya thách bạn bật tất cả các ấm chỉ bằng thao tác sau (thực hiện không hoặc nhiều lần):
- Chọn ít nhất và nhiều nhất chiếc ấm liên tiếp và đổi trạng thái của chúng (đang bật thành tắt và ngược lại).
Hãy kiểm tra xem bạn có thể bật tất cả các ấm bằng thao tác Henya đề ra hay không.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên dương (): số bộ test. Mỗi bộ test gồm:
- Dòng thứ nhất chứa ba số nguyên dương (): số ấm của Henya, số ấm tối thiểu và tối đa được đổi trạng thái trong mỗi thao tác.
- Dòng thứ hai chứa xâu nhị phân độ dài : nghĩa là ấm thứ ban đầu đang tắt, nghĩa là ấm thứ ban đầu đang bật.
Dữ liệu ra
Với mỗi bộ test, in ra "YES" (không có dấu ngoặc kép) nếu bạn có thể bật tất cả các ấm. Ngược lại, in ra "NO".
Ràng buộc
- chỉ gồm các ký tự và
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 7 3 4 0000000 3 3 3 101 3 2 3 101 |
YES NO YES |
Bộ test thứ nhất: đổi trạng thái ấm đầu, rồi ấm cuối. Bộ test thứ hai: chỉ có thể chọn cả ấm; lần đầu được 010, lần thứ hai quay lại 101, nên không thể bật hết. Bộ test thứ ba: 101 → 011 (đổi ấm ) → 000 (đổi ấm ) → 111 (đổi cả ấm). |
| 3 1 1 1 0 4 2 2 0110 5 2 2 00100 |
YES YES YES |
Bộ test thứ hai: 0110 → 1010 → 1100 → 1111 (lần lượt đổi các cặp ấm ; ; ). Bộ test thứ ba: đổi ấm rồi ấm . |
Bình luận