012 Pietre

[•k_ounu_eddy]

Am observat cateva configuratii,care daca se ajunge castiga urmatorul la rand.de ex daca acum muta Macarie,si daca are una din configuratiile 1 2,3 5,4 7,6 10(care este 3*2 5*2),7 4(care este inversul lui 4 7),8 14(care este 4*2 7*2),9  15(care este 3*3 5*3),10 6(care este inversul lui 6 10),rezulta ca persoana castigatoare este Petronela.Am mai observat ca sunt configuratii de baza,de la care se poate ajunge la alte configuratii.De ex 3, 5(prima multime este 3 ,a doua 3*2-1),4 7(prima multime este 4 a doua 4*2-1).
Deci perechea in care castiga Petronela se obtine fie prin regula n n*2-1,ori daca a mai fost utilizata invers.Dar pentru perechea 11 18(am luat din matricea postata de Chris) nu se poate aplica regula care am observat-o(ar fi trebuit sa fie 11 21).
Cineva a zis sa ma uit la modul in care sunt dispusi 2 in functie de randul trecut,dar nu am reusit sa obtin nici o regula.
Dati-mi o sugestie va rog.

[•devilkind]

te sfatuiesc sa cauti la .campion nu mai stiu exact la ce runda s-a dat problema tz (acolo iti cerea si programarea miscarilor), citeste acolo descrierea solutiei si vei intelege mai bine. De altfel problema se gaseste in mai toate cartile cu jocuri cu gramezi de pietre e cam clasica /

[•k_ounu_eddy]

Pai am cautat pe site,dar problemele care s-au dat raman in vreo arhiva ceva.Nu gasesc de unde sa downloadez.As fi foarte recunoscator daca mi-ai da un link.

[•C_Ovidiu]

    http://campion.edu.ro/problems.php?mode=view_round&group_number=2&year=2006&round_number=3#
 Nu cauta regula, cauta sa intelegi problema si regula o gasesti dupaia. 

[•k_ounu_eddy]

Mersi.Am inteles problema in cele din urma,dar daca eram la olimpiada si primeam problema asta ,nici prin gand nu imi trecea sa folosesc reprezentarea unui nr in sistemul de numeratie Fibonacci(de care nici nu stiam pana acum).La ce clasa s-a dat problema asta?

[•k_ounu_eddy]

Am reusit sa il fac,dar evaluatorul mi-a zis sistem error,asa ca am postat pe forum Id-ul jobului:job #17759(ce eroare e asta?,ca am inteles ca e grava).
Solutia mea e cam asa:mai intai am generat sirul fibonacci pana la al 40lea termen.Apoi,am am luat fiecare pereche de numere(multimi),si daca erau diferite,am determinat minimul,l-am convertit in baza fibonacci,iam adaugat un zero,lam convertit in nou in baza 10,astfel determinandu-i perechea pt care castiga 2.De acum e usor.Nu stiu daca mi se incadreaza in timp.Sper.Stiti alta solutie mai buna(optimizata)?

[•domino]

Am reusit sa il fac,dar evaluatorul mi-a zis sistem error,asa ca am postat pe forum Id-ul jobului:job #17759(ce eroare e asta?,ca am inteles ca e grava).
Solutia mea e cam asa:mai intai am generat sirul fibonacci pana la al 40lea termen.Apoi,am am luat fiecare pereche de numere(multimi),si daca erau diferite,am determinat minimul,l-am convertit in baza fibonacci,iam adaugat un zero,lam convertit in nou in baza 10,astfel determinandu-i perechea pt care castiga 2.De acum e usor.Nu stiu daca mi se incadreaza in timp.Sper.Stiti alta solutie mai buna(optimizata)?

Ar trebui sa citesti si din fisierul care trebuie...

[•k_ounu_eddy]

Te-ai uitat peste solutia mea?Pai nu e bun pietre.in,pietre.out?

[•domino]

Te-ai uitat peste solutia mea?Pai nu e bun pietre.in,pietre.out?

