시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 150 | 84 | 62 | 55.357% |
남극의 한 빙하 지대 어딘가에 펭귄 여러 마리가 살고 있다. 각 펭귄들은 바다에 떠 있는 여러 얼음 조각 위에 나뉘어 서 있다. 한 얼음 조각 위에 여러 마리의 펭귄이 있을 수도 있으며, 펭귄이 없는 빈 얼음 조각도 있을 수 있다.
펭귄은 사회성이 높은 동물이기 때문에 한 개의 얼음 위에 모두 모이고 싶다. 펭귄들은 얼음 조각들 중 하나를 도착지로 정해서 얼음과 얼음 사이를 점프해 오가며 도착지 위로 모두 모일 것이다. 단, 펭귄은 날 수 없기 때문에 많이 먼 얼음으로는 점프해서 가지 못한다.
게다가 지구 온난화 때문에 얼음 조각들이 녹고 있어서 몇몇 얼음 조각들은 펭귄이 밟았을 때 부서져 바다 아래로 가라앉아 버릴 수도 있다. 펭귄들은 얼음에 대해서는 아주 전문가이기 때문에 정확히 몇 번 밟아야 얼음이 가라앉는지 알 수 있다.
펭귄이 점프하여 다른 얼음으로 도약할 때 펭귄이 딛고 있던 얼음은 손상된다. 하지만 펭귄이 어떤 얼음으로 착지할 때 그 얼음은 손상되지 않는다.
펭귄들이 어떤 얼음 위로 모여야 다 모일 수 있을까?
얼음 조각 5개와 펭귄 세 마리가 있는 예제
첫 줄에 테스트 케이스의 수 T가 주어진다. ( T ≤ 100 )
각 테스트 케이스는 다음과 같이 구성되어 있다.
각 테스트 케이스마다 펭귄들이 모두 모일 수 있는 얼음 조각의 번호를 공백으로 구분하여 오름차순으로 출력한다.
얼음 조각의 번호는 0부터 시작하여 입력으로 주어진 순서대로이며, 만일 어떤 얼음으로도 펭귄들이 다 모일 수 없을 경우 -1을 출력한다.
2 5 3.5 1 1 1 1 2 3 0 1 3 5 1 1 5 1 1 1 5 4 0 1 3 1.1 -1 0 5 10 0 0 3 9 2 0 1 1
1 2 4 -1
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2007 B번