Pendelkeks

시간 제한3초메모리 제한1024 MB

요약

N개의 점프 길이를 순서를 바꿔가며 오른쪽부터 좌우 교대로 사용할 때 도달 가능한 모든 종료 칸을 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

Pendel-keksumängu mängitakse ruutude real, kus stardiruut on tähistatud arvuga $0$ , sellest paremal on ruudud $1, 2, 3, \ldots$ ja vasakul ruudud $-1, -2, -3, \ldots$ . Mängijale on ette antud hüpete arv $N$ ja hüpete pikkused $L\_1, L\_2, \ldots, L\_N$ . Mängija peab tegema esimese hüppe paremale ja edasi vaheldumisi vasakule ja paremale. Iga hüppe pikkuseks valib ta pikkuste loendi sellise liikme, mida ta pole veel kasutanud. Leida, millistel ruutudel võib $N$ -hüppeline seeria lõppeda.

입력

Esimesel real on hüpete arv $N$ ( $1 \le N \le 80$ ), teisel real tühikutega eraldatuna hüpete pikkused $L\_1, L\_2, \ldots, L\_N$ ( $0 \le L\_i \le 2\\,000$ , kus mõned väärtused võivad olla ka omavahel võrdsed).

출력

Ainsale reale kirjutada kasvavas järjekorras nende ruutude numbrid, millel võib hüpete seeria lõppeda.

예제1

예제 1
입력
```
4
1 2 3 4
```
예상 출력
```
-4 -2 0 2 4
```