시작값인 0 이상의 정수 \mathbf{S}와 목표값인 0 이상의 정수 \mathbf{E}가 주어진다. \mathbf{S}와 \mathbf{E}는 모두 이진수 표현(즉, 2진법 표기)으로 주어진다. 목표는 \mathbf{S}를 \mathbf{E}로 변환하는 것이다. 사용할 수 있는 연산은 다음 두 가지뿐이다:

현재 값을 2배로 만든다.
현재 값에 비트 단위 NOT(bitwise NOT)을 취한다. 현재 값의 이진수 표현은 불필요한 앞자리 0을 제거한 형태로 취하며, 연산 결과로 생긴 불필요한 앞자리 0도 모두 제거한다. (필요한 앞자리 0은 0의 표현에 있는 것 하나뿐이다.)

예를 들어 2배 연산을 하면 6은 12가 되고, 0은 0이 되며, 10은 20이 된다. NOT 연산을 하면 0은 1이 되고, 1은 0이 되며, 3 = 11_2는 0이 된다. 또한 14=1110_2는 1이 되고, 10=1010_2는 5=101_2가 되며, 5=101_2는 2=10_2가 된다. (X_2는 이진수 표현이 X인 정수를 뜻한다.)

두 연산은 원하는 만큼, 원하는 순서로 사용할 수 있다. 예를 들어 \mathbf{S} = 10001_2를 \mathbf{E} = 111_2로 바꾸려면, NOT 연산을 먼저 한 뒤 2배 연산을 두 번 하고 마지막으로 다시 NOT 연산을 하면 된다: 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.

변환을 완료하는 데 필요한 연산 횟수의 최솟값을 구하라. 만약 불가능하다면 불가능하다고 출력하라.

#10403 upload 1 done 1 how_to_reg 1

Double or NOTing timer 10s memory 1024MB

#10403

Double or NOTing 10s 1024MB