시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 8 | 6 | 6 | 100.000% |
You are given a starting non-negative integer $S$ and an ending non-negative integer $E$. Both $S$ and $E$ are given by their binary representation (that is, they are given written in base $2$). Your goal is to transform $S$ into $E$. The following two operations are available to you:
For example, by using the double operation, $6$ becomes $12$, $0$ becomes $0$, and $10$ becomes $20$. By using the NOT operation, $0$ becomes $1$, $1$ becomes $0$, $3=11_2$ becomes $0$, $14=1110_2$ becomes $1$, $10=1010_2$ becomes $5=101_2$, and $5=101_2$ becomes $2=10_2$. ($X_2$ means the integer whose binary representation is $X$).
You can use these operations as many times as you want in any order. For example, you can transform $S=10001_2$ to $E=111_2$ using the NOT operation first, then using the double operation twice, and then another NOT operation:
$$10001_2 \overset{\text{NOT}}{\Longrightarrow} 1110_2 \overset{\times 2}{\Longrightarrow} 11100_2 \overset{\times 2}{\Longrightarrow} 111000_2 \overset{\text{NOT}}{\Longrightarrow}111_2\text{.}$$
Determine the smallest number of operations needed to complete the transformation, or say it is impossible to do so.
The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each consists of a single line containing two strings $S$ and $E$, the binary representations of the starting and ending integers, respectively.
For each test case, output one line containing Case #x: y
, where $x$ is the test case number (starting from 1) and $y$ is IMPOSSIBLE
if there is no way to transform $S$ into $E$ using the two operations. Otherwise, $y$ is the smallest number of operations needed to transform $S$ into $E$.
0
or 1
.0
only if the length of $S$ is $1$.0
or 1
.0
only if the length of $E$ is $1$.6 10001 111 1011 111 1010 1011 0 1 0 101 1101011 1101011
Case #1: 4 Case #2: 3 Case #3: 2 Case #4: 1 Case #5: IMPOSSIBLE Case #6: 0
Sample Case #1 is the example shown in the main part of the statement.
These are possible optimal ways of solving Sample Cases #2, #3, and #4, respectively:
$$1011_2 \overset{\text{NOT}}{\Longrightarrow} 100_2 \overset{\times 2}{\Longrightarrow} 1000_2 \overset{\text{NOT}}{\Longrightarrow}111_2\text{,}$$
$$1010_2 \overset{\times 2}{\Longrightarrow} 10100_2 \overset{\text{NOT}}{\Longrightarrow} 1011_2\text{, and}$$
$$0_2 \overset{\text{NOT}}{\Longrightarrow} 1_2\text{.}$$
In Sample Case #5, it is not possible to get from $0_2$ to $101_2$ with any sequence of operations.
In Sample Case #6, we do not need to perform any operations because $S=E$.
Contest > Google > Code Jam > Google Code Jam 2021 > Round 1C C번