Zadanie Robocik OI

pytanie zadane 16 stycznia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Natknąłem się na zadanie Robicik z 1 etapu XXVI OI. https://szkopul.edu.pl/problemset/problem/p4hlBS7BwoH_rymSj2wtb5_J/site/?key=statement

Nie mam pomysłu na rozwiązanie o sensownej złożonności, ale mam 3 spostrzerzenia.

- Ile robocik wykona ruchów(sekwencji gora prawo dol lewo) mozna wyszukać binarnie (o ile to coś da)

- W każdym ruchu (sekwencji gora prawo dol lewo), maksymalnie raz stanie na polu szukanym.

- Robocik po każdym ruchu(sekwencji) będzie przesuwał się o stałą liczbę x i y. Np w tescie przykladowym zaczyna na 0,0 po 1 sekwencji jest na 1,1 po 2 na 2,2, po 3 by byl na 3,3 itd.

Wiem ze moge symulowac kazda sekwencje w O(1), ale tych sekwencji może być bardzo dużo, więć pewnie maks z jakieś 20pkt da.

Ma ktoś jakiś pomysł jak poskładać to w całość / inny pomysł

Z góry dziękuję za poświęcony czas i pomoc.

komentarz 16 stycznia 2023 przez Whistleroosh Maniak (56,980 p.)

O nie to było straszne zadanie. Pomysł na rozwiązanie nie był trudny z tego co pamietam, ale kod do tego ma co najmniej 500 linijek

komentarz 16 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

a jakaś trudna technika czy jak?

komentarz 16 stycznia 2023 przez Whistleroosh Maniak (56,980 p.)

Nie, po prostu dużo przypadków do rozpatrywania

komentarz 16 stycznia 2023 przez jankustosz1 Nałogowiec (35,880 p.)

Też pamiętam to zadanie. Cała sztuczka polega na tym aby zauważyć, że powstaje cykl i po pewnej ilości ruchów zaczyna się on od nowa. Dzięki czemu można raz wyliczyć o jaki wektor przesunie nasz cykl, następnie dodać ten wektor tyle razy ile cyklów się zmieści, a końcówkę policzyć na pałę.