trang chủ / đề bài / icpcwf03_b

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 n bóng đèn được điều khiển bởi n công tắc. Bóng đèn và công tắc được đánh số từ 1 đến 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 (i=1) đảo trạng thái của hai bóng trái nhất (1 và 2); công tắc phải nhất (i=n) đảo trạng thái của hai bóng phải nhất (n−1 và n). Mỗi công tắc còn lại (1<i<n) đảo trạng thái của ba bóng có chỉ số i−1, i và i+1. (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 1 đang BẬT và bóng 2 đang TẮT thì gạt công tắc 1 sẽ làm bóng 1 TẮT và bóng 2 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 đó 0 nghĩa là bóng TẮT và 1 nghĩa là bóng BẬT. Chẳng hạn, 01100 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 10000 bằng cách gạt các công tắc 1, 4 và 5, nhưng sẽ ít tốn kém hơn nếu chỉ gạt công tắc 2.

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 01100 và 10000 được biểu diễn bởi các số 12 và 16.

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á 100 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 đó 1 nghĩa là BẬT và 0 nghĩa là TẮT.

Để tránh vấn đề với các chữ số 0 ở đầ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, n là độ dài biểu diễn nhị phân của số lớn hơn trong hai số, và bóng 1 ứ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ố 0 ở đầ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ố 0.

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ứ n; bit 1 nghĩa là công tắc được gạt, bit 0 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ừ 1), 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á 100 chữ số, hai số của một bộ dữ liệu không đồng thời bằng 0.
  • Mỗi file có không quá 1000 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: 01100→10000 (n=5), chỉ gạt công tắc 2, đáp án 010002=8. Bộ 2: hai trạng thái giống nhau, không gạt công tắc nào. Bộ 3: 11→00, gạt công tắc 1 hoặc công tắc 2 đều được (giá trị 2 hoặc 1), chọn giá trị nhỏ hơn là 1. Bộ 4: 11110→00101 (n=5), gạt công tắc 2 và 4 (giá trị 010102=10) hoặc 1 và 5 (giá trị 17), chọn 10.
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: n=1, công tắc duy nhất chỉ đảo bóng 1. Bộ 2: 10→01, hai công tắc đều đảo cả hai bóng, chọn công tắc 2. Bộ 3: 000→111 (bóng 1 BẬT ở trạng thái cuối nên n=3), gạt công tắc 2. Bộ 4: 11011→00000, gạt {2,4} (giá trị 10) hoặc {1,5} (giá trị 17), cùng chi phí 2, chọn 10.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0