Problem B
Light Bulbs
---- The 2003 ACM Programming Contest World Finals ----

Hollywood’s newest theater, the Atheneum of Culture and Movies, has a huge computer-operated marquee composed of thousands of light bulbs. Each row of bulbs is operated by a set of switches that are electronically controlled by a computer program. Unfortunately, the electrician installed the wrong kind of switches, and tonight is the ACM's opening night. You must write a program to make the switches perform correctly.
 「ハリウッドの最新劇場 Atheneum of Culture and Movies の入り口に、コンピュータで制御可能な、何千本もの照明電球の入った看板がある。電球の照明はスイッチの操作によって行われるが、そのスイッチはコンピュータプログラムから電気的に制御される。不幸なことに、スイッチが間違って組み込まれてしまった。しかし、ACMオープンニング・ナイトが間もなく始まる。スイッチを正しく動かすプログラムを急いでつくれ。」

A row of the marquee contains n light bulbs controlled by n switches. Bulbs and switches are numbered from 1 to n, left to right. Each bulb can either be ON or OFF. Each input case will contain the initial state and the desired final state for a single row of bulbs.
 「1列に配置された n本の電球がn個のスイッチによって制御される。電球およびスイッチに、左から右まで、1からnの番号がついている。電球はON、OFFできる。入力データに、電球一列の初期状態と、必要とされる最終状態が書かれている。」

The original lighting plan was to have each switch control a single bulb. However the electrician's error caused each switch to control two or three consecutive bulbs, as shown in Figure 1. The leftmost switch (i = 1) toggles the states of the two leftmost bulbs (1 and 2); the rightmost switch (i = n) toggles the states of the two rightmost bulbs (n-1 and n). Each remaining switch (1 < i < n) toggles the states of the three bulbs with indices i-1, i, and i+1. (In the special case where there is a single bulb and a single switch, the switch simply toggles the state of that bulb.) Thus, if bulb 1 is ON and bulb 2 is OFF, flipping switch 1 will turn bulb 1 OFF and bulb 2 ON. The minimum cost of changing a row of bulbs from an initial configuration to a final configuration is the minimum number of switches that must be flipped to achieve the change.
 「スイッチ1つが電球1本を制御するように当初計画されていたが、間違えられて、図のように、スイッチ1つが電球2本または3本を同時に制御するようになってしまった。左端のスイッチ(i=1)は左端の電球2本(1と2)を、右端のスイッチ(i=n)は右端の電球2本(n-1とn)を、その間のスイッチ(1<i<n)が電球3本(i-1、i、i+1)を制御している。(極端なケースでは、スイッチ1つと電球1本だけの構成もありうる。その場合、1対1の操作と考えてよい。)電球1がON、電球2がOFFの状態であれば、フリップスイッチ1(<訳注>Flipイッチ。押すたびにオン⇔オフと切り替わるタイプのスイッチと考えてよい</訳注>)は電球1をOFF、電球2をONにする。初期状態から最終状態に変える最小コストとは、スイッチの押す回数を最小にすることだ。」

You can represent the state of a row of bulbs in binary, where 0 means the bulb is OFF and 1 means the bulb is ON. For instance, 01100 represents a row of five bulbs in which the second and third bulbs are both ON. You could transform this state into 10000 by flipping switches 1, 4, and 5, but it would be less costly to simply flip switch 2.
 「電球1列の状態を2進数で表現する。0を電球のOFF、1を電球のONを示す。例えば、01100は5本の電球に、2本目と3本目がONになっていることを表す。この状態から、スイッチ1、4、5を押すことで10000にすることができるが、もっとも簡単なのはスイッチ2を押すことだ。」

You must write a program that determines the switches that must be flipped to change a row of light bulbs from its initial state to its desired final state with minimal cost. Some combinations of initial and final states may not be feasible. For compactness of representation, decimal integers are used instead of binary for the bulb configurations. Thus, 01100 and 10000 are represented by the decimal integers 12 and 16.
 「初期状態から最終状態にするため、押さなきゃいけないスイッチの最小コストを決めるプログラムをつくってほしい。組合せによっては、最終状態は初期状態から実現できないかもしれない。短く表現したいので、2進数の代わりに10進数を使う。それで、01100と10000を10進数12と16で表現する。」

Input
The input file contains several test cases. Each test case consists of one line. The line contains two non-negative decimal integers, at least one of which is positive and each of which contains at most 100 digits. The first integer represents the initial state of the row of bulbs and the second integer represents the final state of the row. The binary equivalent of these integers represents the initial and final states of the bulbs, where 1 means ON and 0 means OFF.
 「入力にいくつかのテストケースが含まれる。各テストケースは1行に書かれる。その行に負でない10進整数が2つが入り、すくなくとも2つのうちの1つは正数。2つの整数は最大100桁。1つ目の整数は電球の初期状態、2つ目は電球の最終状態を表す。2つの整数に対応した2進表現では、1が電球のON、0が電球のOFFを示す。」

To avoid problems with leading zeros, assume that the first bulb in either the initial or the final configuration (or both) is ON. There are no leading or trailing blanks in the input lines, no leading zeros in the two decimal integers, and the initial and final states are separated by a single blank.
 「数字の先頭に0を無くすために、最初の電球が初期状態においても、終了状態においてもONと考えてよい。入力行の先頭と末尾に空白文字は入らないし、2つの10進整数の先頭に0は入らない。初期状態と終了状態との間に空白文字が1つ入る。」

The last test case is followed by a line containing two zeros.
 「入力の最後に0が二つ入る。

Output
For each test case, print a line containing the case number and a decimal integer representing a minimum-cost set of switches that need to be flipped to convert the row of bulbs from initial state to final state. In the binary equivalent of this integer, the rightmost (least significant) bit represents the nth switch, 1 indicates that a switch has been flipped, and 0 indicates that the switch has not been flipped. If there is no solution, print “impossible”. If there is more than one solution, print the one with the smallest decimal equivalent.
 「各テストケースに対して、ケース番号(case number)と、初期状態から最終状態にするための押すスイッチの組合せの最小コストを10進整数で1行に書くこと。整数の2進表現では、右端ビット(最下位)はn番目のスイッチを表し、1は押すべくスイッチ、0はそのまま押さないスイッチを表すこと。解答がなければ、"impossible"と表示すること。解答が複数ある場合、最小の10進表現にすること。」

Print a blank line between cases. Use the output format shown in the example.
 「各ケースの間に空白行を入れること。出力フォーマット例を参照せよ。」

Sample Input
12 16
1 1
3 0
30 5
7038312 7427958190
4253404109 657546225
0 0

Output for the Sample Input
Case Number 1: 8

Case Number 2: 0

Case Number 3: 1

Case Number 4: 10

Case Number 5: 2805591535

Case Number 6: impossible

Comments are closed.

Post Navigation