만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

진자 쿠키

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

요약
주어진 N개의 점프 길이를 오른쪽과 왼쪽으로 번갈아 배정할 때, 도달할 수 있는 모든 칸의 번호를 구합니다.
난이도

보통10점 중 6점

유형
동적 계획법, 비트 연산
정답자
아직 제출이 없습니다

문제

진자 쿠키는 칸들이 일렬로 놓인 곳에서 하는 게임이다. 시작 칸은 00번이고, 그 오른쪽 칸은 1,2,3,…1, 2, 3, \ldots번, 왼쪽 칸은 −1,−2,−3,…-1, -2, -3, \ldots번이다. 점프 횟수 NN과 점프 길이 L1,L2,…,LNL_1, L_2, \ldots, L_N이 주어진다. 첫 번째 점프는 오른쪽으로 하고, 이후에는 왼쪽과 오른쪽을 번갈아 뛴다. 각 점프마다 길이 목록에서 아직 사용하지 않은 원소 하나를 고른다. NN번의 점프로 이루어진 시리즈가 끝날 수 있는 칸을 모두 구하라.

입력

첫 줄에 점프 횟수 NN (1≤N≤801 \le N \le 80)이 주어진다. 둘째 줄에는 공백으로 구분된 점프 길이 L1,L2,…,LNL_1, L_2, \ldots, L_N이 주어진다 (0≤Li≤2 0000 \le L_i \le 2\,000). 값 중에는 서로 같은 것이 있을 수 있다.

출력

시리즈가 끝날 수 있는 칸의 번호를 오름차순으로 한 줄에 출력한다.

예제1

  1. 예제 1

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