SPAM#194

SPAM (Editorial)

Найважливіше — правильно прочитати умову: на першій сторінці видно найсвіжіших листів узагалі, а не не-спамів. Спам теж займає місце на сторінці. Плутанина тут — найпоширеніша причина неправильних розв'язків.

Тепер спостереження, яке робить задачу лінійною. Листи, що не є спамом і вже потрапили на першу сторінку, залишаються на ній назавжди: вони найсвіжіші з-поміж тих, що лишилися, і Вася їх ніколи не видаляє. Тому стан системи повністю описується двома числами:

  • — скільки не-спамових листів уже «осіло» на сторінці;

  • — індекс наступного ще не показаного листа.

Один крок моделювання виглядає так:

  1. сторінці бракує M - \mathit{kept} листів; беремо стільки наступних листів починаючи з позиції (або менше, якщо листи скінчилися) і зсуваємо ;

  2. серед узятих рахуємо кількість спаму і кількість не-спаму ;

  3. якщо s = 0, спаму на сторінці немає — Вася задоволений, зупиняємось;

  4. інакше збільшуємо лічильник натискань на одиницю, додаємо до кількості видалених листів, а не-спамові листи залишаються на сторінці: \mathit{kept} \mathrel{+}= t.

Кожен лист проглядається рівно один раз, тому складність — , і жодного фізичного зсування масиву робити не треба.

Зверніть увагу на завершення: коли листи закінчилися, чергова ітерація візьме нуль нових листів, отримає s = 0 і коректно зупиниться.

Виводимо два числа — скільки листів видалено і скільки разів натиснуто кнопку. Кількість видалених може сягати N = 2 \cdot 10^5, тож звичайного цілого типу вистачає.