|
Titlul: 039 Coins Scris de: Mircea Pasoi din Noiembrie 18, 2004, 00:28:46 Aici puteţi discuta despre problema Coins (http://infoarena.ro/problema/coins).
Titlul: 039 Coins Scris de: Andrei G�nczi in C++ :D din Februarie 24, 2005, 21:21:42 care e faza cu problema asta??? adik... sunt o groaza care au (printre care shi eu) 10 puncte... doar primul test.. shi nu pot sa intzeleg de ce... daca poate cineva sa ma ajute.. pur shi simplu aflu numarul de mutari pana cand toate coin-urile ajung pe pozitiile 1,2,3... shi vad daca numarul lor e par sau impar... care e faza?? am facut pana shi pe numere mari, ca sa fiu sigur, shi tot doar primul test il iau... help plz...
Titlul: 039 Coins Scris de: marius gherman din Februarie 24, 2005, 21:33:43 faza e ca trebuie sa fii atent la enunt..! zice : "O mutare consta din alegerea unui galben si deplasarea sa in primul patratel liber din stanga sa" Primul patratel liber nue neaparat primul patratel din stanga valorii alese, adica pot alege un 1 si sa sar cu el peste alti 5 de unu ex: 0 1 1 1 1 1 1 ..... ultimul 1 ajunge primul intr-o singura mutare...
De asta exista si conditia ca secundul sa joace optim cel putin asa cred eu! Titlul: 039 Coins Scris de: Costea Andrei din Martie 21, 2005, 17:08:48 Ok...
Am si eu o intrebare : solutia mea determina pur si simplu care jucator castiga pentru o configuratie data recursiv. Am incercat 2 cazuri : cand gasesc o solutie care ii convine primului jucator, ma opresc din alte cautari, al doilea : nu ma opresc pt ca toate configuratiile le retin intr-un vector de vreo 2^22 elemente si cand n este destul de mare unele configuratii se repeta. Va rog spuneti-mi daca exista alta solutie (totusi 3 sec timpul) sau daca trebuie sa mai optimizez ca sa imi mearga si ultimele 3 teste. 10x Titlul: 039 Coins Scris de: cristi8 din Martie 21, 2005, 17:21:49 eu am facut cu un vector mare (toate configuratile) de 1 sau 0.. daca configuratia respectiva e castigatoare pt cel care incepe. daca faceam cu memoizare iesea din timp la un test parca, dar daca calculam la inceput tot vectorul si dupa aia doar dadeam raspunsul, mi-a intrat in timp.
Titlul: 039 Coins Scris de: Costea Andrei din Martie 21, 2005, 18:07:14 Am calculat tot vectorul la inceput ! :)
Toate imi ies din timp ! :? Poate imi explici cum l-ai calculat mai rapid... 10x Titlul: 039 Coins Scris de: cristi8 din Martie 21, 2005, 19:26:12 in primul rand, am facut castigatoare toate configuratiile de genu:
00000001 00000011 00000111 00001111 00011111 ... , si pierzatoare alea de genu (cred ca intra in timp si fara astea) : 00000010 00000101 00001011 00010111 ... dupa aia am luat fiecare configuratie in parte pt care nu stiam daca e castigatoare sau pierzatoare, si am verificat daca se poate ajunge intr-o conf. pierzatoare, caz in care marcam a[conf]=1 si treceam la urmatoarea. daca nu gaseam nici o conf. pierzatoare in care se poate ajunge, a[conf]=0; e destul de clar ? vrei sa postez si cod (daca nu se supara nimeni) ? PS: am retinut bitii in ordine inversa Titlul: 039 Coins Scris de: Costea Andrei din Martie 21, 2005, 19:47:26 Pai asa il construiesc si eu!
numai ca pt a completa tot vectorul e suficient sa calculezi numai pt 22 de configuratii(fara sa te opresti cand ai gasit o configuratie care itzi convine) 00000000000001 00000000000011 00000000000111 .. 11111111111111 acestea luate ca in exemplu daca ai facut recursiv posteaza putzin functia pls Titlul: 039 Coins Scris de: cristi8 din Martie 21, 2005, 19:53:19 sper ca e destul de clara, ...ca am scris-o in graba, am incercat mai multe variante (memoizare, etc).. si am ajuns la functia asta care contine si goto :D
Cod:
Titlul: 039 Coins Scris de: vladut.forum din August 05, 2005, 16:16:32 eu n-am inteles doua lucruricare primul patratel liber din stanga lui :O
de exemplu Cod:
asta o fii ca daca o luam asa 0 de pe pozitia 1, este primul zero care apare, si in plus apare si primu in stanga... si ce inseamna ca Secundu muta optim... daca fac recursiv ii simulez cum joaca, cum ar trebuii sa tin cont de mutare valida si se considera ca primul castiga banii, daca dupa toate tipurile de mutari facute recursiv nu pierde nicioadata, o fii asta... Titlul: 039 Coins Scris de: cristi8 din August 05, 2005, 18:32:20 Citat din mesajul lui: vladut.forum eu n-am inteles doua lucruricare primul patratel liber din stanga lui :O de exemplu Cod:
asta o fii ca daca o luam asa 0 de pe pozitia 1, este primul zero care apare, si in plus apare si primu in stanga... pai "primul patratel liber din stanga lui" inseamna ca de la pozitia 1-lui te duci o patratica in stanga, daca e libera, ESTE POSIBIL sa-l muti acolo. daca nu e libera, te mai duci o patratica in stanga si vezi daca e libera. si tot asa. adica daca alegi un 1, ai cel mult o mutare posibila (nu ai nici una doar daca in stanga lui sunt numai 1). Cod:
PS: citeste si posturile precedente.. s-a mai explicat Titlul: 039 Coins Scris de: vladut.forum din August 05, 2005, 19:28:39 ok, m-am mai lamurit, acum fac asa, fac recusiv, toate posibilitatile de mutare, adica cum se poate juca meciu in cate feluri....
asa si de fiecare data cand castiga Paftenie, numar...cand castiga S, numar.. la urma daca winsP>=winsS ii dau banii pt tabla aia, si iau numa 30, hai ca ma mai uit prin cod, sa vad daca am gresit pe undeva... Titlul: 039 Coins Scris de: cippi din Septembrie 04, 2005, 15:23:15 Imi iau 80 orice as face...imi da WA la ultimele 2 teste...
E ciudat ce au alea special si primele 8 nu au... aveti vreo idee ce ar putea fi ? se supara cineva daca postez codul ? (are 53 linii parca..) sau se uita cineva ? :D Titlul: 039 Coins Scris de: Iacob Ioan Fanica din Februarie 18, 2006, 16:47:25 :cry: Am si eu niste intrebari.
Stau de doua zile la problema asta si am luat numa 30 de puncte. Eu iau fiecare joc si simulez toate posibilaitatile de a juca si in functie de cine castiga am doua variabile pt fiecare jucator pe care le cresc. Daca nr de castiguri pt Paftenie e mai mare sau egal cu cel al secundului ii dau banii. Am luat cateva teste pe care am calculat si imi da, dar evaluatorul imi da WA. Tin cont si de faptul ca un unu poate trece si peste altii. Imi mai da si mie cineva vreo indicatie sau vreo doua teste mai mari si reziltatu sa vad daca imi da corect. Nu teste oficiale. Daca se poate si un test oficial mia-r fi de folos sa vad ce am gresit(testul 4 sau 5). Multumes anticipat! :oops: :oops: Si ar mai fi un lucru: ce inseamna memoizare? Titlul: 039 Coins Scris de: Machu Picchu din Februarie 22, 2006, 18:12:51 Am facut un program cu preprocesare care nu vrea sa-mi intre in timp. Pe computerul meu (P4 2,4 GHz Win XP) imi face in 3 secunde preprocesarea si in 3 sec citirea datelor (pentru 100000 de jocuri)- cronometrate separat, pur si simplu nu se incadreza in timp.
Stie cineva ce ar trebui sa fac ca sa mi se incadreze? (repet: simpla citire a datelor dureaza 3 sec). Titlul: 039 Coins Scris de: Marius Stroe din Februarie 22, 2006, 19:39:39 Daca folosesti C++, atunci incearca sa faci citirea datelor in stil C, cu fscanf... Poate o sa iei 100 fara fstream... :)
Titlul: 039 Coins Scris de: Machu Picchu din Februarie 22, 2006, 19:51:17 Eu lucrez in pascal (Este mai incet?), cred ca o sa incerc si o solutie in c cu scanf, daca asta e singura solutie sa-mi intre in timp...
Titlul: 039 Coins Scris de: Andrei Grigorean din Februarie 22, 2006, 22:24:33 si eu am avut probleme cu incadrarea in timp, insa nu din cauza ca foloseam pascal.
eu nu faceam preprocesarea aia ca lumea. gandeste-te daca nu ai putea sa imbunatatesti ceva la ea. ;) Titlul: 039 Coins Scris de: andreit1 din Februarie 24, 2006, 21:50:42 Alberte stai linistit ca intra si in pascal( 1.5 secunde in cel mai rau caz). Foloseste operatori pe biti ca sa imbunatatesti constanta( sau poate chiar complexitatea).
Titlul: Raspuns: 039 Coins Scris de: Savin Tiberiu din August 09, 2006, 18:32:24 faptul ca secundul joaca optim inseamna ca dak exista cel putin o posibilitate ca secundul sa castige atunci acesta va castiga?? sau numarul de posibilitati ca paftenie sa castige tre sa fie mai mic decat cele ale secundului ptr ca cel din urma sa castige??
PS: iau 10 pt si nu inteleg, teoretic dak secundul joaca optim atunci dak exista cel putin o posibilitate ca acesta sa castige atunci el va castiga. Titlul: Raspuns: 039 Coins Scris de: Marius Stroe din August 10, 2006, 12:17:35 Citeste putin despre functia Sprague - Grundy! Te va lamuri imediat! :)
Titlul: Răspuns: 039 Coins Scris de: Toma Radu din Martie 25, 2008, 20:50:06 Pe testul :
Cod: 10 raspunsul este 90? Titlul: Răspuns: 039 Coins Scris de: Gabriel Bitis din Martie 25, 2008, 20:53:48 Mie imi da 111.
Titlul: Răspuns: 039 Coins Scris de: Flaviu Pepelea din Decembrie 23, 2008, 11:45:08 Citat secundul joaca intotdeauna optim Primul nu joaca optim si el ?Titlul: Răspuns: 039 Coins Scris de: Sima Cotizo din Decembrie 23, 2008, 13:08:18 Daca intrebarea nu era o glumita, atunci gandeste-te ca primul esti tu si vrei sa castigi. Daca nu joci optim, exista posibilitatea sa nu castigi.
Titlul: Răspuns: 039 Coins Scris de: Chirac Cristian din Martie 12, 2009, 12:57:35 de curiozitate...ce gresesc, ca mie imi da bine cand probez, dar iau 0 puncte la evaluatorul de aici...
Cod: #include<fstream.h> [editat] foloseste tag-ul "code" cand postezi cod pe forum Titlul: Răspuns: 039 Coins Scris de: Cristi din Iunie 30, 2009, 13:22:38 da' la un joc ......trebuie parcurse toate posibilitatile de joc.....?? adica daca ai 1000111..... se poate 1001110 sau 100101 si altele...asa?
Titlul: Răspuns: 039 Coins Scris de: Antoche Ioana Alexandra din Septembrie 02, 2009, 17:28:50 Daca iau toate nr de la 2^22 pana la 1 si stabilesc ca toate conviguratiile care incep cu 1 si au o singura secventa de 1 (1111...10...000) sunt castigatoare, atunci stiu ca orice mutare as face voi obtine un numar mai mare decat cel actual. Deci stiu despre numarul actual daca e sau nu castigator. Pentru fiecare nr tin intr-un vector pentru cantig true dak se poate castiga si false altfel; la fel pentru pierdut. Astfel stiu pt orice numar daca pierd sau castig!
Pe ideea asta iau 30 pct cu restul WA ](*,) ! Are cineva vreo sugestie? Multumesc anticipat! Titlul: Răspuns: 039 Coins Scris de: Halalai Tudor Andrei din Martie 17, 2010, 18:38:23 QS(question):Dc va chinuiti atata...totusi....
daca pe tabla inaintea ultimului (1) se afla nr impar de (0) atunci castiga secundul.... altfel castiga capatanul... cred eu... also... stiind nr de 0 atunci stim si cine castiga... ASTA CRED EU. AM DREPT DE COPYRIGHT... :D ....accept ca acest mesaj sa fie stres daca nu convine regulilior pe care nu le-am citit ale acustui site(doar le-am bifat)...Titlul: Răspuns: 039 Coins Scris de: Mihai Calancea din Martie 17, 2010, 19:24:10 ....accept ca acest mesaj sa fie stres daca nu convine regulilior pe care nu le-am citit ale acustui site(doar le-am bifat)... Stai linistit , 'regulile pe care nu le-ai citit ale acustui site ' nu au nimic impotriva postarii de solutii gresite pe forum. Desigur , e putin comic cand postarea are tonul asta. Mai ales ca aceasta idee a fost desfiintata in primele 2 posturi. Citeste-le , poate scoti o solutie demna de sters :D Titlul: Răspuns: 039 Coins Scris de: Halalai Tudor Andrei din Martie 17, 2010, 19:37:31 ok :fool: poate ai dreptate...da' am o intrebare...
care-i raspunul corect la testul de mai sus(cam pe la inceputul paginii)? 111,90 sau(cum mi-a da mie) 75 si facut manual 72 :-k Titlul: Răspuns: 039 Coins Scris de: Mihai Calancea din Martie 17, 2010, 19:41:44 111
Titlul: Răspuns: 039 Coins Scris de: Halalai Tudor Andrei din Martie 18, 2010, 19:42:06 ....apropos ce inseamna a juca optim?
si ex:000011(pe care unii l-au notat "castigator") nu castiga secundul? I 100010-capitan II 110000-secund sau nu? HELP ME PLS Titlul: Răspuns: 039 Coins Scris de: Mihai Calancea din Martie 18, 2010, 19:53:39 Optim inseamna ca daca unul din jucatori are o strategie sigura de castig , o va folosi.
Ai voie sa muti un 1 in cel mai apropiat 0 din stanga , nu oricare 0 din stanga. N-am stat sa verific daca respectiva configuratie e castigatoare .Cred ca se refereau la cazurile triviale , dar tin configuratiile oglindite in implementare : 110000 e caz trivial. Si mai usor cu efectele speciale. Titlul: Răspuns: 039 Coins Scris de: Halalai Tudor Andrei din Martie 19, 2010, 17:01:43 THANK U! cred ca-mi pierd mintile!!! :rotfl: :rotfl: :fool: :PL. E.: am inteles ca trebuie sa fie mutat in primul 0 din stanga :harhar: Editat de admin: Nu mai posta consecutiv, editeaza-ti mesajele anterioare/ Titlul: Răspuns: 039 Coins Scris de: Prisacariu Alexandru din Aprilie 27, 2013, 15:33:27 Din cate s-au scris aici inseamna ca exemplul e gresit:
Citat 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 este castigat tot de capitan deoarece el incepe primul deci va muta unule de pozitia 2 pe pozitia 1 si va fi castigator.Titlul: Răspuns: 039 Coins Scris de: mihai craciun din Decembrie 31, 2016, 00:44:03 In exemplu, de ce Paftenie nu castiga si jocurile 2 si 4?
|