[Algorytmy] Skoczek [B] Potyczki Algorytmiczne 2009

[matexik]

Nie potrafię wymyślić algorytmu do zadania (K,N)-skoczek skoczek.
Jeśli ktoś ma jakiś pomysł to proszę podpowiedź.

[pasman]

Zastanów się, kiedy skoczek przesunie się w poziomie o zadaną liczbę pól
bez przesuwania w pionie.

[matexik]

Jeśli założymy, że skoczek może skakać na długość \(\displaystyle{ a}\) i \(\displaystyle{ b}\). to aby nie przesunął się w pionie musi istnieć jakaś kombinacja
\(\displaystyle{ 2a * m + 2b * n}\), która jest równa odległości w poziomie, ale nie wiem co mi to wciąż daje.

[Jan Kraszewski]

Jeśli odległość w poziomie jest wynosi \(\displaystyle{ p}\), to muszą istnieć liczby całkowite \(\displaystyle{ x,y}\) takie, że \(\displaystyle{ ax+by=p}\). No i teraz w temacie pojawia się rozszerzony algorytm Euklidesa - takie \(\displaystyle{ x,y}\) istnieją jeśli \(\displaystyle{ NWD(a,b)\mid p}\).

JK