Val Karan igra igru na ploči s
redaka i
stupca. U
polja skrivena su čudovišta. U početku Val ne zna gdje se nalaze čudovišta, ali zna da se u svakom retku, osim u prvom i posljednjem, nalazi točno jedno čudovište te da svaki stupac sadrži najviše jedno čudovište.
Val poduzima niz pokušaja kako bi stigao od prvog do posljednjeg retka. U svakom pokušaju bira početno polje u prvom retku, a zatim se uzastopno pomiče na susjedno polje (ono s kojim dijeli stranicu). (Dopušteno mu je vratiti se na prethodno posjećeno polje.) Ako stigne na polje s čudovištem, pokušaj završava i on se vraća u prvi red kako bi započeo novi pokušaj. Čudovišta se ne pomiču, a Val pamti sadrži li svako polje koje je posjetio čudovište ili ne (nije još toliko dementan. Ako stigne na bilo koje polje u posljednjem retku, pokušaj završava i igra je gotova.
Odredite najmanju vrijednost broja 
za koju Val ima strategiju koja jamči dolazak do posljednjeg retka u -tom pokušaju ili ranije, bez obzira na položaj čudovišta.
Wave Screwed plays a game on a board with
rows and
columns. There are hidden monsters in
of the cells. Initially, Wave does not know where any of the monsters are, but he knows that there is exactly one monster in each row except the first row and the last row, and that each column contains at most one monster.
Wave makes a series of attempts to go from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then repeatedly moves to an adjacent cell sharing a common side. (He is allowed to return to a previously visited cell.) If he reaches a cell with a monster, his attempt ends and he is transported back to the first row to start a new attempt. The monsters do not move, and Wave remembers whether or not each cell he has visited contains a monster (dementia hasn't kicked that hard yet). If he reaches any cell in the last row, his attempt ends and the game is over.
Determine the minimum value of for which Wave has a strategy that guarantees reaching the last row on the -th attempt or earlier, regardless of the locations of the monsters.
[lang=hr]
Val Karan igra igru na ploči s $2026$ redaka i $2025$ stupca. U $2024$ polja skrivena su čudovišta. U početku Val ne zna gdje se nalaze čudovišta, ali zna da se u svakom retku, osim u prvom i posljednjem, nalazi točno jedno čudovište te da svaki stupac sadrži najviše jedno čudovište.
Val poduzima niz pokušaja kako bi stigao od prvog do posljednjeg retka. U svakom pokušaju bira početno polje u prvom retku, a zatim se uzastopno pomiče na susjedno polje (ono s kojim dijeli stranicu). (Dopušteno mu je vratiti se na prethodno posjećeno polje.) Ako stigne na polje s čudovištem, pokušaj završava i on se vraća u prvi red kako bi započeo novi pokušaj. Čudovišta se ne pomiču, a Val pamti sadrži li svako polje koje je posjetio čudovište ili ne (nije još toliko dementan. Ako stigne na bilo koje polje u posljednjem retku, pokušaj završava i igra je gotova.
Odredite najmanju vrijednost broja $n$ za koju Val ima strategiju koja jamči dolazak do posljednjeg retka u $n$-tom pokušaju ili ranije, bez obzira na položaj čudovišta.
[/lang]
[lang=en]
Wave Screwed plays a game on a board with $2026$ rows and $2025$ columns. There are hidden monsters in $2024$ of the cells. Initially, Wave does not know where any of the monsters are, but he knows that there is exactly one monster in each row except the first row and the last row, and that each column contains at most one monster.
Wave makes a series of attempts to go from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then repeatedly moves to an adjacent cell sharing a common side. (He is allowed to return to a previously visited cell.) If he reaches a cell with a monster, his attempt ends and he is transported back to the first row to start a new attempt. The monsters do not move, and Wave remembers whether or not each cell he has visited contains a monster (dementia hasn't kicked that hard yet). If he reaches any cell in the last row, his attempt ends and the game is over.
Determine the minimum value of $n$ for which Wave has a strategy that guarantees reaching the last row on the $n$-th attempt or earlier, regardless of the locations of the monsters.
[/lang]
