역방향 메뚜기
시간 제한2초메모리 제한1024 MB
칸 수 n과 목표 경로 수 k가 주어질 때, 첫 칸에서 마지막 칸까지 정확히 k가지 경로가 나오도록 칸의 상태를 정합니다. 만들 수 없으면 Impossible을 출력합니다.
문제
공원에 풀잎 개가 한 줄로 자라고 있다. 첫 번째 풀잎 위에 있는 메뚜기는 뛰어서 마지막 번 풀잎까지 가려고 한다. 메뚜기는 한 번에 앞쪽으로 한 칸 또는 두 칸 떨어진 풀잎으로만 뛸 수 있다. 일부 풀잎은 부러져 있어서 메뚜기가 그 위에 뛰어내릴 수 없다. 부러진 풀잎이 어디인지 알고 첫 번째와 마지막 풀잎은 부러지지 않았다고 가정하면, 메뚜기가 첫 번째 풀잎에서 마지막 풀잎까지 갈 수 있는 경로의 수를 구할 수 있다. 보바는 이 문제를 금방 풀고 이에 대한 역문제를 만들었다.
이번 문제에서는 그 역문제를 풀어야 한다. 즉, 메뚜기의 서로 다른 경로 수가 정확히 가 되도록 풀잎의 상태를 나타내는 설명을 찾아라.
입력
입력 파일에는 두 정수 과 가 주어진다 (, ). 은 풀잎의 개수이고, 는 서로 다른 경로의 수이다.
출력
출력 파일의 한 줄에 공백으로 구분한 개의 수를 출력한다. 부러진 풀잎은 0, 온전한 풀잎은 1로 나타낸다. 첫 번째와 마지막 풀잎은 반드시 온전해야 한다. 답이 여러 개이면 그중 아무것이나 출력하면 된다.
답이 없으면 Impossible이라는 단어를 출력한다.