Đoạn nguyên tố
Cho một dãy số nguyên dương \(a_1, a_2, a_3,.., a_n (1 \le a_i \le 10^6; 1 \le i \le n)\). Với mỗi phần tử \(a_i\) 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 \le k \le n \le 10^5);\)
- Dòng 2: Chứa \(n\) số nguyên dương \(a_1, a_2, a_3,.., a_n (1 \le a_i \le 10^6,\) với \(1 \le i \le 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ó \(a_i\) đều là số nguyên tố với \(1 \le i \le n\);
- Có 40% số điểm có \(n, k \le 5000; a_i \le 5000\) với \(1 \le i \le 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 =)))
:::))))