Международная олимпиада 2024, Бат, Великобритания, 2024 год

Турбо атты ұлу 2024 жолы және 2023 бағаны бар тақтада келесі ойын ойнайды. Тақтаның 2022 ұяшығында құбыжықтар тығылып отыр. Турбо бастапқыда құбыжықтардың қай ұяшықта отырғанын білмейді, бірақ ол бірінші және соңғы жолдан басқа әр жолда дәл бір құбыжық бар екенін; және әр бағанда ең көп дегенде бір құбыжық бар екенін біледі.
   Турбо бірінші жолдан соңғы жолға өтетіндей бірнеше әрекет жасайды. Әрбір әрекетте ол бірінші қатардағы кез келген ұяшықты бастапқы ұяшық ретінде таңдап алып, содан кейін ортақ қабырғасы бар көрші ұяшыққа өту серияларын жасайды. (Оған бұрын барған ұяшықтарға оралуға рұқсат.) Егер ол құбыжығы бар ұяшыққа түссе, онда оның осы кезектегі әрекеті аяқталады да, ол қайтадан бірінші жолға қайтарылады. Құбыжықтар қозғалмайды және Турбо ол барған әрбір ұяшықта құбыжықтың бар-жоғын есіне сақтап отырады. Егер Турбо осылай соңғы қатардағы кез келген ұяшыққа жетсе, оның әрекеті аяқталған болып есептеледі және ойын аяқталады.
   Құбыжықтардың орналасуына қарамастан Турбо $n$ немесе одан аз әрекет санында соңғы ұяшыққа жете алатындай стратегия ойлап таба алатындай ең кіші $n$ санын табыңыз.

Комментарий/решение

Ответ: 3

Оценка: Заметим, что когда турбо приходит в 2 ряд, тогда он может напороться на монстра, откуда -1 попытка, в следующем, так как он не в предыдущей клетке, он спокойно может напороться на другого монстра отсюда еще -1 попытка значит попыток хотябы 3

Давайте придумаем стратегию для 3 попыток:

Потратим одну попытку на нахождения монстра в 2 ряду и у нас есть два случая:

1) Этот монстр не в конце, тогда мы не более чем за 2 попытки подбираемся под него и дальше легко

2) Этот монстр в конце, тогда будем идти в противоположоный конец третьего ряда и рассмотрим две клетки до монстра. Если там есть монстр то можно прокрасться под монстром второго ряда создавая "лестницу", если монстров нет, то лестница дойдет до конца. Например, если первый монстр в (2;1) тогда:

(2,2)->(2,3)->(3,3)->(3,4)->...->(2024;2023).