시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 72 | 18 | 18 | 27.273% |
신탁이란 신이 자신의 의지를 순례자에게 전달하려는 것이고, 그렇기에 신탁을 이해하는 것은 순례자들의 기본 소양이다.
신탁을 이루는 문자는 1
에서 88888888
사이에 있는 88888888
가지 정수다. 즉, 123
도 하나의 문자가 되고, 88888888
도 하나의 문자가 된다. 하나의 문자는 하나의 뜻을 가지고 있다.
신탁은 홀수개 문자의 나열이다. 신탁을 해석하는 방법은 신탁에 변환을 거듭해서 단 하나의 문자만 남기는 것이고, 남겨진 문자가 신탁의 뜻이 된다. 신탁을 변환하는 순서에 따라 마지막에 남는 문자의 종류가 달라질 수 있기 때문에, 신탁은 여러 뜻을 가질 수 있다.
신탁을 변환하는 법은 다음과 같다.
예를 들어, [3,3,1,1,2,1,1]
이라는 신탁이 있다고 하자. 이 신탁을 읽는 예를 들어 보면,
[3,3,1,1,2,1,1]
$\rightarrow$ [1]
[3,3,1,1,2,1,1]
$\rightarrow$ [3,3,1]
$\rightarrow$ [3]
등이 방법이 있다. 그리고 놀랍게도 이 신탁을 2로 해석하는 방법은 존재하지 않는다. 그래서, [3,3,1,1,2,1,1]
라는 신탁은 1
또는 3
으로 해석될 수 있다. 주어진 신탁이 어떤 뜻으로 해석될 수 있는지 모두 구하여라.
첫 번째 줄에, 신탁의 개수를 나타내는 자연수 $T$가 주어진다.
그다음 줄부터 각 신탁마다 두 개의 줄이 입력으로 주어진다:
첫 번째 줄에, 신탁의 길이를 나타내는 자연수 $N$이 주어진다.
두 번째 줄에, 신탁의 구성을 나타내는 $N$ 개의 정수 $c_1, c_2, \cdots, c_N$ ($1\leq c_i \leq 88\ 888\ 888$)가 주어진다.
$T$ 개의 신탁 각각에 대해 두 개의 줄을 출력한다:
주어진 신탁이 $K$ 종류의 문자로 해석될 수 있다면, 첫 번째 줄에 $K$를 출력한다.
해석 결과로 가능한 서로 다른 $K$ 개의 문자를 정수의 오름차순으로 $C_1, C_2, \cdots, C_K$라고 할 때, 두 번째 줄에 $C_1, C_2, \cdots, C_K$를 공백으로 구분하여 출력한다.
1 7 3 3 1 1 2 1 1
2 1 3
2 7 1 2 4 5 3 6 7 11 8 1 6 2 1 5 100 5 4 7 3
4 2 4 5 6 3 3 4 5
1 1 88888888
1 88888888
Contest > BOJ User Contest > 전시관 > 제1 전시관 2번