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 , cần xây dựng dãy số nguyên thỏa mãn các điều kiện sau:
Dãy là đơn điệu tăng, nghĩa là ;
Độ chênh lệch ) giữa hai dãy và được tính theo công thức là nhỏ nhất.
Dãy 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 của dãy số .
Yêu cầu: Hãy giúp Vinh tìm dãy số thỏa mãn các yêu cầu đặt ra.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên dương ;
Dòng thứ hai chứa số nguyê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ố đã cho.
Dữ liệu ra:
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 số nguyê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ó số test ứng với số điểm của bài thỏa mãn điều kiện: ;
Có số test khác ứng với số điểm của bài thỏa mãn điều kiện: ;
Có số test khác ứng với số điểm của bài thỏa mãn điều kiện: ;
Có số test khác ứng với số điểm của bài thỏa mãn điều kiện: ;
Có số test còn lại ứng với số điểm của bài thỏa mãn điều kiện: .
Đối với mỗi test, số điểm của test dành cho việc đưa ra giá trị độ chênh lệch nhỏ nhất và 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.
