Editorial for Bedao Mini Contest 06 - YUGIOH
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Gọi hàm ~isGood(x)~ là hàm xác định phần tử ~a_i~ thỏa mãn đề bài, ~isGood(x) = 1~ khi ~0 < a_i \leq X~ và ~a_i~ là số nguyên tố, ngược lại ~isGood(x) = 0~.
Gọi ~p_i~ là số các số thỏa mãn ~isGood(x) = 0~ từ ~1~ đến ~i~.
Gọi ~cnt~ là số lượng số thỏa mãn ~isGood(x) = 1~.
Nhận xét: Ta cần nhét hết tất cả các số có ~isGood(x) = 1~ nằm cạnh nhau, giả sử ta đang xét ở phần tử thứ ~i~ thì để nhét đủ ta cần các số trong đoạn ~[i-cnt+1,i]~ thỏa mãn ~isGood(x) = 1~.
Vì các số thỏa mãn yêu cầu đề bài có thể nằm bất cứ đâu nhưng cách tối ưu để xếp cạnh nhau là đưa các số ~isGood(x) = 1~ ngoài đoạn ~[i-cnt+1,i]~ về vị trí các số ~isGood(x) = 0~ mà nằm cạnh các số ~isGood(x) = 1~ trong đoạn ~[i-cnt+1,i]~. Vậy đáp án bài toán chính là ~min(p_i-p_{i-cnt+1})~ với ~i-cnt+1 < i \leq n~.
Comments