Лицарі та брехуни#36

Лицарі та брехуни (Розбір)

Розберемося, що означає кожне висловлювання. Людина з номером (для i < n) стверджує: «усі люди з номерами, кратними i+1, — брехуни». Людина з номером мовчить.

Оскільки лицар каже правду, а брехун бреше, для кожного i < n маємо точну рівносильність:

\text{людина } i \text{ --- лицар} \iff \text{усі } j,\ (i+1) \mid j,\ j \le n,\ \text{--- брехуни}.

Тепер ключове спостереження: усі кратні числа i+1, які не перевищують , строго більші за (найменше з них — це саме i+1). Тому статус людини повністю визначається статусами людей з більшими номерами.

Звідси випливає, що вся розстановка однозначно відновлюється, щойно ми зафіксуємо статус останньої людини. А вона нічого не сказала, тому обидва варіанти допустимі — усього маємо рівно дві можливі конфігурації.

Алгоритм такий: беремо припущення про статус людини (лицар або брехун) і йдемо вниз від i = n-1 до , щоразу перевіряючи всі кратні числа i+1: якщо серед них є хоча б один лицар, то людина — брехун, інакше — лицар. Порахувавши лицарів, повторюємо те саме для другого припущення. Відповідь — менше з двох чисел при k = 0 і більше при k = 1.

Складність: для кожного ми перебираємо кратні до i+1, тобто приблизно n/(i+1) значень. Разом це гармонічна сума

\sum_{i=1}^{n} \frac{n}{i} \approx n \ln n,

що при n \le 10^5 становить близько 1.2 \cdot 10^6 операцій — цілком швидко. Обидва прогони роблять це двічі.