012 Pietre

[•fluffy]

Aici puteţi discuta despre problema Pietre.

[•fireatmyself]

de ce dracu' nu-mi mere testu 1?

[•dinu]

Toate testele, in afara de 1, au raspuns numai 1. Nu ai strategie de castig decat in cateva cazuri simple. Un program de 10 lini iti aduce 95 de puncte si unul de 35, 100 de puncte

[•fireatmyself]

ma rog, aici ai dreptate... :lol:

[•thestick]

problema asta e cam aiurea!!!! mai ales din cauza ca am luat numa 95 de puncte! si testele sunt aiurea la fel!!!

[•dobre]

Mai sunt ceva cazuri particulare:
n n->1
n n+1->1 |n>1
1 n ->1    |n>2
0 n ->1
1 2 ->2

Siguri nu ati verificat una dintre conditiile astea...
Am luat 5 p pe problema si merge doar primul test  :lol:

[•calinux]

Eu am incercat sa fac tot asa-> tinand cont de cazurile limitate de castig pentru Petronela (biata de ea  :lol: ), am incercat sa vad doar cand datele de intrare sunt favorabile ei, iar daca nu  afisez 1. Dar.... desi am tratat cazul 1 2 ( si 2 1 ) nu am reusit 100p. Daca ati putea sa-mi dati un indiciu....

[•dobre]

Eu nu mi-am batut prea mult capul la problema asta dar, dintre toate testele imi iese doar testul 1, deci probabil este una din conditiile care le-am pus eu mai sus...Nu ai scapat una din situaii?
...

[•calinux]

Pai... in primul rand conditiile exprima urmatoarea chestie:
1 2 sau 2 1 -> castiga Petronela
Restu -> castiga Macarie
P.S.: Conform cerintei nu o sa existe un a = 0, deci conditia 0 n este inutila  

Oricum, am incercat sa implementez cu conditiile de mai sus, avand si grija sa verific si 1 n si n 1 la toate, dar am luat 0 p.  :cry:  Poate ai copiat ceva gresit. Daca ai putea sa te mai uiti o data ar fi super.  

[u-92]

pai nu sunt decat 2 cazuri cand castiga petronela (4 cu tot cu inversele).. in rest 1 .. asa am facut eu si am luat 100

[•bogdan2412]

De fapt (daca solutia mea e buna) exista o infinitate de cazuri in care castiga Petronela. Pentru fiecare numar de pietre dintr-o gramada ii corespunde un alt numar de pietre din cealalta gramada (nu spun cum se determina ) astfel incat Petronela sa castige. De aceea daca numarul a nu este perechea lui b Macarie castiga, el putand lua pietre din una dintre gramezi astfel incat sa se ajunga la o pozitie de castig pentru el.

[•dobre]

Uite aici codul meu... Pentru 5 puncte , intradevar ce am scris eu in urma nu era suficient, am implementat din nou program-ul  pt. ca il pierdusem...
Merge pentru test-ul 1...

Cod:

program pietre;
var f,g:text;
    i,t,A,B:integer;

procedure calcul;
var q:longint;
begin
assign(g,'pietre.in');reset(g);
assign(f,'pietre.out');rewrite(f);
readln(g,t);
for i:=1 to t do
    begin
     readln(g,A,B);
     if a>b then begin
         a:=a+b;b:=a-b;a:=a-b;
        end;
     if(a=1)and(b>2) then writeln(f,'1')
        else if(a=1)and(b=2) then writeln(f,'2');
     if(a=b)or(a=2) then writeln(f,'1')
     else
     if((a=b-1)and(a>1))or(a=0) then writeln(f,'1')
         else if a>2 then begin
           q:=a-3;b:=b-q;
           if((b-a)mod 2=0)and(b>a) then  writeln(f,'2')
              else writeln(f,'1');
         end;
    end;
close(g);close(f);
end;
begin
calcul;
end.

[•bogdan2412]

Pentru 6 10 programul tau afiseaza 1, dar el ar trebui sa afiseze 2.
Ai pozitiile castigatoare pt Petronela deja determinate: 0 n;1 2; 3 5; 4 7 si inversele (verifica daca vrei).
Daca Macarie ia la prima mutare din gramada de 6, Petronela ia din gramada de 10 cate pietre sunt necesare pentru al aduce pe Macarie intr-o pozitie de pierdere ( pt toate nr mai mici ca 6 exista o pozitie castigatoare pt Petronela printre cele date mai sus ). Daca Macarie ia din gramada de 10, atunci numarul de pietre din gramezi va fi de forma: 6 6+x, x<=3 sau 6 6-x;x<=6. In primul caz Petronela va lua din ambele gramezi numarul necesar de pietre ( pt 6 9 -> 4 7; pt 6 8 ->3 5; pt 6 7 -> 1 2; pt 6 6-> 0 0). In al doilea caz gramada a doua va contine un numar de pietre din multimea: 1, 2, 3, 4, 5, dar deja avem determinate perechi castigatoare pt aceste numere. Daca Macarie ia din ambele gramezi => in gramada care avea 6 va exista un numar de pietre < 6 => Petronela va putea lua din gramada care avea 10 pietre pentru a-l aduce pe Macarie in pozitie de pierdere.

