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

[Pawel i Gawel 2] Testy
http://informatyka.wroc.pl/forum/viewtopic.php?f=83&t=1169
Strona 1 z 3

Autor:  Piotr Żurkowski [ 16 kwi 2011, o 23:23 ]
Tytuł:  [Pawel i Gawel 2] Testy

Anything po raz drugi;P

Autor:  Mateusz Witkowski [ 17 kwi 2011, o 03:18 ]
Tytuł:  Re: [Pawel i Gawel 2] Testy

czy te zadanie nie jest wręcz identyczne z tym zadaniem
http://informatyka.wroc.pl/node/266 ;p ?

Autor:  Michał Kownacki [ 17 kwi 2011, o 13:26 ]
Tytuł:  Re: [Pawel i Gawel 2] Testy

Chyba nie, spryciarzu.

Autor:  Michał Kownacki [ 17 kwi 2011, o 18:13 ]
Tytuł:  Re: [Pawel i Gawel 2] Testy

Jak to zrobić??

Autor:  Bartek Dudek [ 17 kwi 2011, o 18:41 ]
Tytuł:  Re: [Pawel i Gawel 2] Testy

Da się łatwo w (n^2)(A^3), gdzie a to rozmiar najwyższego rozpatrując wszystkie stany:
(pocz, wysokość początkowego, kon, wys. końcowego) i z definicji rozpatrywać wszystkie możliwe ruchy. Można też to przyspieszyć do (nA)^2, gdyż zamiast przeglądać wszystkie ruchy zmniejszające jeden słupek, można przekazywać informację, czy gdzieś jest już zero osiągalne. Ale lepiej nie umiem. A Wy?

Autor:  Damian Dyńdo [ 17 kwi 2011, o 19:02 ]
Tytuł:  Re: [Pawel i Gawel 2] Testy

@Bartek ja doszedłem do cudownego wniosku rozpisując sporo opcji, że jedynie pożądane ruchy to albo zmniejszyć dany stos do 1 kamienia, albo wyzerować go (możliwe ruchy to zmniejszenie o 1 lub więcej). W ten sposób oddziałujemy na decyzje przeciwnika bo albo on go zeruje, albo może już korzystać z następnego. Dlatego wielkości stosów (osobiście uznawałem wielkość stosów za wysokość "słupka" :P) jest równa albo 1 albo 2 (0 nie może).

Niestety z braku testów, a samemu dla n>5-6 ciężko obliczyć (naprawdę sporo możliwości dla 1 układu, a układów może być w zależności od ułożenia poszczególnych wysokości też sporo :P). Patrząc do tego na czas 1s na 10zestawów testowych rzuciłem na chybił trafił (co również pokrywało mi się z kartką) - dla parzystej liczby słupków o takich samych wysokościach (np. 1221 lub 1111 lub 112222) wygrywa Gaweł, w przeciwnym wypadku Paweł (zdecydowanie ma łatwiej zaczynając).

Ale na 99.99% będzie WA :)

Autor:  Paweł Michalak [ 17 kwi 2011, o 19:07 ]
Tytuł:  Re: [Pawel i Gawel 2] Testy

No ale np. dla [2, 5, 3] optymalnie jest zdjąć tylko jeden kamień.

Autor:  Damian Dyńdo [ 17 kwi 2011, o 19:09 ]
Tytuł:  Re: [Pawel i Gawel 2] Testy

Niby dlaczego? Dla Gawła 1 kamień a A-1 nie robi rożnicy, bo i tak może pozbyć się całego tego rzędu lub tego z 2giej strony. Z braku większej ilości testów tylko tyle wymyśliłem i raczej się mylę, ale w tym zadaniu akurat nie widzę sensu dlaczego 1 kamień z prawego (3jki) zdejmuje, a nie np. 2 (i tak by wygrał ;)) Tak samo mógłby wygrać jakby cały zdjął prawy bądź lewy... :)

Autor:  Damian Straszak [ 17 kwi 2011, o 19:11 ]
Tytuł:  Re: [Pawel i Gawel 2] Testy

Damian Dyńdo napisał(a):
@Bartek ja doszedłem do cudownego wniosku rozpisując sporo opcji, że jedynie pożądane ruchy to albo zmniejszyć dany stos do 1 kamienia, albo wyzerować go


Być może nie rozumiem czym są "pożądane ruchy", ale w sytuacji (3,5) jedyny ruch który zapewnia zwycięstwo to (3,3).

Autor:  Paweł Michalak [ 17 kwi 2011, o 19:12 ]
Tytuł:  Re: [Pawel i Gawel 2] Testy

No to gramy, jest [2, 5, 3] i zaczynasz robiąc coś innego niż biorąc jeden z trzeciego stosu.

Gra:

[2,5,3] - [2,5,1]
[1,5,1] - ...

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