Chuyển sang đỏ
Đề bài
Mô tả
Bố mẹ của Mei đã dành cả năm qua để sửa sang lại ngôi nhà, nhưng hệ thống đèn của nhà thì khá phức tạp! Mỗi phòng trong nhà có một bóng đèn LED, có thể đặt màu đỏ (R), xanh lá (G) hoặc xanh dương (B). Hình dưới là trạng thái ban đầu của các bóng đèn trong ví dụ thứ nhất (không vẽ nút bấm và dây nối):
array G B R B R R R G highlight green 1 8 highlight blue 2 4 highlight red 3 5 6 7
Khắp nhà có nhiều nút bấm, mỗi nút được nối với một hoặc nhiều bóng đèn. Khi bấm một nút, mọi bóng đèn đỏ nối với nút đó chuyển sang xanh lá, mọi bóng xanh lá nối với nút đó chuyển sang xanh dương, và mọi bóng xanh dương nối với nút đó chuyển sang đỏ. Mỗi nút có thể được bấm nhiều lần. Vì ngôi nhà được xây trước khi có kiểu đi dây chéo, mỗi bóng đèn được điều khiển bởi nhiều nhất hai nút.
Màu yêu thích của Mei là màu đỏ, nên cô muốn chuyển tất cả các bóng đèn sang màu đỏ. Bố mẹ cô sợ các nút bị mòn nên yêu cầu cô làm điều đó với tổng số lần bấm nút ít nhất.
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên và : số bóng đèn và số nút bấm.
- Dòng thứ hai là một xâu gồm ký tự, mỗi ký tự là
R,GhoặcB; ký tự thứ là màu ban đầu của bóng đèn thứ . - dòng tiếp theo mô tả các nút bấm. Mỗi dòng bắt đầu bằng số nguyên , số bóng đèn mà nút này điều khiển, tiếp theo là số nguyên phân biệt, chỉ số của các bóng đèn đó. Các bóng đèn được đánh số từ đến .
Dữ liệu ra
In ra số lần bấm nút ít nhất để Mei chuyển tất cả các bóng đèn sang màu đỏ. Nếu không thể chuyển tất cả các bóng đèn sang màu đỏ, in ra impossible.
Ràng buộc
- , .
- với mỗi nút.
- Mỗi bóng đèn xuất hiện nhiều nhất hai lần trong mô tả của tất cả các nút.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 6 GBRBRRRG 2 1 4 1 2 4 4 5 6 7 3 5 6 7 1 8 1 8 |
8 | Bấm nút 1 hai lần (đèn 1 thành đỏ, đèn 4 thành xanh lá), nút 2 một lần (đèn 2 thành đỏ), nút 3 hai lần (đèn 4 thành đỏ, đèn 5, 6, 7 thành xanh dương), nút 4 một lần (đèn 5, 6, 7 thành đỏ), và tổng cộng hai lần ở nút 5 và nút 6 cho đèn 8: . |
| 4 3 RGBR 2 1 2 2 2 3 2 3 4 |
impossible | Đèn 1 chỉ do nút 1 điều khiển và đã đỏ, nên số lần bấm nút 1 chia hết cho ; tương tự với nút 3 và đèn 4. Khi đó đèn 2 buộc nút 2 bấm lần (theo modulo ), nhưng đèn 3 lại buộc nút 2 bấm lần. |
| 4 4 GBRG 2 1 2 2 2 3 2 3 4 1 4 |
6 | Bấm các nút 1, 2, 3, 4 lần lượt lần. |
| 3 3 RGB 1 1 1 2 1 3 |
3 | Không bấm nút 1, bấm nút 2 hai lần và nút 3 một lần. |
Bình luận