Điểm:
1000 (p)
Thời gian:
2.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bessie có một dãy \(a_1, a_2, \dots, a_N\), trong đó \(1 \le N \le 300\) và \(0 \le a_i \le 10^9\) với mọi \(i\). Cô nàng sẽ không nói thẳng cho bạn dãy \(a\) mà lại thích vòng vo Tam Quốc, chỉ nói cho bạn khoảng xác định của dãy. Nghĩa là, với mỗi cặp chỉ số \(i \le j\), Bessie sẽ nói cho bạn \(r_{i, j} = \max a[i \dots j] - \min a[i \dots j]\). Cho các giá trị của \(r\), hãy xây dựng lại một dãy mà có thể là dãy ban đầu của Bessie. Các giá trị trong dãy phải nằm trong đoạn \([-10^9, 10^9]\).
Input
- Dòng đầu tiên là số \(N\).
- \(N\) dòng tiếp theo, dòng thứ \(i\) là các số \(r_{i, i}, r_{i, i + 1}, \dots r_{i, n}\).
- Dữ liệu đảm bảo luôn có dãy \(a\) với các giá trị nằm trong đoạn \([0, 10^9]\) thoả mãn điều kiện của test.
Output
- In ra một dòng là \(N\) số nguyên \(b_1, b_2, \dots, b_N \in [-10^9, 10^9]\) thoả mãn \(r_{i, j} = \max a[i \dots j] - \min a[i \dots j] \forall i \le j\).
Scoring
- Subtask \(1\): \(r_{1, N} \le 1\).
- Subtask \(2\): \(r_{i, i + 1} = 1 \forall 1 \le i \le N\).
- Subtask \(3\): Không có ràng buộc thêm.
Test 1
Input
3
0 2 2
0 1
0
Output
1 3 2
Note
Ví dụ \(r_{1, 3} = \max a[1 \dots 3] - \min a[1 \dots 3] = 3 - 1 = 2\).
Test 2
Input
3
0 1 1
0 0
0
Output
0 1 1
Note
Test này thoả mãn ràng buộc của subtask \(1\).
Test 3
Input
4
0 1 2 2
0 1 1
0 1
0
Output
1 2 3 2
Note
Test này thoả mãn ràng buộc của subtask \(2\).
Test 4
Input
4
0 1 1 2
0 0 2
0 2
0
Output
1 2 2 0
Bình luận