시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 411 | 55 | 44 | 15.225% |
순례자는 영원히 끝나지 않을 것만 같은 순례를 계속하고 있다. 순례자는 위치한 성지에서 다른 성지로 이동하고, 성지에 도착할 때마다 신께 기도를 드린다.
지상에는 총 $N$ 개의 성지가 있어 $1$에서 $N$사이의 번호가 붙어있고, $i$번 성지에는 성직자가 $i$명 있다. 순례자는 적당한 순서를 정해서, 모든 성지를 정확히 한 번씩 방문해서 시작했던 성지로 돌아오는 순례 계획을 세우고 있다.
순례자가 $i$번 성지에서 $j$번 성지로 이동할 때, $i$번 성지에 있는 성직자와 $j$번 성지에 있는 성직자 총 $i+j$ 명이 순례자와 순례의 안녕을 기원하는 정신적인 의식을 거행한다. 순례자는 $N$번 이동하기 때문에 의식은 총 $N$번 열리는데, 각각의 의식에 몇 명이 모였는지에 따라 의식은 질서의 성질 혹은 혼돈의 성질을 갖게 된다.
성직자 $x$명의 정신을 일렬로 세우지 않고 직사각형 모양으로 배치 할 수 있다면, $x$를 질서의 수라고 한다. 즉, $x = pq$인 1보다 큰 자연수 $p$와 $q$가 존재하면 $x$를 질서의 수라고 한다. 그리고 질서의 수가 아닌 자연수들은 혼돈의 수이다. 질서의 수의 예로는 $420$, $123$ 등이 있고 혼돈의 수의 예로는 $2$, $3$, $7$, $1\ 000\ 000\ 007$ 등이 있다.
어떤 의식에 모인 사람의 수가 질서의 수가 되면, 그 의식은 질서의 의식이 된다. 그것이 아니라면 사람의 수가 혼돈의 수가 되기 때문에, 그 의식은 혼돈의 의식이 된다.
질서의 순례자는 순례하는 과정에서 질서의 의식이 최대한 많았으면 좋겠다고 생각하고, 혼돈의 순례자는 순례하는 과정에서 혼돈의 의식이 최대한 많았으면 좋겠다고 생각한다. 각 순례자를 위해서 어떤 순서로 성지를 순례해야 하는지 구하여라.
첫 번째 줄에, 문자열 $S$와 성지의 개수를 나타내는 자연수 $N$이 공백으로 구분되어 주어진다. $S$는 order
혹은 chaos
이다. $S$가 order
인 경우에는 질서의 순례자가 순례하고, chaos
인 경우에는 혼돈의 순례자가 순례한다는 것을 의미한다.
첫 번째 줄에, 순례자가 성지를 방문하는 순서를 의미하는 $N$ 개의 수를 공백으로 구분하여 출력하라. 가능한 방문 순서가 여럿 있을 경우 그중 아무거나 하나를 출력해도 좋다.
order
chaos
chaos 4
1 2 3 4
order 9
6 3 9 1 5 4 2 7 8