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

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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

Vinh rất thích các bài toán liên quan đến dãy số. Vừa qua thầy dạy giải tích đã giao cho Vinh giải quyết bài toán sau đây:

Cho dãy số nguyên ~A = \, <a\_1, a\_2, \ldots, a\_N>~, cần xây dựng dãy số nguyên ~B = \, <b\_1, b\_2, \ldots, b\_N>~ thỏa mãn các điều kiện sau:

  • Dãy ~B~ là đơn điệu tăng, nghĩa là ~b_1 < b_2 < \ldots < b_N~;
  • Độ chênh lệch ~d(A, B)~ giữa hai dãy ~A~ và ~B~ được tính theo công thức: ~d(A, B) = |a_1 − b_1| + |a_2 − b_2| + ... + |a_N − b_N|~ là nhỏ nhất.

Dãy ~B~ thỏa mãn các điều kiện nêu trên được gọi là dãy đơn điệu tăng xấp xỉ tốt nhất dãy số ~A~.

Yêu cầu: Hãy giúp Vinh tìm dãy số ~B~ thỏa mãn các yêu cầu đặt ra.

Input

  • Dòng đầu tiên chứa số nguyên dương ~N~;
  • Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~, hai số liên tiếp được ghi cách nhau bởi dấu cách, là các số hạng của dãy số ~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;
  • Dòng thứ hai chứa ~N~ số nguyên ~b_1, b_2, \ldots, b_N~, hai số liên tiếp được ghi cách nhau bởi dấu cách, là các số hạng của dãy tìm được. Nếu có nhiều dãy cùng thỏa mãn các điều kiện đặt ra, hãy đưa ra một dãy tùy ý trong số chúng.

Giới hạn

  • Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N = 3~; ~0 \le a_k \le 10^9, k = 1, 2, \ldots, N~;
  • Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N \le 300~; ~0 \le a_k \le 300, k = 1, 2, \ldots, N~;
  • Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N \le 300~; ~0 \le a_k \le 10^9, k = 1, 2, \ldots, N~;
  • Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N \le 3\,000~; ~0 \le a_k \le 10^9, k = 1, 2, \ldots, N~;
  • Có ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N \le 300\,000~; ~0 \le a_k \le 10^9, k = 1, 2, \ldots, N~.

Đối với mỗi test, ~50\%~ số điểm của test dành cho việc đưa ra giá trị độ chênh lệch nhỏ nhất và ~50\%~ số điểm còn lại dành cho việc đưa ra dãy đơn điệu tăng xấp xỉ tốt nhất dãy đã cho.

Sample Input

7
1 5 1 7 3 1 3

Sample Output

17
-1 0 1 2 3 4 5

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


Comments

Please read the guidelines before commenting.


There are no comments at the moment.