Sper ca ai inteles

[•Cosmin]

E tagul "[code]" care il poti folosi pentru ca programul sa ramana indentat, oricum nu e prea frumos sa dai cod la depanat pe forum.

[Chris]

Eu sunt de acord cu bogdan. Sunt mai mult de 4 cazuri in care Petronela poate castiga. Eu am rezolvat problema dupa ce am facut o dinamica de O(numar_pietre^3+numar_teste) si apoi folosind cateva observatii am optimizat-o sa mearga in O(max_pietre + numar_teste).
Aici am pus o matrice generata pentru cazurile pana la 20x20 (pentru cei care nu ma cred   )- sunt mai mult de 4 cazuri in care castiga Petronela - de fapt pentru fiecare gramada cu A pietre exista o singura gramada cu B pietre astfel incat Petronela sa castige :

Cod:

*  12345678901234567890
01 12111111111111111111
02 21111111111111111111
03 11112111111111111111
04 11111121111111111111
05 11211111111111111111
06 11111111121111111111
07 11121111111111111111
08 11111111111121111111
09 11111111111111211111
10 11111211111111111111
11 11111111111111111211
12 11111111111111111112
13 11111112111111111111
14 11111111111111111111
15 11111111211111111111
16 11111111111111111111
17 11111111111111111111
18 11111111112111111111
19 11111111111111111111
20 11111111111211111111

  Va sfatuiesc sa nu mai pierdeti timpul cautand cazuri particulare ci sa incercati o solutie mai inteligenta.
P.S.: Sper ca e corecta matricea (am rezolvat cu ceva timp in urma problema!)

[•dobre]

Am pus cod-ul care merge pentru test-ul 1,pentru ca  m-am gandit ca  cineva si-ar putea da seama daca scapa o situatie...Majoritatea au WA testul 1.

[•calinux]

Gata.Am reusit.   Am facut tot cu nr. max de pietre+nr de teste. Mersi de ajutor.

[•Dark_Raxvan]

O constatare a mea este k in aproape toate cazurile castiga primul.

[•thestick]

bah...macar ai citit ce au scris altii inaintea ta inainte sa spui ca

Acuma sa explic putin celor care nu pot sa inteleaga aceasta problema.
Daca cumva cititi cu atentzie problema realizatzi k in 95 % din cazuri castiga primul.

Nu cred!

[•danburzo]

95 puncte :cry: testul 2 WA.

[•LucAnd]

lol nu imi vine sa cred cat de usoara era solutia , ma asteptam la o solutie de complexitate covarsitoare, pur si simplu iei matricea cu solutii de mai sus si ai sirul x i= j pentru care castiga 2 , observi ca fie acest numar il obtii prin inversarea unei solutii obtinute precedent ,iar celalte au un termen general ( nu spun care de e destul de usor de observat )

[ditzone]

Am modificat niste teste ... Si am reevaluat solutiile... S-au modificat ceva punctaje...
nu e CHIAR asa de usoara

[•devilkind]

eu am ramas cu 100   , oricum formula nu e asha greu de determinat dak te uiti atent pe matricea de mai sus. Succes celor care nu au reushit sa o rezolve ink, shi un hint : uitativa atent la acea matrice (hintul era mai lung insa e prea explicit shi l-am scos).

[•Marius]

uitativa atent la acea matrice shi incercati sa observati felul in care este dispus nr 2 pe fiecare linie in functie de linia precedenta (indici sunt cheia). Sper ca nu e prea explicit.

Eu cred ca ai spus cum se rezolva!

[stelistu]

ma poate ajuta cineva cu prob asta? ma tot chinui si nu-mi iese deloc 

iau 6 de WA.
am facut un vector in care a[ i ]  =j specifica faptul ca pentru perechea de multimi de pietre (i,j), rezultatul este 2.am parcurs toate liniile de la 1 la 10^6.

Cod:

void make()
{int i,j;int max=1000000;
int ady;
 for (y=0,ady=2,i=1;i<=max;i++)
  if (a[i]) ady++;
  else {y+=ady;
  if (y>1000000) break;
  a[i]=y;ady=2;a[y]=i;}
}

Later edit: Mi-a iesit pana la urma...era ceva prost scris mai sus :d