cho.sh

미끄럼틀! (Small)

건물 수 B(최대 6)와 경로 수 M(최대 20)이 주어질 때, 1번에서 B번으로 가는 경로가 정확히 M개가 되도록 정해진 규칙에 따라 인접 행렬을 출력하거나 불가능을 판정한다.

보통5조합론동적 계획법구현아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

Gooli는 언덕 지대에 건물 B개를 가진 거대 기업이다. 건물에는 1부터 B까지 번호가 붙어 있다.

CEO는 1번 건물에 있는 사무실에서 B번 건물에 있는 단골 카페까지 이동할 수 있도록 건물 사이에 미끄럼틀을 설치하려고 한다. 미끄럼틀은 당연히 한 방향으로만 탈 수 있다. 하지만 건물이 높고 엘리베이터가 있으므로 미끄럼틀은 어느 건물에서든 출발해 다른 어느 건물에든 도착할 수 있고, 방향도 자유롭다. 정확히 말하면 서로 다른 두 건물 x, y에 대해 x에서 y로 가는 미끄럼틀을 0개 또는 1개 설치할 수 있고, y에서 x로 가는 미끄럼틀도 0개 또는 1개 설치할 수 있다. 단, B번 건물에서 출발하는 미끄럼틀은 설치할 수 없다. CEO가 B번 건물에 도착하면 더 미끄러질 필요가 없기 때문이다.

Gooli가 생긴 지 정확히 M밀리초가 된 것을 기념해서, 새 미끄럼틀로 1번 건물에서 B번 건물까지 가는 방법이 정확히 M가지가 되도록 설계해야 한다. 방법이란 1번 건물로 시작해 B번 건물로 끝나는 건물의 수열로, 수열에서 연속한 두 건물 x, y마다 x에서 y로 가는 미끄럼틀이 있어야 한다. CEO는 모든 건물 사이가 미끄럼틀로 이어져 있기를 요구하지는 않는다.

조건을 만족하는 미끄럼틀을 1개 이상 설치하는 방법을 찾거나, 불가능하다고 판정하라.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. 다음 T개의 줄에는 각각 위에서 설명한 두 정수 B와 M이 주어진다.

출력

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 CEO의 요구를 만족할 수 있으면 POSSIBLE, 없으면 IMPOSSIBLE이다.

가능한 경우에는 이어서 B개의 줄에 각각 문자 B개를 출력한다. 이 줄들은 미끄럼틀 설치 방법을 나타내는 행렬이다. i번째 줄의 j번째 문자는 i번 건물에서 j번 건물로 가는 미끄럼틀을 설치하면 1, 아니면 0이다(i와 j는 1부터 센다). i번째 줄의 i번째 문자는 항상 0이고, 마지막 줄의 문자는 모두 0이다.

답이 하나로 정해지도록 미끄럼틀은 다음 규칙대로 설치한다.

  • 2≤i<j≤B2 \le i < j \le B인 모든 건물 쌍 i, j에 대해 i번 건물에서 j번 건물로 가는 미끄럼틀을 설치한다.
  • M=2B−2M = 2^{B-2}이면 1번 건물에서 다른 모든 건물로 가는 미끄럼틀을 설치한다.
  • 그렇지 않으면 1번 건물에서 B번 건물로 가는 미끄럼틀은 설치하지 않는다. 2≤i≤B−12 \le i \le B-1인 각 i에 대해, M을 이진수로 나타냈을 때 값이 2B−1−i2^{B-1-i}인 비트가 1이면 1번 건물에서 i번 건물로 가는 미끄럼틀을 설치하고, 0이면 설치하지 않는다.
  • 그 밖의 미끄럼틀은 설치하지 않는다.

요구를 만족할 수 있는 경우에는 항상 이 규칙으로 정확히 M가지 방법이 만들어진다.

제한

  • 1≤T≤1001 \le T \le 100
  • 2≤B≤62 \le B \le 6
  • 1≤M≤201 \le M \le 20

힌트

1번 예제의 첫 번째 케이스(B = 5, M = 4)에서 규칙대로 설치하면 1번 건물에서 5번 건물까지 가는 방법은 다음 4가지다.

  • 1, 2, 5
  • 1, 2, 3, 5
  • 1, 2, 4, 5
  • 1, 2, 3, 4, 5

세 번째 케이스에서 1에서 2, 2에서 3, 3에서 1, 1에서 4로 가는 미끄럼틀을 설치하면 CEO가 4번 건물에 도착하는 방법은 무한히 많아진다. 4번 건물로 바로 갈 수도 있고, 고리를 한 바퀴 돈 뒤 4번 건물로 갈 수도 있고, 두 바퀴 돈 뒤 갈 수도 있다. 하지만 CEO가 요구한 방법의 수는 정확히 20가지다.