VOI 18 Bài 6 - Dãy xấp xỉ tăng - VNOJ: VNOI Online Judge

VOI 18 Bài 6 - Dãy xấp xỉ tăng

Points: 1.50 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Problem type

Allowed languages

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

In case the statement didn't load correctly, you can download the statement here: Statement

Đọc đề gốc tại đây

Vinh rất thích các bài toán liên quan đến dãy số. Vừa qua thầy dạy giải tích đã giao cho Vinh giải quyết bài toán sau đây:

Cho dãy số nguyên ~A = \, <a_1, a_2, \ldots, a_N>~, cần xây dựng dãy số nguyên ~B = \, <b_1, b_2, \ldots, b_N>~ thỏa mãn các điều kiện sau:

Dãy ~B~ là đơn điệu tăng, nghĩa là ~b_1 < b_2 < \ldots < b_N~;
Độ chênh lệch ~d(A, B)~ giữa hai dãy ~A~ và ~B~ được tính theo công thức: ~d(A, B) = |a_1 - b_1| + |a_2 - b_2| + ... + |a_N - b_N|~ là nhỏ nhất.

Dãy ~B~ thỏa mãn các điều kiện nêu trên được gọi là dãy đơn điệu tăng xấp xỉ tốt nhất dãy số ~A~.

Yêu cầu: Hãy giúp Vinh tìm dãy số ~B~ thỏa mãn các yêu cầu đặt ra.

Input

Dòng đầu tiên chứa số nguyên dương ~N~;
Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~, hai số liên tiếp được ghi cách nhau bởi dấu cách, là các số hạng của dãy số ~A~ đã cho.

Output

Dòng đầu tiên chứa một số nguyên là độ chênh lệch giữa dãy số tìm được với dãy đã cho;
Dòng thứ hai chứa ~N~ số nguyên ~b_1, b_2, \ldots, b_N~, hai số liên tiếp được ghi cách nhau bởi dấu cách, là các số hạng của dãy tìm được. Nếu có nhiều dãy cùng thỏa mãn các điều kiện đặt ra, hãy đưa ra một dãy tùy ý trong số chúng.

Giới hạn

Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N = 3~; ~0 \le a_k \le 10^9, k = 1, 2, \ldots, N~;
Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N \le 300~; ~0 \le a_k \le 300, k = 1, 2, \ldots, N~;
Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N \le 300~; ~0 \le a_k \le 10^9, k = 1, 2, \ldots, N~;
Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N \le 3\,000~; ~0 \le a_k \le 10^9, k = 1, 2, \ldots, N~;
Có ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N \le 300\,000~; ~0 \le a_k \le 10^9, k = 1, 2, \ldots, N~.

Đối với mỗi test, ~50\%~ số điểm của test dành cho việc đưa ra giá trị độ chênh lệch nhỏ nhất và ~50\%~ số điểm còn lại dành cho việc đưa ra dãy đơn điệu tăng xấp xỉ tốt nhất dãy đã cho.

Sample Input

7
1 5 1 7 3 1 3

Sample Output

17
-1 0 1 2 3 4 5

Comments

Please read the guidelines before commenting.

There are no comments at the moment.