Wrocławski Portal Informatyczny
http://informatyka.wroc.pl/forum/

[Rozwiązania]Paweł i gaweł
http://informatyka.wroc.pl/forum/viewtopic.php?f=83&t=1161
Strona 1 z 1

Autor:  Damian Dyńdo [ 15 kwi 2011, o 18:02 ]
Tytuł:  [Rozwiązania]Paweł i gaweł

Witam, jako iż nie przystąpiłem do tego zadania (mało czasu) oraz nie miałem z początku dobrego pomysłu - mógłby się ktoś pochwalić ciekawszymi metodami ? ;)

Autor:  Paweł Michalak [ 15 kwi 2011, o 19:18 ]
Tytuł:  Re: [Rozwiązania]Paweł i gaweł

Programowanie dynamiczne.

Autor:  Aleksander Kramarz [ 15 kwi 2011, o 19:49 ]
Tytuł:  Re: [Rozwiązania]Paweł i gaweł

Zwycięzca konkursu na omówienie roku.

Autor:  Bartek Dudek [ 15 kwi 2011, o 20:14 ]
Tytuł:  Re: [Rozwiązania]Paweł i gaweł

Paweł Michalak napisał(a):
Programowanie dynamiczne.

nie no, dobrze zaczął :D

generalnie masz dla każdego pola dwie możliwe sytuacje:
a)gracz, który ma teraz ruch jest na łóżku
b)gracz, który teraz ma ruch jest pod łóżkiem

no i chcesz wiedzieć, czy w tej sytuacji może wygrać, czyli skończyć na górze, więc pozostaje rozpatrywać, co będzie gdy pójdziemy w odpowiednią stronę.

no i teraz lecimy po tej mapce od tyłu (ruchy mamy przeciwne do tych z zadania) i dzięki temu dynamicznie możemy liczyć odpowiedź

Nasuwa się pytanie, czy nie musimy jeszcze pamiętać, który gracz ma teraz ruch. Otóż nie, bo to można łatwo wywnioskować z parzystości sumy współrzędnych-->
Paweł - 0,
Gaweł - 1.

czas : n*m,
pamięć: łatwo n*m, przy odrobinie gimnastyki min(m+n) + k.

Pozdrawiam : )

Autor:  Damian Dyńdo [ 15 kwi 2011, o 20:45 ]
Tytuł:  Re: [Rozwiązania]Paweł i gaweł

Dzięki serdeczne za opis ;) Po skończeniu konkursu spróbuję tak dla "wprawy" "zakodzić" coś takiego :).

Autor:  Marek Bardoński [ 16 kwi 2011, o 19:00 ]
Tytuł:  Re: [Rozwiązania]Paweł i gaweł

Jeśli chodzi o mnie, zrobiłem zadanie intuicyjną metodą, robiąc 2 tablice (jak Paweł jest na górze i jak Paweł jest na dole) w których trzymałem informacje, czy dana pozycja jest wygrywająca czy przegrywająca. Potem od końca dla każdego pola, z którego da się dojść do pozycji przegrywającej (dla następnego gracza) wstawiałem '1'. A jak pole był z X to krzyżowałem tablice ze sobą. Wartość początkowa to 1 na końcu gdy Paweł jest na górze i 0 gdy jest na dole, wynik był w pierwszym polu w tablicy Paweł na górze.

Autor:  Wojciech Żółtowski [ 30 kwi 2011, o 22:31 ]
Tytuł:  Re: [Rozwiązania]Paweł i gaweł

aleee...że jak? snczy ja ten dynamiczny zarys trochę chyba rozumiem, ale jak to zrobić?

Autor:  Damian Dyńdo [ 3 maja 2011, o 22:39 ]
Tytuł:  Re: [Rozwiązania]Paweł i gaweł

Masz omówienie?!

Autor:  Wojciech Żółtowski [ 4 maja 2011, o 12:43 ]
Tytuł:  Re: [Rozwiązania]Paweł i gaweł

jeśli chodzi Ci o to ,co wcześniej Bartek napisał, dla mnie to za mało. Nie mam praktycznie żednej wprawy z dynamikami, więc pozostaje pytanie jak to liczenie dynamiczne ma działać;)

Autor:  Wojciech Żółtowski [ 4 maja 2011, o 12:46 ]
Tytuł:  Re: [Rozwiązania]Paweł i gaweł

ok, nie zauważyłem ich...xd

Strona 1 z 1 Strefa czasowa: UTC + 1 [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/