참을 수 없는 머슥

시간 제한1초메모리 제한1024 MB

요약
N과 K가 주어질 때 합이 N인 음이 아닌 정수 (a1,a2,b1,b2)를 찾는다. 어떤 유효한 이진 문자열 A, B에서도 영의 개수를 같게 만드는 뒤집기 선택이 존재해야 하며, 사전순으로 최소인 답을 출력한다.
난이도

어려움10점 중 8점

유형
수학, 그리디, 완전 탐색, 조합론
정답자
아직 제출이 없습니다

문제

머슥은 문자열을 가지고 노는 것을 매우 좋아한다. 그는 먼저 네 개의 음이 아닌 정수 a_1,a_2,b_1,b_2a\_1,a\_2,b\_1,b\_2가 주어졌을 때, 다음 조건을 만족하는 이진 문자열 A,BA,B를 만든다.

  • AA의 길이는 a_1+a_2a\_1+a\_2이다. 단, AA는 빈 문자열일 수 없다.
  • BB의 길이는 b_1+b_2b\_1+b\_2이다. 단, BB는 빈 문자열일 수 없다.
  • AA와 BB를 이어 붙였을 때, 이어 붙인 문자열에서 0\tt{0}은 정확히 KK개 존재하여야 한다.

이후 머슥은 다음 두 가지 행동을 수행한다. 어떤 문자를 뒤집는다는 것은 해당 문자가 0\tt{0}인 경우 1\tt{1}로, 1\tt{1}인 경우 0\tt{0}으로 바꾸는 것을 의미한다.

  • 이진 문자열 AA에서 서로 다른 위치의 문자 a_2a\_2개를 선택하여 뒤집고, 나머지 a_1a\_1개의 문자는 그대로 둔다.
  • 이진 문자열 BB에서 서로 다른 위치의 문자 b_2b\_2개를 선택하여 뒤집고, 나머지 b_1b\_1개의 문자는 그대로 둔다.

하지만 머슥은 뒤집는 방법 중 다음 조건을 만족하지 않는 방법이 존재한다면 화를 낸다.

  • 문자열을 뒤집은 후 문자열 AA에 있는 0\tt{0}의 개수와 문자열 BB에 있는 0\tt{0}의 개수가 같아야 한다.

모그는 a_1+a_2+b_1+b_2=Na\_1+a\_2+b\_1+b\_2=N을 만족하는 네 개의 음이 아닌 정수를 머슥에게 줄 것이다. 다만 머슥이 화를 내면 달래기가 매우 번거롭기 때문에, 모그가 선택한 네 정수로 머슥이 어떤 문자열을 만들더라도 머슥이 화를 내지 않도록 해야 한다. 할 일이 많았던 모그를 대신해 a_1,a_2,b_1,b_2a\_1,a\_2,b\_1,b\_2를 찾아주자. 이 때 수열 (a_1,a_2,b_1,b_2)(a\_1,a\_2,b\_1,b\_2)는 사전순으로 최소여야 한다. 만약 가능한 답이 없다면 -1을 출력한다.

입력

첫째 줄에 정수 N,KN, K가 공백으로 구분되어 주어진다. (2≤N≤1018;0\<K\<N)(2\le N\le 10^{18}; 0\<K\<N)

출력

첫째 줄에 모그가 머슥에게 줄 네 개의 음이 아닌 정수 a_1,a_2,b_1,b_2a\_1, a\_2, b\_1, b\_2를 공백으로 구분하여 출력한다.

만약 가능한 답이 없다면 -1을 출력한다.

힌트

이진 문자열이란, 0\tt{0}과 1\tt{1}로만 이루어진 문자열을 말한다. 이진 문자열의 예시로는 "000\tt{000}", "01010\tt{01010}", "1010\tt{1010}", "11\tt{11}"등이 있다.

수열 (p_1,p_2,p_3,p_4)(p\_1, p\_2, p\_3, p\_4)이 수열 (q_1,q_2,q_3,q_4)(q\_1, q\_2, q\_3, q\_4)보다 사전 순으로 앞선다는 것은 p_1=q_1,p_2=q_2,⋯ ,p_i−1=q_i−1p\_1 = q\_1, p\_2 = q\_2, \cdots, p\_{i-1} = q\_{i-1}이고 p_i<q_ip\_i < q\_i인 정수 i(1≤i≤4)i (1\leq i\leq 4)가 존재하는 것이다.

예제1

  1. 예제 1

    입력
    2 1
    
    예상 출력
    0 1 1 0