레이팅 미적용베시는 배열 \(a_1, \ldots, a_N\)을 가지고 있으며, \(1 \leq N \leq 300\)이고 모든 \(i\)에 대해 \(0 \leq a_i \leq 10^9\)이다. 베시는 \(a\) 자체는 알려 주지 않지만, \(a\)의 각 부분 배열의 범위(range)를 알려 준다. 즉, 각 인덱스 쌍 \(i \leq j\)에 대해 베시는 \(r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]\)를 알려 준다. 이 \(r\) 값들이 주어질 때, 베시의 원래 배열이 될 수 있었던 배열을 하나 구성하시오. 구성한 배열의 값들은 \([-10^9, 10^9]\) 범위에 있어야 한다.
출제: Danny Mittal
배점
- 테스트 5는 \(r_{1,N} \leq 1\)을 만족한다.
- 테스트 6-8은 모든 \(1 \leq i < N\)에 대해 \(r_{i,i+1} = 1\)을 만족한다.
- 테스트 9-14는 추가 제약이 없다.
출제: Danny Mittal
첫째 줄에 \(N\)이 주어진다.
이어서 \(N\)개의 줄이 주어진다. 이 중 \(i\)번째 줄에는 정수 \(r_{i, i}, r_{i, i + 1}, \ldots, r_{i, N}\)이 주어진다.
모든 \(i \leq j\)에 대해 \(r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]\)를 만족하는, 값이 \([0, 10^9]\) 범위인 어떤 배열 \(a\)가 존재함이 보장된다.
구성한 배열을 나타내는 \([-10^9, 10^9]\) 범위의 정수 \(b_1, b_2, \ldots, b_N\) \(N\)개를 한 줄에 출력한다. 이들은 모든 \(i \leq j\)에 대해 \(r_{i, j} = \max b[i\ldots j] - \min b[i\ldots j]\)를 만족해야 한다.
3
0 2 2
0 1
01 3 2For example, \(r_{1, 3} = \max a[1\ldots 3] - \min a[1\ldots 3] = 3 - 1 = 2\).
3
0 1 1
0 0
00 1 1This example satisfies the constraints for subtask 1.
4
0 1 2 2
0 1 1
0 1
01 2 3 2This example satisfies the constraints for subtask 2.
4
0 1 1 2
0 0 2
0 2
01 2 2 0riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > December > Silver