In job-ul 17759 in care ai luat system error citesti si scrii in cifra.in/.out.

[•k_ounu_eddy]

Mersi,era din cauza compilatorului(Borland C++ 5.01),care nush de ce imi salveaza si programul anterior la care am lucrat(fiind problema cifra).

[•k_ounu_eddy]

Am luat si eu in sfarsit 100 de puncte.Prima data am luat doar 50 de puncte,dar am rescris sursa ,si acum iau 100.Totusi ma mai intereseaza un lucru.Stiti cumva cum se poate demonstra matematic ca in cazul in care este o perche distincta n baza fibonacci,Petronela are strategie sigura de castig?

[•C_Ovidiu]

   E mai greu sa demonstrezi matematic asa ceva . Eu inteleg logic de ce e asa dar e cam greu de povestit.  Oricum, la problema de aici nu trebuie sa stii nimic de fibonacci . Retii intr-un vector doar perechea 2 1 (si evident 1 2 ) ca strategii nesigure , si la fiecare noua pozitie vezi daca poti reduce perechea ta de pietre la o strategie nesigura de castig, prin operatiile permise . Daca poti , strategia ta e sigura de castig . Altfel e nesigura si o adaugi in vector . 

[•k_ounu_eddy]

Stai putin ca nu am inteles intru totul.In primul rand de ce perechea 2,1,respectiv 1,2 e nesigura de castig,deoarece stiu sigur ca va castiga urmatorul la rand.De ex daca acum muta Macarie ,si in fata lui sunt multimile de pietre 1,2 => castiga Petronela.

si la fiecare noua pozitie vezi daca poti reduce perechea ta de pietre la o strategie nesigura de castig, prin operatiile permise

Ai zis la o strategie nesigura de castig.Te refereai la 1,2 sau la 2,1(mai sunt si altele?ca din textul tau reiese ca sunt doar astea 2).
Mai explica odata ce ai vrut sa spui,pls.

[•pocaitu]

Deci
 Spunem ca perechea (a,b) e castigatoare daca cel care muta primul castiga la sigur (evident, cu o strategie optima). Altfel spunem ca ea este necastigatoare.
  Observi ca perechea (1 2) e prima necastigatoare.
  Iei toate perechile la rand si vezi daca pot fi reduse la o pereche necastigatoare(prin mutarile permise). Daca poti , perechea e castigatoare: o  lasi in pace . Daca nu poti , e necastigatoare . O adaugi in multimea perechilor necastigatoare. 
 
Exemplu
perechea (1,2) e necastigatoare => toate perechile (1,m) cu m>2 sunt castigatoare (si inversele lor)
perechea (3,5) e si ea necastigatoare pt ca orice mutari ai face nu o poti reduce la una necastigatoare
de acum trebuie sa vezi daca poti reduce perechea (a,b) la (1,2) sau la (3,5)
 Si tot asa.
Dupa ce intelegi algoritmul , se observa niste simetrii . Poti lua prima pereche necastigoare ca fiind (0 0)

[•k_ounu_eddy]

Am inteles pana la urma.Mersi de idee.

[•kyrk]

am shi eu o problema, cand trimit sursa iau doar 55 pct...OKAY..shi la restul testelor    Killed by signal 11(SIGSEGV). Sunt sigur ca am declarat suficienta memoria...am creat un vector..dupa o anumita regula...care poate avea maxim 1 mil elem..deci a[1000000]. Mah poate ajuta cineva ? (mah gasitzi shi pe ym : kyrk_dd )
Job Link : http://infoarena.ro/job_detail/27911

[•y2k]

Pai se poate sa fii folosit indici negativi pentru vector din greseala

[•kyrk]

nope..nu am folosit...daca va putetzi uita cumva peste sursa..datzi-mi shi mie un add pe id de mai sus...chiar nu shtiu ce se poate intampla]

Later Edit :Am rezolvat nu mai este nevoie

[•razyelx]

