거짓말
면접 대비시간 제한2초메모리 제한1024 MB
각 사람이 거짓말을 하는 사람 수의 하한 또는 상한을 말할 때, 모든 주장과 모순되지 않는 거짓말쟁이 수를 모두 구한다.
문제
당신 앞에는 명의 사람들이 있다. 각 사람은 자신을 포함하여 몇 명 이상이 거짓말을 하고 있다고 말하거나, 몇 명 이하의 사람이 거짓말을 하고 있다고 말한다.
예를 들어, 각 사람이 다음과 같이 주장한다고 하자.
- 첫 번째 사람이 이렇게 말한다: "1명 이상이 거짓말을 하고 있다!"
- 두 번째와 세 번째 사람이 이렇게 말한다: "1명 이하가 거짓말을 하고 있다!"
- 네 번째 사람이 이렇게 말한다: "2명 이상이 거짓말을 하고 있다!"
이 경우에 가능한 시나리오는 다음과 같다.
- 네 번째 사람만 거짓말을 하고 있다.
- 두 번째와 세 번째 사람이 거짓말을 하고 있다.
사람들의 주장이 주어질 때, 거짓말을 하는 사람의 수로 가능한 것을 모두 구해라.
입력
첫째 줄에 사람의 수 이 주어진다.
둘째 줄에 개의 정수 이 공백을 사이에 두고 주어진다.
- 가 양의 정수라면, 번째 사람이 "명 이상이 거짓말을 하고 있다"고 말했다는 뜻이다.
- 가 0이거나 음의 정수라면, 번째 사람이 "명 이하가 거짓말을 하고 있다"고 말했다는 뜻이다.
출력
첫째 줄에 거짓말을 하는 사람의 수로 가능한 수의 개수를 출력한다.
둘째 줄에 가능한 수들을 공백을 사이에 두고 오름차순으로 출력한다.
제한
- ()