039 Coins

[•domino]

Aici puteţi discuta despre problema Coins.

[•Figure09]

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...

[•spixie]

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!

[•unholyfrozen]

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

[cristi8]

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.

[•unholyfrozen]

Am calculat tot vectorul la inceput !  
Toate imi ies din timp !  
Poate imi explici cum l-ai calculat mai rapid...
10x

[cristi8]

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

[•unholyfrozen]

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

[cristi8]

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

Cod:

#define n 22
#define getb(nr,pos) ( (nr) & 1<<(pos-1) )
#define set1(nr,pos) ( (nr) |=  (1<<(pos-1)) )
#define set0(nr,pos) ( (nr) &= ~(1<<(pos-1)) )

int a[1<<n];

void init()
{
  int i,conf=0, confmax,pos,conf2;
  memset(a,255, sizeof(a));
  for(i=1;i<=n;i++)
  {
    set1(conf,i);
    a[conf]=1;
    if(i>1)
      a[conf & ~(1<<i-2)]=0;
  }
  confmax=conf;
  for(conf=1;conf < confmax;conf++)
    if(a[conf]==-1)
    {
      conf2=conf;
      pos=1;
      while(getb(conf,pos))
        pos++;
      i=pos;
      while(pos<n)
      {
        set1(conf2,pos);
        i++;
        while(getb(conf,i))
        {
          set0(conf2,i);
          if(a[conf2]==0)
            goto ExitTRUE;
          set1(conf2,i);
          i++;
          if(i>n)
            goto ExitFALSE;
        }
        set0(conf2,pos);
        pos=i;
      }
    ExitFALSE:
      a[conf]=0;
      continue;
    ExitTRUE:
      a[conf]=1;
    }
}

[vladut.forum]

eu n-am inteles doua lucruricare primul patratel liber din stanga lui :O
de exemplu

Cod:

0 1 0 1 1 0 0 0 0 0 00000000
e valida mutarea ultimului unu in patratica in prima patratica libera...
1 1 0 1 0 0 0 0 0 0 0 0000000 

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...

[cristi8]

eu n-am inteles doua lucruricare primul patratel liber din stanga lui :O
de exemplu

Cod:

0 1 0 1 1 0 0 0 0 0 00000000
e valida mutarea ultimului unu in patratica in prima patratica libera...
1 1 0 1 0 0 0 0 0 0 0 0000000 

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:

0 1 0 1 1 0 0 0 0 0 00000000
daca muti ultimul 1, ajungi la:
0 1 1 1 0 0 0 0 0 0 0 0000000 

PS: citeste si posturile precedente.. s-a mai explicat

[vladut.forum]

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...

[cippi]

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 ?  

[•the_godfather]

: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!  
Si ar mai fi un lucru: ce inseamna memoizare?

[•alberte]

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).

[•Marius]

Daca folosesti C++, atunci incearca sa faci citirea datelor in stil C, cu fscanf... Poate o sa iei 100 fara fstream...  

[•alberte]

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...

[•wefgef]

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.

[andreit1]

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).

[•devilkind]

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.

[•Marius]

Citeste putin despre functia Sprague - Grundy! Te va lamuri imediat! 

[•tm_radu]

Pe testul :

Cod:

10
1 1 0 0 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 1 0
0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 0 1
1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0
1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 0 1 0
1 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0
1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0
1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1
0 1 0 0 1 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 0 1
1 0 1 0 1 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 1

raspunsul este 90?

[•gabitzish1]

Mie imi da 111.

[•Pepelea_Flaviu]

secundul joaca intotdeauna optim

Primul nu joaca optim si el ?

[•sima_cotizo]

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.