problem z zrozumieniem treści

0

Witam robie ostatnio takie zadania:

Na nieskończonej szachownicy znajduje się superskoczek, który może wykonywać różnego rodzaju ruchy. Każdy rodzaj ruchu jest określony za pomocą dwóch liczb całkowitych - pierwsza mówi o ile kolumn (w prawo w przypadku liczby dodatniej lub w lewo w przypadku liczby ujemnej), a druga o ile wierszy (do przodu w przypadku liczby dodatniej lub do tyłu w przypadku liczby ujemnej) przesuwa się skoczek wykonując taki ruch.
Zadanie
Napisz program, który:
??wczyta z pliku tekstowego sup.in zestawy danych opisujące różne superskoczki,
??dla każdego superskoczka stwierdzi, czy za pomocą swoich ruchów może dotrzeć do każdego pola na planszy,
??zapisze wynik do pliku tekstowego sup.out .
Wejście
W pierwszym wierszu pliku tekstowego sup.in znajduje się jedna liczba całkowita k określająca liczbę zestawów danych, 1<=k<=100. Po niej następuje k zestawów danych. W pierwszym wierszu każdego z nich pojawia się liczba całkowita n będąca liczbą rodzajów ruchów, które może wykonywać superskoczek, 1<=n<=100. Każdy z kolejnych n wierszy zestawu danych zawiera dwie liczby całkowite p i q oddzielone pojedynczym odstępem, opisujące ruch, -100<=p, q<=100.
Wyjście
Plik tekstowy sup.out powinien składać się z k wierszy. Wiersz i-ty powinien zawierać jedno słowo TAK, jeśli superskoczek opisany w i-tym zestawie danych może dotrzeć do każdego pola na planszy, a słowo NIE w przeciwnym przypadku.
Przykład
Dla pliku wejściowego sup.in:
2
3
1 0
0 1
-2 -1
5
3 4
-3 -6
2 -2
5 6
-1 4

I mam problem po pierwsze z ustaleniem wielkosci szachownicy dla chociażby taich danych:

3
1 0
0 1
-2 -1

Wydaje mi się, ze wielkość szachownicy to 5 na 5 (moduł z -2 + pole zerowe), ale nie wiem czy dobrze myślę..

0

hmm.. niekończona szachownica.. ale pierwsza myśl jaki mi nachodzi do głowy to: jeżeli szachownica jest nieskończona, to jeżeli ruchy są we wszystkich kierunkach, to na pewno superskoczek stanie na wszystkich polach,, ale tak się nie dzieje wedle:

5
3 4
-3 -6
2 -2
5 6
-1 4

0

No np. w tym przypadku się nie da :D może spróbuj sobie rozrysować sobie to na kartce i sprawdź, gdzie skoczek nie będzie mógł być (przy czym radziłbym zwrócić szczególną uwagę na drugą współrzędną). Jakbyś jednak coś zauważył, to nie jestem pewien, czy to będzie pasować do wszystkich przypadków - bo na pewno nie będzie się dało dla zestawu (2: (2, 1), (-1, -1)).

0

Wydaję mi się, że rozwiązanie tkwi w kierunkach ruchu skoczka.. jest ich właściwie 8..
góra, dół, góra-lewo , góra-prawo , dół-prawo , dół-lewo. Teraz tylko zobaczyć dlaczego pierwszy przykład jest ok a drugi jest be.

0

Dostrzegam już, że tam brakuje nie parzystej współrzędnej przez co skoczek nie będzie mógł stanąć na takim polu.. Czyli jeżeli nie ma jedynki i brak parzystych w dół, góra lub nie parzystych to się nie da.. ale czy tylko to?

0

Dobra, doszedłem do czegoś takiego: czy można znaleźć takie pola, że jeśli da się na nich stanąć, to można dotrzeć wszędzie, a jeśli się nie da, to już nie można dotrzeć wszędzie? Wydaje mi się, że można będzie wtedy użyć BFS-a lub DFS-a, ale nie obiecuję.

0

Trochę zawile to napisałeś:)
Mi teraz wydaje się, że rozwiązanie będzie dużo prostsze. Mamy odpowiedzieć tylko "TAK" lub "NIE"
Musimy po prostu sprawdzić czy odpowiednio
-dla pionu: czy mamy wartości parzyste i nie parzyste (z tym, że po jednej dla dodatnich i ujemnych) i musimy jeszcze sprawdzić czy moduł z tych liczb jest różny bo dla np. 3 i -3 nie jest to możliwe.
czyli dla pionu zachodziłoby dla np: -3 i 5 lub 3 i -5 a NIE zachodziło by dla -3 i 3 lub 3 i 10 lub -3 i -10
-dla poziomu: robimy praktycznie to samo..

