만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

역방향 메뚜기

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

요약
칸 수 n과 목표 경로 수 k가 주어질 때, 첫 칸에서 마지막 칸까지 정확히 k가지 경로가 나오도록 칸의 상태를 정합니다. 만들 수 없으면 Impossible을 출력합니다.
난이도

보통10점 중 5점

유형
동적 계획법, 그리디, 구현
정답자
아직 제출이 없습니다

문제

공원에 풀잎 nn개가 한 줄로 자라고 있다. 첫 번째 풀잎 위에 있는 메뚜기는 뛰어서 마지막 nn번 풀잎까지 가려고 한다. 메뚜기는 한 번에 앞쪽으로 한 칸 또는 두 칸 떨어진 풀잎으로만 뛸 수 있다. 일부 풀잎은 부러져 있어서 메뚜기가 그 위에 뛰어내릴 수 없다. 부러진 풀잎이 어디인지 알고 첫 번째와 마지막 풀잎은 부러지지 않았다고 가정하면, 메뚜기가 첫 번째 풀잎에서 마지막 풀잎까지 갈 수 있는 경로의 수를 구할 수 있다. 보바는 이 문제를 금방 풀고 이에 대한 역문제를 만들었다.

이번 문제에서는 그 역문제를 풀어야 한다. 즉, 메뚜기의 서로 다른 경로 수가 정확히 kk가 되도록 풀잎의 상태를 나타내는 설명을 찾아라.

입력

입력 파일에는 두 정수 nn과 kk가 주어진다 (2≤n≤10002 \le n \le 1000, 0≤k≤10180 \le k \le 10^{18}). nn은 풀잎의 개수이고, kk는 서로 다른 경로의 수이다.

출력

출력 파일의 한 줄에 공백으로 구분한 nn개의 수를 출력한다. 부러진 풀잎은 0, 온전한 풀잎은 1로 나타낸다. 첫 번째와 마지막 풀잎은 반드시 온전해야 한다. 답이 여러 개이면 그중 아무것이나 출력하면 된다.

답이 없으면 Impossible이라는 단어를 출력한다.

예제4

  1. 예제 1

    입력
    3 1
    
    예상 출력
    1 0 1
    
  2. 예제 2

    입력
    3 2
    
    예상 출력
    1 1 1
    
  3. 예제 3

    입력
    4 0
    
    예상 출력
    1 0 0 1
    
  4. 예제 4

    입력
    566 239
    
    예상 출력
    Impossible