Bóng đèn
Đề bài
Mô tả
Rạp chiếu phim mới nhất của Hollywood, Atheneum of Culture and Movies, có một bảng hiệu khổng lồ điều khiển bằng máy tính, gồm hàng nghìn bóng đèn. Mỗi hàng bóng đèn được điều khiển bởi một bộ công tắc do một chương trình máy tính điều khiển điện tử. Không may, người thợ điện đã lắp nhầm loại công tắc, trong khi tối nay là đêm khai trương của ACM. Bạn phải viết chương trình để các công tắc hoạt động đúng.
Một hàng của bảng hiệu gồm bóng đèn được điều khiển bởi công tắc. Bóng đèn và công tắc được đánh số từ đến , từ trái sang phải. Mỗi bóng đèn ở một trong hai trạng thái BẬT hoặc TẮT. Mỗi bộ dữ liệu cho trạng thái ban đầu và trạng thái mong muốn cuối cùng của một hàng bóng đèn.
Theo thiết kế ban đầu, mỗi công tắc điều khiển một bóng đèn. Tuy nhiên do lỗi của người thợ điện, mỗi công tắc lại điều khiển hai hoặc ba bóng đèn liên tiếp, như hình dưới. Công tắc trái nhất () đảo trạng thái của hai bóng trái nhất ( và ); công tắc phải nhất () đảo trạng thái của hai bóng phải nhất ( và ). Mỗi công tắc còn lại () đảo trạng thái của ba bóng có chỉ số , và . (Trường hợp đặc biệt chỉ có một bóng đèn và một công tắc thì công tắc đó chỉ đảo trạng thái của bóng đèn đó.) Chẳng hạn, nếu bóng đang BẬT và bóng đang TẮT thì gạt công tắc sẽ làm bóng TẮT và bóng BẬT. Chi phí nhỏ nhất để chuyển một hàng bóng đèn từ trạng thái ban đầu sang trạng thái cuối là số công tắc ít nhất cần gạt để đạt được sự thay đổi đó.
dot
digraph {
rankdir=TB;
node [shape=circle];
s1 [label="CT 1"]; s2 [label="CT 2"]; s3 [label="CT 3"]; s4 [label="CT n-1"]; s5 [label="CT n"];
b1 [label="Đèn 1", shape=box]; b2 [label="Đèn 2", shape=box]; b3 [label="Đèn 3", shape=box];
b4 [label="Đèn n-1", shape=box]; b5 [label="Đèn n", shape=box];
s1 -> b1; s1 -> b2;
s2 -> b1; s2 -> b2; s2 -> b3;
s3 -> b2; s3 -> b3; s3 -> dots1;
dots1 [label="...", shape=plaintext];
s4 -> dots2; s4 -> b4; s4 -> b5;
dots2 [label="...", shape=plaintext];
s5 -> b4; s5 -> b5;
{ rank=same; s1; s2; s3; s4; s5; }
{ rank=same; b1; b2; b3; dots1; dots2; b4; b5; }
}
Có thể biểu diễn trạng thái của một hàng bóng đèn dưới dạng nhị phân, trong đó nghĩa là bóng TẮT và nghĩa là bóng BẬT. Chẳng hạn, biểu diễn một hàng năm bóng đèn, trong đó bóng thứ hai và thứ ba BẬT. Có thể chuyển trạng thái này thành bằng cách gạt các công tắc , và , nhưng sẽ ít tốn kém hơn nếu chỉ gạt công tắc .
Hãy viết chương trình xác định các công tắc cần gạt để chuyển một hàng bóng đèn từ trạng thái ban đầu sang trạng thái mong muốn với chi phí nhỏ nhất. Một số cặp trạng thái ban đầu và trạng thái cuối có thể không thực hiện được. Để biểu diễn gọn, các trạng thái bóng đèn được cho bằng số nguyên thập phân thay vì nhị phân. Như vậy và được biểu diễn bởi các số và .
Dữ liệu vào
Dữ liệu gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu gồm một dòng chứa hai số nguyên thập phân không âm, trong đó ít nhất một số dương và mỗi số có không quá chữ số. Số thứ nhất biểu diễn trạng thái ban đầu của hàng bóng đèn, số thứ hai biểu diễn trạng thái cuối. Biểu diễn nhị phân của các số này là trạng thái ban đầu và trạng thái cuối của các bóng đèn, trong đó nghĩa là BẬT và nghĩa là TẮT.
Để tránh vấn đề với các chữ số ở đầu, giả sử bóng đèn thứ nhất BẬT ở trạng thái ban đầu hoặc ở trạng thái cuối (hoặc cả hai). Nói cách khác, là độ dài biểu diễn nhị phân của số lớn hơn trong hai số, và bóng ứng với bit cao nhất. Các dòng không có dấu cách thừa ở đầu hay cuối, hai số không có chữ số ở đầu và được phân cách bởi đúng một dấu cách.
Sau bộ dữ liệu cuối cùng là một dòng chứa hai số .
Dữ liệu ra
Với mỗi bộ dữ liệu, in một dòng gồm số thứ tự của bộ dữ liệu và một số nguyên thập phân biểu diễn một tập công tắc có chi phí nhỏ nhất cần gạt để chuyển hàng bóng đèn từ trạng thái ban đầu sang trạng thái cuối. Trong biểu diễn nhị phân của số này, bit phải nhất (bit thấp nhất) ứng với công tắc thứ ; bit nghĩa là công tắc được gạt, bit nghĩa là không gạt. Nếu không có cách nào, in impossible. Nếu có nhiều tập công tắc có chi phí nhỏ nhất, in tập có giá trị thập phân nhỏ nhất.
In một dòng trống giữa hai bộ dữ liệu liên tiếp. In theo đúng định dạng ở ví dụ: Case Number, số thứ tự (bắt đầu từ ), dấu hai chấm, một dấu cách rồi đến đáp án.
Ràng buộc
- Mỗi số có không quá chữ số, hai số của một bộ dữ liệu không đồng thời bằng .
- Mỗi file có không quá bộ dữ liệu.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 12 16 1 1 3 0 30 5 7038312 7427958190 4253404109 657546225 0 0 |
Case Number 1: 8 Case Number 2: 0 Case Number 3: 1 Case Number 4: 10 Case Number 5: 2805591535 Case Number 6: impossible |
Bộ 1: (), chỉ gạt công tắc , đáp án . Bộ 2: hai trạng thái giống nhau, không gạt công tắc nào. Bộ 3: , gạt công tắc hoặc công tắc đều được (giá trị hoặc ), chọn giá trị nhỏ hơn là . Bộ 4: (), gạt công tắc và (giá trị ) hoặc và (giá trị ), chọn . |
| 1 0 2 1 0 7 27 0 0 0 |
Case Number 1: 1 Case Number 2: 1 Case Number 3: 2 Case Number 4: 10 |
Ví dụ tự thêm. Bộ 1: , công tắc duy nhất chỉ đảo bóng . Bộ 2: , hai công tắc đều đảo cả hai bóng, chọn công tắc . Bộ 3: (bóng BẬT ở trạng thái cuối nên ), gạt công tắc . Bộ 4: , gạt (giá trị ) hoặc (giá trị ), cùng chi phí , chọn . |
https://oj.chuyentin.pro/problem/icpcwf03_b
Bình luận