Editorial for Bedao Mini Contest 06 - YUGIOH


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

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

Please read the guidelines before commenting.


There are no comments at the moment.