deci eu am gasit o chestie:
presupunem cazul 3 5:
1)3-0, 5-3
2)3-1,2-1
3)2-1,1-1
4)1-1,0 adik Petronela castiga asa si trebuie.
dar sa vedem cazul asta
1)3,5-1
2)3-1,4-1
3)2,3-2
4)2-1,1-1
5)1-1,0 adik Macarie castiga am inteles eu cresit? pls ajutati-ma si pe mine 

[•devilkind]

ambi jucatori joaca optim, uite pe exemplul tau.
din 3 5 sa zicem ca macarie muta si ajunge in 3 4. atunci petronela ia 2 din ambele grupe si ajunge in 1 2, de aici macarie orice mutare face va pierde.

[•razyelx]

ms mult... 

[•peanutz]

Vreau sa rezolv problema dinamic, dar numarul de pietre poate fii destul de mare. Intrebarea mea este daca intra in timp daca folosesc o matrice rara(retin doar indicii i si j unde am solutie true)?... Si, eventual, daca aveti indoieli ca s-ar incadra asa in timp, sa-mi ziceti o alta modalitate de a rezolva problema memoriei. (Cu mentiunea ca am gasit recurenta deja pentru matrice normala). Multumesc

Later edit: Yep, sunt destul de convins ca intra acum, multumesc oricum.

[•razyelx]

Deci  ... serios am incercat cu 10 6, cu 5 3, 2 1, 2 3, 4 7 si toate imi ies bine. Lucru haios e ca daca il dau la evaluat iau 5 pct... iar daca zic nu incerc sa aduc jocul in pozitia 1 2 prim metode acceptate atunci iau 40 de pct. Va rog sa imi dati alte exemple care ar putea sa imi dea peste cap algoritmul si la mine pe pc...   

[•fireatmyself]

pietre.in

Cod:

20
16 26
15 43
17 28
19 31
20 20
21 34
22 36
26 23
27 15
24 39
25 41
27 44
30 69
29 47
30 49
32 52
33 54
35 57
37 60
38 62

pietre.out

Cod:

2
1
2
2
1
2
2
1
1
2
2
2
1
2
2
2
2
2
2
2

sper sa fie cu folos

[•razyelx]

Dupa cateva sfaturi am reusit sa imi formulez si eu o idee in cap. Deci cei doi joaca optim. Presupunem ca (a,b) e diferit de (1,2) sau inversa. Macarie face prima mutare. El doreste ca pe durata concursului sa ajunga la o mutare de tip (1,2) sau inversa. Si de ce m-am gandit asa. El incepand primul are tot timpul nr mutarii impar, iar ca la final nr sa fie tot impar are nevoie de o combinatie care sa il faca castigtor intr-un nr impar de pasi(impar+par=impar). La fel cu petronela nu prea mare filosofie. Atunci presupunem ca avel multimile 15 43.
pasul 0 - 15 43
pasul 1 -  3  43
pasul 2 -  3   5
pasul 3 -  2   4
pasul 4 -  1   3
pasul 5 -  1   2
pasul 6 -  1   1
pasul 7 -  0   0
Cam acesta ar fi jocul pentru multimea aceasta. Daca la pasul 2 petronela ia din multimea 1 pietre sau din multimea 2 pietre nu schimba cu nimic jocul.
De ce am evaluat asa jocul? presupun ca Macarie joaca destul de smecher. El doreste sa ajunga la multimea (1,2) respectiv inversa dar nu o poate face din prima mutare deoarece i-ar lasa pozitie de castig Petronelei. Deci prima miscare a lui Macare trebuie sa lase o multimile A si B diferite de 1 sau 2. Iar cel mai mic care ii poate duce o pozitie nesigura este 3. daca el face ca in oricare multime sa apara 3 petronela nu are sanse de castig. Aceasta regula nu include cazurile in care multimea la pasul 0 este (3,x) sau inversa
E corect? Daca nu de ce? Da-ti-mi si un contra exemplu.