cho.sh

프랙타일 (Large)

복잡도 C인 K진 프랙털 작품에서 G 타일이 있는지 판별하는 타일 위치를 S개 이하로 골라 출력하거나 IMPOSSIBLE을 보고한다.

보통7수학조합론구현완전 탐색아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

아주 오래전 프랙탈 문명은 타일을 한 줄로 늘어놓은 예술 작품을 만들었다. 이들이 쓸 수 있는 타일은 금(G)과 납(L) 두 종류였다.

프랙탈 작품은 모두 두 매개변수로 정해진다. 하나는 타일 K개로 이루어진 원본 수열이고 다른 하나는 복잡도 C다. 원본 수열이 주어졌을 때 복잡도 1인 작품은 원본 수열 그 자체이고, 복잡도 X+1인 작품은 복잡도 X인 작품을 다음과 같이 바꾼 것이다.

  • 복잡도 X인 작품의 L 타일을 각각 원본 수열 하나로 바꾼다.
  • 복잡도 X인 작품의 G 타일을 각각 G 타일 K개로 바꾼다.

예를 들어 원본 수열이 LGL이면 복잡도 1부터 3까지의 작품은 다음과 같다.

  • C = 1: LGL (원본 수열 그대로)
  • C = 2: LGLGGGLGL
  • C = 3: LGLGGGLGLGGGGGGGGGLGLGGGLGL

당신은 방금 프랙탈 작품 하나를 발견했지만 타일이 너무 더러워서 어떤 재질인지 알아볼 수 없다. 당신은 이 지역의 프랙탈 문화에 정통한 고고학자라서 작품의 K와 C는 알지만 원본 수열은 모른다. 금이 있으면 신나는 일이니 작품에 G 타일이 적어도 하나 있는지 알고 싶다. 예산으로 대학원생 S명을 고용할 수 있고, 대학원생 한 명은 작품의 타일 KCK^C개 가운데 당신이 고른 타일 하나를 닦아서 그 타일이 G인지 L인지 확인한다.

원본 수열이 무엇이든 작품에 G 타일이 적어도 하나 있는지 확실히 알 수 있도록, 닦을 타일을 S개 이하로 고를 수 있을까? 고를 수 있다면 어떤 타일을 닦아야 할까? 가능한 선택이 여러 가지일 수 있으므로 출력 절에서 정한 한 가지 선택을 출력해야 한다.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 정수 K, C, S가 적힌 한 줄이다.

제한

  • 1≤T≤1001 \le T \le 100
  • 1≤K≤1001 \le K \le 100
  • 1≤C≤1001 \le C \le 100
  • KC≤1018K^C \le 10^{18}
  • 1≤S≤K1 \le S \le K

출력

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. 타일 위치는 가장 왼쪽 타일이 1, 가장 오른쪽 타일이 KCK^C가 되도록 번호를 붙인다.

S개 이하의 타일로 답을 알 수 있는 방법이 없으면 y는 IMPOSSIBLE이다. 그렇지 않으면 y는 아래에서 정의하는 위치 p1,p2,…,pmp_1, p_2, \ldots, p_m을 이 순서(오름차순)대로 공백 하나씩으로 구분한 목록이다.

m=⌈K/C⌉m = \lceil K / C \rceil이라 하자. 각 j=1,2,…,mj = 1, 2, \ldots, m에 대해 sj=min⁡((j−1)C+1, K−C+1)s_j = \min((j-1)C + 1,\ K - C + 1)로 두고, 각 t=1,2,…,Ct = 1, 2, \ldots, C에 대해 aj,t=max⁡(1, sj+t−1)a_{j,t} = \max(1,\ s_j + t - 1)로 둔다. jj번째 위치는

pj=1+∑t=1C(aj,t−1)⋅KC−tp_j = 1 + \sum_{t=1}^{C} (a_{j,t} - 1) \cdot K^{C-t}

이다.

pjp_j는 복잡도 1인 작품에서 aj,1a_{j,1}번째 타일을 고르고, 이후 복잡도마다 직전에 고른 타일이 바뀐 구간 안에서 aj,ta_{j,t}번째 타일을 골라 도달하는 타일이다. S개 이하의 타일로 답을 알 수 있는 방법이 있으면 p1,p2,…,pmp_1, p_2, \ldots, p_m도 그런 방법이다.

힌트

예제 1번 케이스에서 가능한 원본 수열은 GG, GL, LG, LL 네 가지이고, 각각 다음 작품을 만든다.

  • 원본 수열 GG: GGGGGGGG
  • 원본 수열 GL: GGGGGGGL
  • 원본 수열 LG: LGGGGGGG
  • 원본 수열 LL: LLLLLLLL

2번 타일만 보면 충분하다. 2번 타일이 G이면 작품에 G가 적어도 하나 있다는 것이 확실하다. (원본 수열이 GG, GL, LG 중 무엇인지는 모르지만 상관없다.) 2번 타일이 L이면 원본 수열은 LL일 수밖에 없으므로 작품에 G가 없다. 이 경우 m=1m = 1, s1=0s_1 = 0, (a1,1,a1,2,a1,3)=(1,1,2)(a_{1,1}, a_{1,2}, a_{1,3}) = (1, 1, 2)이고 p1=2p_1 = 2다.

1번 타일만 보는 것으로는 부족하다. 1번 타일이 L이면 원본 수열은 LG일 수도 LL일 수도 있다. LG라면 작품에 G가 있지만 LL이라면 하나도 없다.

예제 2번 케이스에서 작품은 타일 하나뿐이고 그 타일은 G 아니면 L이다. 그 타일을 보면 작품에 G가 있는지 바로 알 수 있다.

예제 3번 케이스에서 작품은 GG, GL, LG, LL 중 하나다. 타일은 하나만 볼 수 있는데 어느 타일도 혼자서는 답을 주지 못한다. 1번 타일이 L이면 작품은 LG일 수도 LL일 수도 있다. 2번 타일이 L이면 작품은 GL일 수도 LL일 수도 있다.

예제 4번 케이스는 3번 케이스와 같지만 타일을 하나 더 볼 수 있다. 이제 작품 전체를 보면 된다.

예제 5번 케이스에서 가능한 원본 수열은 여덟 가지이고, 각각 다음 작품을 만든다.

  • 원본 수열 GGG: GGGGGGGGG
  • 원본 수열 GGL: GGGGGGGGL
  • 원본 수열 GLG: GGGGLGGGG
  • 원본 수열 GLL: GGGGLLGLL
  • 원본 수열 LGG: LGGGGGGGG
  • 원본 수열 LGL: LGLGGGLGL
  • 원본 수열 LLG: LLGLLGGGG
  • 원본 수열 LLL: LLLLLLLLL

2번과 6번 타일을 보면 답을 알 수 있다. 둘 다 L이면 작품은 모두 L이고, 그렇지 않으면 G가 적어도 하나 있다. 1번과 2번 타일로는 안 된다. 둘 다 L이어도 원본 수열이 LLG일 가능성이 남기 때문이다.