Федерація ООП#34

Федерація ООП (Розбір)

Задача виглядає як складна теорія ігор на дереві, але насправді відповідь визначається лише парністю — саме дерево взагалі не має значення.

Ключових спостережень два.

Перше: гра завжди триває, доки є незамальовані міста. Множина з одного міста задовольняє обидві умови «хорошої» (вона тривіально зв'язна, а — непарне число). Тому гравець, у якого лишилося хоч одне незамальоване місто, завжди має хід. Отже, гра закінчується рівно тоді, коли замальовано всі міст, і програє той, чия черга настала після цього.

Друге: парність кількості ходів фіксована. Кожен хід замальовує непарну кількість міст. Якщо всього зроблено ходів, то сума непарних чисел дорівнює . А сума непарних чисел завжди має ту саму парність, що й , отже

k \equiv n \pmod 2.

Це працює за будь-якої гри: скільки б ходів не зробили гравці і як би вони не грали, парність їх кількості визначена наперед.

Пан X ходить першим, тобто робить ходи з непарними номерами. Якщо непарне, останній хід зробив саме він, і програє Пан Y. Якщо парне, останній хід за Паном Y, і програє Пан X.

Отже, відповідь: Pan X при непарному і Pan Y при парному. Дерево читати не обов'язково — достатньо першого числа.