jeżeli takich wartości nie mamy to nie ma opcji, żeby stanąć na wszystkich polach a z drugiej strony jeżeli są a plansza jest nieskończona, to oznacza, że jest na tyle duża aby stanąć na wszystkich polach. Gdyby była ograniczona, zadanie byłoby trudniejsze i chyba rzeczywiście należałoby szukać bardziej wyrafinowanego sposobu..
Wydaje mi się ok, jak myślicie?

0

Jeśli szachownica jest nieskończona, to skoczek na pewno nie może dotrzeć do każdego pola na planszy. :D

0

@iooi a to czemu? W nieskończonej ilości ruchów mógłby bez problemu ;] Widać słabo u ciebie z wyobraźnią ;)

0
Shalom napisał(a)

@iooi a to czemu? W nieskończonej ilości ruchów mógłby bez problemu ;] Widać słabo u ciebie z wyobraźnią ;)

Zakładając nawet, że czas jest nieskończony, to i tak nie dotrze. Na skutek tarcia będzie robił się coraz mniejszy, w pewnym momencie zniknie.

0

Już to napisałem, ale tak wg. teraz propozycja rozwiązania tego za pomocą "BFS-a lub DFS-a" wydaje mi się gorzej niż zła..

0

@skoczek sam fakt że w poleceniu masz nieskończoną szachownicę powinien ci dać do myślenia, ze w zadaniu chodzi o odszukanie pewnej matematycznej zalezności dzięki której mozna stwierdzić czy skoczek moze odwiedzić każde pole czy też nie ;)

0

To ciekawy problem i raczej niełatwy do rozwiązania. W uproszczeniu chodzi o to, żeby udowodnić, że skoczek w czasie poruszania się nie może wytworzyć pozycji która spowoduje zablokowanie sobie dostępu do pewnych pól.

0

mi to przypomina sprawdzanie, czy pewien wektor jest kombinacją liniową (o współczynnikach całkowitych) innych wektorów

http://www.matematyka.pl/38729.htm

0

Teraz zaproponowałbym nieco inne rozwiązanie - bo jeśli da się znaleźć taką czwórkę liczb całkowitych dodatnich a,b,c,d, że NWD(a,b)=1, NWD(c,d)=1 oraz skoczek może dotrzeć na pola (a,0), (-b,0) [czyli że można poruszać się po osi 0X w przód o a i w tył o b; ponieważ a,b są względnie pierwsze, będzie można dotrzeć na każde możliwe pole na osi 0X], (0,c), (0,-d) [analogicznie dla osi 0Y], to będzie można dotrzeć na każde pole na szachownicy.

Do wyznaczenia możliwych a,b,c,d proponowałbym taką metodę [przedstawiłem dla a,b, czyli osi 0X - analogicznie można zrobić dla osi 0Y]: bierzemy każdą możliwą parę wektorów (p1,q1), (p2,q2); jeśli wartości q1, q2 mają takie same znaki (czyli po wykonaniu ruchu znajdziemy się zawsze pod lub nad osią 0X), para nam odpada; jeśli q1=0 lub q2=0, to już możemy dopisać sobie odpowiednio p1 lub p2 do listy*; inaczej chcemy, by dla m skoków pierwszego typu i n skoków drugiego typu (m,n>0) otrzymać y=0:
m*q1 + n*q2 = 0
które będzie miało swoje najmniejsze możliwe rozwiązanie dla m=q2/NWD(q1,q2), n=q1/NWD(q1,q2). Wtedy możemy sobie policzyć, na które miejsce na osi trafiliśmy i dodać sobie do listy*.

  • widzimy, że a będzie przechowywać przesunięcie naprzód po osi 0X, a b w tył - więc jeśli dodajemy do listy liczbę dodatnią, to dodajemy ją do listy z wartościami a; inaczej dodajemy jej wartość bezwzględną (bo chcemy tyle, ile cofniemy się w tył) do listy z wartościami b.*

Potem trzeba byłoby jeszcze znaleźć względnie pierwsze pary liczb (a,b), (c,d)...

Mam nadzieję, że to wszystko jest zrozumiałe :D Rozpisałem się, a to tylko zarys algorytmu...

0

http://www.oi.edu.pl/html/blue/download/oi9.pdf
Nie ma tu ani jednego twojego słowa :) Znalazłem to już po napisaniu programu,, a tak wg. mojego rozwiązania tam nie ma, a też jest poprawne..:)

1 użytkowników online, w tym zalogowanych: 0, gości: 1