{"code":"bll9tpth2023c4","name":"Đoạn nguyên tố","description":"## Câu 4. ĐOẠN NGUYÊN TỐ\r\nCho một dãy số nguyên dương 𝐴 = (𝑎1, 𝑎2, … , 𝑎n) (𝑎i ≤ $10^6$; 1 ≤ 𝑖 ≤ 𝑛). Với mỗi phần tử 𝑎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 đó.\r\n***Yêu cầu:*** Hãy chọn ra một đoạn con gồm 𝑘 phần tử liên tiếp nhau của dãy 𝐴 sao cho tổng chi phí biến đổi mọi phần tử trong đoạn con đó thành các số nguyên tố là nhỏ nhất.\r\n***Dữ liệu:*** Vào từ file DOANNT.INP có cấu trúc như sau:\r\n-Dòng 1: Chứa hai số nguyên dương 𝑛, 𝑘 (1 ≤ 𝑘 ≤ 𝑛 ≤ $10^5$);\r\n-Dòng 2: Chứa 𝑛 số nguyên dương 𝑎1, 𝑎2, . . , 𝑎n (𝑎i ≤ $10^6$ ∀𝑖 = 1,2, … , 𝑛).\r\n***Kết quả:*** Ghi ra file DOANNT.OUT một số nguyên duy nhất là tổng chi phí biến đổi nhỏ nhất tìm được.\r\n***Ví dụ:***\r\n!!! Question \"TEST1\"\r\n    ???+ \"DOANNT.INP\"\r\n        4 2\r\n        9 5 8 15\r\n    ???+ \"DOANNT.OUT\"\t\r\n        1\r\n***Giải thích:*** chọn đoạn [5,8], biến đổi 8 → 7 với chi phí là 1.\r\n***Giới hạn:***\t\r\n+ Có 20% số điểm có 𝑎𝑖 đều là số nguyên tố ∀ 𝑖 = 1,2, … , 𝑛;\r\n+ Có 40% số điểm có 𝑛, 𝑘 ≤ 5000; 𝑎𝑖 ≤ 5000 ∀ 𝑖 = 1,2, … , 𝑛;\r\n+ Có 40% số điểm còn lại không có ràng buộc bổ sung.","points":2.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}