Giá trị của dãy số (bài 2 đề thi Tin học trẻ quốc gia năm 2022)

Xem dạng PDF

Gửi bài giải

Điểm: 3,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài

Cho dãy số nguyên A gồm N phần tử a1, A2, ..., AN. Giá trị của dãy số A được tính như sau:

Ví dụ dãy số A: 6, 2, 1,3. Ta có v (A) = |6 - 1| + |2 - 2| + |1 - 3| + |3 - 4| = 8.

Cho thao tác quay vòng mảng A được thực hiện như sau: chuyển số ở vị trí cuối cùng lên vị trí đầu tiên: a1, a2,., aN-1, aN → aN, a1, a2, .., aN-1

Ví dụ dãy số A: 6, 2, 1, 3, sau một thao tác quay vòng thì dãy số sẽ như sau: 3, 6, 2, 1.

Yêu cầu: cho dãy số A, hãy sử dụng thao tác quay vòng một số lần để giá trị của dãy số lớn nhất.


Dữ liệu: Vào từ thiết bị vào chuẩn có khuôn dạng:

Dòng đầu tiên gồm một số nguyên dương N (N ≤ 10^5);

Dòng thứ hai gồm N số nguyên a1, a2, ..., aN-1, aN (|ai| ≤ 10^9;1 ≤ i ≤ N).

Kết quả: Ghi ra thiết bị ra chuẩn gồm một số nguyên là giá trị của dãy số lớn nhất tìm được.


Ràng buộc:

Có 40% số test ứng với 40% số điểm của bài có N ≤ 10^3;

30% số test khác ứng với 30% số điểm của bài có N ≤ 10^5; ai ≤ ai+1 Với 1 ≤ i < N;

30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì thêm.


Input:
4
6 2 1 3
Output:
10

Giải thích:

Ban đầu dãy số 6,2,1,3 có giá trị là 8;

Quay vòng dãy số trên ta có dãy số: 3,6,2,1 có giá trị là 10

Quay vòng dãy số trên ta có 1,3,6,2 có giá trị là 6

Quay vòng dãy số trên ta có dãy số 2,1,3,6 có gí trị là 4

Vậy giá trị lớn nhất tìm được là 10


Bình luận

Hãy đọc nội quy trước khi bình luận.


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