Xây Dựng Lại Range

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie có một mảng nhưng không muốn tiết lộ trực tiếp. Thay vào đó, cô ấy cung cấp range (hiệu giữa giá trị lớn nhất và nhỏ nhất) của mọi mảng con liên tiếp. Cho các giá trị range này, hãy xây dựng lại một mảng thỏa mãn.

Dữ liệu vào

Dòng 1: số nguyên $N$ ( $1 \leq N \leq 300$ ).
$N$ dòng tiếp theo: dòng thứ $i$ chứa $N - i + 1$ số nguyên $r_{i, i}, r_{i, i + 1}, \dots, r_{i, N}$ là range của mảng con từ vị trí $i$ đến $j$ .

Dữ liệu ra

In ra $N$ số nguyên $b_{1}, b_{2}, \dots, b_{N}$ ( $- 10^{9} \leq b_{i} \leq 10^{9}$ ) sao cho với mọi $i \leq j$ , range của $b_{i}, \dots, b_{j}$ bằng $r_{i, j}$ .

Ràng buộc

$1 \leq N \leq 300$
Các giá trị trong mảng nằm trong $[- 10^{9}, 10^{9}]$
Luôn tồn tại lời giải

Ví dụ

Input	Output	Giải thích
3 0 2 2 0 1 0	-1 1 0	$r_{1, 1} = 0$ , $r_{1, 2} = ‖ - 1 - 1 ‖ = 2$ , $r_{1, 3} = 1 - (- 1) = 2$ , $r_{2, 2} = 0$ , $r_{2, 3} = ‖ 1 - 0 ‖ = 1$ , $r_{3, 3} = 0$ .
4 0 1 1 2 0 0 2 0 2 0	1 2 2 0	Mảng $[1, 2, 2, 0]$ thỏa mãn tất cả các ràng buộc range.

Bình luận

Không có bình luận tại thời điểm này.