Найважливіше — правильно прочитати умову: на першій сторінці видно найсвіжіших листів узагалі, а не не-спамів. Спам теж займає місце на сторінці. Плутанина тут — найпоширеніша причина неправильних розв'язків.
Тепер спостереження, яке робить задачу лінійною. Листи, що не є спамом і вже потрапили на першу сторінку, залишаються на ній назавжди: вони найсвіжіші з-поміж тих, що лишилися, і Вася їх ніколи не видаляє. Тому стан системи повністю описується двома числами:
— скільки не-спамових листів уже «осіло» на сторінці;
— індекс наступного ще не показаного листа.
Один крок моделювання виглядає так:
сторінці бракує M - \mathit{kept} листів; беремо стільки наступних листів починаючи з позиції (або менше, якщо листи скінчилися) і зсуваємо ;
серед узятих рахуємо кількість спаму і кількість не-спаму ;
якщо s = 0, спаму на сторінці немає — Вася задоволений, зупиняємось;
інакше збільшуємо лічильник натискань на одиницю, додаємо до кількості видалених листів, а не-спамові листи залишаються на сторінці: \mathit{kept} \mathrel{+}= t.
Кожен лист проглядається рівно один раз, тому складність — , і жодного фізичного зсування масиву робити не треба.
Зверніть увагу на завершення: коли листи закінчилися, чергова ітерація візьме нуль нових листів, отримає s = 0 і коректно зупиниться.
Виводимо два числа — скільки листів видалено і скільки разів натиснуто кнопку. Кількість видалених може сягати N = 2 \cdot 10^5, тож звичайного цілого типу вистачає.