레이팅 미적용*참고: 이 문제의 시간 제한은 기본의 1.5배인 3초이다.*
농부 존은 베시에게 길이 \(N\)의 배열 \(a\)를 주었다 (\(2\le N\le 500, -10^{15}\le a_i\le 10^{15}\)). 이 배열의 \(\frac{N(N+1)}{2}\)개의 연속 부분 배열의 합은 모두 서로 다르다. 각 인덱스 \(i\in [1,N]\)에 대해, \(a\)에 합이 같은 서로 다른 두 연속 부분 배열이 존재하도록 만들기 위해 \(a_i\)를 바꿔야 하는 최소량을 계산하도록 베시를 도와준다.
출제자: Benjamin Qi
배점
- 입력 3: \(N\le 40\)
- 입력 4: \(N \le 80\)
- 입력 5-7: \(N \le 200\)
- 입력 8-16: 추가 제약이 없다.
출제자: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
다음 줄에 \(a_1,\dots, a_N\)(\(a\)의 원소들이 순서대로)이 주어진다.
각 인덱스 \(i\in [1,N]\)에 대해 한 줄씩 출력한다.
2
2 -32
3Decreasing \(a_1\) by \(2\) would result in \(a_1+a_2=a_2\). Similarly, increasing
\(a_2\) by \(3\) would result in \(a_1+a_2=a_1\).
3
3 -10 41
6
1Increasing \(a_1\) or decreasing \(a_3\) by \(1\) would result in \(a_1=a_3\).
Increasing \(a_2\) by \(6\) would result in \(a_1=a_1+a_2+a_3\).
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Gold