17395번 - 이진수 변환 스페셜 저지

당신에게 자연수 x₀와 N이 주어졌다. 지금부터 당신은 이 자연수 x₀를 N번의 '변환'을 통해 0으로 바꿀 것이다. 변환이란, 양의 정수를 이진법으로 표기하여, 1개 이상의 1을 0으로 바꾸는 작업이다. 예를 들어 9를 이진법으로 나타내면 1001₍₂₎인데, 9는 0(0000₍₂₎), 1(0001₍₂₎), 또는 8(1000₍₂₎)로 변환될 수 있다. 바뀐 자릿수는 밑줄로 표기되었다. 여러분의 목표는 x_i를 변환하여 x_i+1를 만드는 과정을 반복해, x_N을 0으로 만드는 것이다.

위 조건을 만족하는 수열 X = x₀, x₁, x₂, ..., x_N는 존재하지 않을 수도 있지만, 여러 개가 존재할 수도 있다. 만약 존재한다면, 각 수열별로 인접한 원소들의 차들의 집합 D(X) = {x₀-x₁, x₁-x₂, ..., x_N-1-x_N}를 정의하자. 이 집합의 원소들의 최대값과 최소값의 차이를 최소화하도록, 수열 X를 만들고자 한다. 즉, 가능한 모든 수열 X_i 중 (D(X_i)에 속한 원소의 최댓값 - D(X_i)에 속한 원소의 최솟값)이 최소가 되는 X_i를 찾고자 한다.

이상해보일 수 있는 문제지만, 당신은 대답해야 한다. 과연 1초안에 답할 수 있을까?

첫 번째 줄에 변환할 자연수와 변환 횟수를 의미하는 두 자연수 x₀과 N이 공백으로 구분되어 주어진다. (1 ≤ x₀ ≤ 10¹⁶, 1 ≤ N ≤ 50)

만약 조건을 만족하는 수열이 존재하지 않으면 첫 번째 줄에 -1을 출력한다.

조건을 만족하는 수열이 존재한다면, 수열의 원소를 의미하는 N개의 정수 x₁, x₂, ..., x_N을 공백으로 구분하여 출력한다.

조건을 만족하는 수열이 여러 개 존재한다면, 아무 것이나 출력해도 좋다.