Trại hè tin học Thái Nguyên 2020 - Khối lớp 11
Trại hè Tin học Thái Nguyên diễn ra vào tháng năm nay là một sự kiện lớn trong giới Tin học các trường THPT chuyên trên toàn miền Bắc. Tại đây không chỉ có những hoạt động trang bị kiến thức lý thú như đố vui hay uống trà sữa, mà còn là cơ hội để cho một số nhân vật đặc biệt có cơ hội được thả thính.
Dù đã sắp vào Đại học và đã quá tuổi tham gia trại hè cũng như chẳng có việc gì ở đây, thành viên đội tuyển Tin học Châu Á Hà Quang Ming dấu tên vẫn quyết định mò đến Thái Nguyên bằng mọi giá. Ming lấy lý do chính khi đến đây là vì không thể rời xa em gái nuôi, nhưng thực ra anh cũng rất tận dụng cơ hội để khoe nhãn mác APIO-er của mình và "giao lưu kết hợp" nhằm tuyển thêm hậu cung.
Năm nay, các học sinh trong trại hè được phân vào lớp. Sau một ngày dạo quanh phố phường dạo qua thị trường, Ming đã chọn ra được em gái xinh tươi nhất đến từ lớp khác nhau. Ming sẽ thả thính từng em một, và với em gái thứ Ming sẽ thả túi thính có độ thơm là . Tất nhiên, Ming thường rất nhạt và thiếu muối, nên độ thơm của các túi thính có thể âm.
Kế hoạch thả thính của Ming làm cô em gái nuôi NTNA vô cùng tức giận và đòi anh trai nuôi phải ngưng lại ngay lập tức. Dù rất yêu em gái nuôi, Ming không thể từ bỏ ham muốn thả thính và chỉ chấp nhận thay đổi độ thơm của tối đa túi thính. Sau sự ra đi của Liinhh, NTNA giờ đã trở thành cô gái quyền lực nhất đội tuyển. Thế nên cô ta đưa ra yêu sách mới: để không cho Ming thả thính quá thơm, độ chênh lệch lớn nhất giữa hai túi thính liền nhau, tức phải nhỏ nhất có thể.
Hãy giúp Ming thay đổi không quá túi thính để có thể giữ lại em gái nuôi.
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên và – số em gái Ming muốn thả thính và số túi thính tối đa Ming muốn thay đổi;
Dòng thứ hai chứa số nguyên – độ thơm của các túi thính theo dự định của Ming.
Dữ liệu ra:
Một số nguyên duy nhất là giá trị nhỏ nhất của .
Giới hạn:
Subtask và
Subtask và
Subtask Không có ràng buộc gì thêm
Ví dụ
Dữ liệu vào:
5 2
4 7 4 7 4
Dữ liệu ra:
0
Dữ liệu vào:
6 2
1 2 3 7 8 9
Dữ liệu ra:
2
Giải thích:
Trong ví dụ thứ nhất, một phương án tối ưu là thay đổi độ hấp dẫn của các túi thính thứ và thành . Khi đó độ hấp dẫn của các túi thính là . Chênh lệch giữa hai túi thính cạnh nhau là .
Trong ví dụ thứ hai, một phương án tối ưu là thay đổi độ hấp dẫn của các túi thính thứ và thành và . Độ hấp dẫn của các túi thính trở thành . Chênh lệch giữa hai túi thính cạnh nhau lớn nhất là .
