Informatica Online Judge

  SNS의 친구들 [1096 / 0448]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 19   Total Tried : 31


The Champion of this Problem (C++) : ajou709 - ms / 737byte
My Best Submission (C++) : N/A

[USACO (Brian Dean, 2014)]

Background

경곽이의 $N$명의 친구들은 세계에서 가장 인기 있는 SNS인 Gsbook에 가입해서 활동하고 있다.

경곽이의 각 친구들이 만약 다른 친구와 관계를 맺었다면 이는 항상 서로 관계를 맺고 있다.

경곽이는 각 친구들이 $N$명 중 몇 명과 관계를 맺고 있는지 궁금하여 이를 조사한 리스트를 만들었다.

하지만 만들다가 실수를 하여 $N$명이 아니라 $N+1$명의 자료를 만들게 되었다. 즉, $N+1$개의 자료들 중 하나의 자료는 잘못된 것이다.

어떤 자료가 잘못된 것일까? 경곽이를 도와주는 프로그램을 작성하시오.

Input

첫 번째 줄에 경곽이의 친구의 수 N이 입력된다.

다음 줄 부터 $N+1$줄에 걸쳐서 각각의 친구의 수가 입력된다.

[입력값의 정의역]

$2 ≤ N ≤ 500$

Output

첫 번째 줄에 잘못됬을 가능성이 있는 자료의 수를 출력한다.

다음 줄 부터 잘못된 자료일 가능성이 있는 번호를 한 줄에 하나씩 출력한다.
(단, 처음 입력된 자료를 $1$번, 마지막에 입력된 자료를 $N+1$번으로 생각한다.)

IO Example

입력
4
1
2
2
1
3


출력
3
1
4
5


* 설명 : 만약 $4$명을 각각 $A$, $B$, $C$, $D$라 하고, 첫 번째 "$1$"이 잘못됬다면, 각 친구들은 $2$ $2$ $1$ $3$명의 친구를 가졌다는 의미이다.

$A$는 ($A$, $B$) ($A$, $D$) 즉, $B$, $D$와 친구를 맺었고,
$B$는 ($B$, $A$) ($B$, $D$)
$C$는 ($C$, $D$)
$D$는 ($D$, $A$) ($D$, $B$) ($D$, $C$)

즉 $2$, $2$, $1$, $3$이 가능하다. 따라서 맨 처음 "$1$"은 잘못작성된 자료일 가능성이 있다.
다음으로 네번 째 "$1$"도 삭제 가능하다.
마지막으로 "$3$"도 삭제가능하다. 이 때는 $1$, $2$, $2$, $1$이므로

$A$ : ($A$, $B$)
$B$ : ($B$, $A$) ($B$, $C$)
$C$ : ($C$, $B$) ($C$, $D$)
$D$ : ($D$, $C$)

로 친구를 맺을 수 있다. 하지만 "$2$"는 하나라도 제거하면 어떤 경우라도 관계를 만들 수 없으므로 잘못된 가능성이 있는 자료는 모두 $3$가지 이며 각 값은 $1$번째, $4$번째, $5$번째 자료가 된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]