Đoạn nguyên tố
Cho một dãy số nguyên dương a1,a2,a3,..,an(1≤ai≤106;1≤i≤n). Với mỗi phần tử ai bạn được phép tăng hoặc giảm một lượng tùy ý để được một số nguyên tố. Khi đó chi phí của bạn cần bỏ ra chính là lượng tăng hoặc giảm đó.
Yêu cầu: Hãy chọn ra một đoạn con gồm k phần tử liên tiếp nhau của dãy A sao cho tổng chi phí biến đổi mọi phần tử trong đoạn cón đó thành các số nguyên tố là nhỏ nhất.
Dữ liệu vào:
- Dòng 1: Chứa hai số nguyên dương n,k(1≤k≤n≤105);
- Dòng 2: Chứa n số nguyên dương a1,a2,a3,..,an(1≤ai≤106, với 1≤i≤n)
Dữ liệu ra:
- Một số nguyên duy nhất là tổng chi phí biến đổi nhỏ nhất tìm được.
Ví dụ:
| INPUT | OUTPUT |
|---|---|
| 4 2 9 5 8 15 |
1 |
Giải thích:
- Chọn đoạn [5,8], biến đổi 8 -> 7 với chi phí là 1
Giới hạn:
- Có 20% số điểm có ai đều là số nguyên tố với 1≤i≤n;
- Có 40% số điểm có n,k≤5000;ai≤5000 với 1≤i≤n
- Có 40% số điểm còn lại không có ràng buộc bổ sung
Comments
làm hộ mình bài này với "Tìm kiếm nhị phân 30"
m k bt lm, b tự đi mà lm =)))
:::))))