Масив монет і запити зважування (Розбір)

Фальшиві монети йдуть поспіль, тому вся невідомість зводиться до одного числа — позиції $p$ найлівішої фальшивої монети. Оскільки блок довжини $k$ має вміститися в ряд, одразу знаємо, що p \in [1,\; n-k+1].

Ідея — звужувати цей відрізок потрійним пошуком за допомогою одного зважування на крок.

Нехай поточний відрізок кандидатів — $[L,R]$, його довжина D = R - L + 1, і візьмемо x = \left\lceil D/3 \right\rceil. Покладемо на ліву шальку монети з номерами L, L+1, \ldots, L+x-1, а на праву — монети R+k-x, \ldots, R+k-1. Обидві множини мають по $x$ монет і не перетинаються.

Порахуємо, скільки фальшивих потрапляє на кожну шальку. Монета $i$ фальшива тоді й лише тоді, коли p \le i \le p+k-1. Звідси:

• на лівій шальці фальшивих рівно \max(0,\; L + x - p) — вони з'являються лише коли p < L + x;

• на правій рівно \max(0,\; p - R + x) — вони з'являються лише коли p > R - x.

Фальшиві легші, тому легшою виявиться та шалька, де їх більше. Це дає три випадки:

• ліва легша — фальшивих ліворуч більше, отже $p$ лежить у лівій третині: звужуємо до [L,\; L+x-1];

• права легша — симетрично, $p$ у правій третині: звужуємо до [R-x+1,\; R];

• рівновага — кількості збіглися; за наведеними формулами це означає, що $p$ лежить у середній частині [L+x,\; R-x].

Кожне зважування зменшує довжину відрізка приблизно втричі, тому потрібно близько \log_3 n запитів — при n \le 10^4 це менш ніж десяток.

Не забувайте про flush після кожного запиту. Коли L = R, відповідь знайдено.