Tổng Mảng Con Bằng Nhau

Điểm: 1,00 (OI)

Giới hạn thời gian: 3.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

Cho mảng $a$ gồm $N$ phần tử sao cho tất cả các tổng mảng con liên tiếp đều khác nhau. Với mỗi chỉ số $i$ , hãy tìm giá trị thay đổi tối thiểu (theo giá trị tuyệt đối) cần áp dụng cho $a_{i}$ để tạo ra hai mảng con liên tiếp khác nhau có cùng tổng.

Dữ liệu vào

Dòng 1: Số nguyên $N$ ( $2 \leq N \leq 500$ ).
Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ ( $- 10^{15} \leq a_{i} \leq 10^{15}$ ).

Tất cả $\frac{N (N + 1)}{2}$ tổng mảng con liên tiếp ban đầu đều khác nhau.

Dữ liệu ra

$N$ dòng, mỗi dòng chứa giá trị thay đổi tối thiểu cho chỉ số $i$ .

Ràng buộc

$2 \leq N \leq 500$
$- 10^{15} \leq a_{i} \leq 10^{15}$
Giới hạn thời gian: 3 giây

Ví dụ

Input	Output	Giải thích
2 2 -3	2 3	Giảm $a_{1}$ đi 2: mảng thành $[0, - 3]$ , khi đó $a_{1} + a_{2} = - 3 = a_{2}$ . Tăng $a_{2}$ thêm 3: mảng thành $[2, 0]$ , khi đó $a_{1} + a_{2} = 2 = a_{1}$ .
3 3 -10 4	1 6 1	Thay đổi $a_{1}$ thêm 1: $a_{1} = 4 = a_{3}$ . Thay đổi $a_{2}$ thêm 6: $a_{1} = a_{1} + a_{2} + a_{3}$ . Thay đổi $a_{3}$ thêm 1: $a_{3} = 3 = a_{1}$ .

Bình luận

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