Imprimă pagina - 689 Carti

Titlul: 689 Carti
Scris de: Airinei Adrian din Aprilie 06, 2008, 14:32:00

Aici puteţi discuta despre problema Carti (http://infoarena.ro/problema/carti).

Titlul: Răspuns: 689 Carti
Scris de: Toma Radu din Aprilie 08, 2008, 15:46:45

Exista cazuri particulare la problema asta? Iau doar 80 de puncte si imi da corect pe testele generate de mine. :-k

Titlul: Răspuns: 689 Carti
Scris de: Filip Cristian Buruiana din Aprilie 08, 2008, 17:04:00

S-a reevaluat. 2 teste erau gresite deoarece N nu corespundea cu numarul de carti de pe masa. Ne cerem scuze pentru neplaceri.
Eu cand citeam, citeam cu fgets, pentru mine nu conta N-ul acela, si de aceea acea eroare e trecut neobservata.
Acum iei 100 ;).

Titlul: Răspuns: 689 Carti
Scris de: Toma Radu din Aprilie 08, 2008, 18:04:16

:winner1: Mersi :)

Titlul: Răspuns: 689 Carti
Scris de: Zajzon Barna din Aprilie 20, 2008, 22:59:09

Care-i smecheria? ](*,) :fighting: iau numai 20 de puncte... personal procedez asa la fiecare configuratie: qsort, ca sa fie in sir, dupa care iau un vector 'seged' cu toate elementele=0; un for pana la m, si pentru fiecare numar dau 1, sau seged[ i ]+=i-1 daca seged[ i ]<k, dupa care seged[i-1]=0; in final numar numerele nenule, si daca %2==0 castiga bob ... Este ceva in neregula cu ideea? (poate nu am inteles bine problema ](*,)

Cod:

   1. #include<fstream>  
   2. #include<cstdlib>  
   3. using namespace std;  
   4. ifstream be ("carti.in");  
   5. ofstream ki ("carti.out");  
   6. typedef struct  
   7.  {  
   8.   int kk, mm;  
   9.  } S;  
  10. S c[15];  
  11.   
  12. int compare (const void*a,const void*b)  
  13.     {  
  14.      return (*(int*)a-*(int*)b);  
  15.     }  
  16. int a[15][15];  
  17. int main()  
  18.     {  
  19.      int m,k,n,i,j,s,SZ,seged[15];  
  20.      char x;  
  21.      be>>n;  
  22.      for (i=0;i<n;i++)  
  23.     {  
  24.      be>>m>>k;  
  25.      c[i].kk=k; c[i].mm=m;  
  26.      for (j=0;j<m;j++)  
  27.        {  
  28.     be>>x;  
  29.     if (x>='A')  
  30.       {  
  31.        switch (x)  
  32.          {  
  33.           case 'A': { a[i][j]=1;break; }  
  34.           case 'J': { a[i][j]=11; break; }  
  35.           case 'Q': { a[i][j]=12; break; }  
  36.           case 'K': { a[i][j]=13; break; }  
  37.          }  
  38.       }  
  39.     else  
  40.       if (x=='1')  
  41.         {a[i][j]=10; be>>x;}  
  42.       else  
  43.         a[i][j]=x-48;  
  44.        }  
  45.     }  
  46.      be.close();  
  47.      for (i=0;i<n;i++)  
  48.        {  
  49.     m=c[i].mm; k=c[i].kk;  
  50.     qsort(a[i],m,sizeof(int),compare);  
  51.     SZ=0;  
  52.     for (j=0;j<15;j++)  
  53.        seged[j]=0;  
  54.     for (j=0;j<m;j++)  
  55.      {  
  56.       seged[a[i][j]]=1;  
  57.       if (seged[a[i][j]-1]<k && seged[a[i][j]-1]>0 && j)  
  58.         {  
  59.           seged[a[i][j]]+=seged[a[i][j]-1];  
  60.          seged[a[i][j]-1]=0;  
  61.         }  
  62.      }  
  63.      for (j=0;j<m;j++)  
  64.          if (seged[a[i][j]]>0)  
  65.            SZ++;  
  66.      if (SZ%2==0)  
  67.       ki<<"Bob";  
  68.      else  
  69.       ki<<"Alice";  
  70.      if (i!=n-1)  
  71.       ki<<"\n";  
  72.     }  
  73.      ki<<"\n";  
  74.      ki.close();  
  75.      return 0;  
  76.    }

ultima parte

eventual un test puteti sa aratati? in afara de primul si 8.

Titlul: Răspuns: 689 Carti
Scris de: Lucian Boca din Aprilie 24, 2008, 11:42:54

Probabil ca scapi din vedere anumite cazuri. Solutia oficiala studiaza toate situatiile posibile de joc si este descrisa aici (http://infoarena.ro/grigore-moisil-2008/solutii#carti).

Titlul: Răspuns: 689 Carti
Scris de: speedzeal din Septembrie 11, 2009, 13:03:34

Ar fi trebuit sa se evidentieze recursitivitatea in solutie si pentru a transforma solutia aceea intr-una valida mai trebuie aduagat ceva cod...e bine ca in solutiile de la concursul de la Grigore Moisil se lasa aprope tot timpul pentru cititor obligatia de a contribui pentru a rezolva problema dar uneori absenta unor informatii poate duce in eroare cititorul... :wink:

Titlul: Răspuns: 689 Carti
Scris de: George Marcus din Martie 14, 2011, 20:24:52

Ce trebuie optimizat pe langa solutia oficiala ca sa intre in timp? Am vazut ca si altii aveau TLE pe aceleasi teste :-k

Titlul: Răspuns: 689 Carti
Scris de: UAIC.VlasCatalin din Decembrie 08, 2012, 21:11:40

Poate sa-mi dea cineva un test pe care sa nu mearga ideea mea:
Daca numarul maxim de carti este k atunci impart cartile in siruri de numere consecutive, apoi fiecare sir il sectionez in blocuri de k numere, dupa aceasta aplic jocul NIM.
Exemplu:
7 2
10 11 1 2 3 8 9
secventele consecutive sunt
1 2 3 si
8 9 10 11
blocurile atunci vor fi
1 2
3
8 9
10 11
respectiv daca fac xor intre numarul de carti din gramezi obtin un numar mai mare ca 0, respectiv Alice cistiga jocul. :?

Titlul: Răspuns: 689 Carti
Scris de: Mihai Calancea din Decembrie 08, 2012, 22:21:02

Un test nu prea am timp sa-ti caut acum, dar e suficient sa realizezi ca NIM-ul descris de tine nu este echivalent cu jocul original.

Presupunem ca ai o gramada de 3 numere : 3 4 5. Sa zicem ca in jocul original iei numarul 4. La tine, s-ar traduce prin faptul ca din gramada cu 3 elemente iti mai raman 2 elemente. Dar asta nu e adevarat, fiindca nu le poti lua impreuna la o eventuala mutare. De fapt tu iei un element din gramada, dupa care o spargi in 2 gramezi de cate un element, iar asta nu respecta regulile NIM-ului.

Titlul: Răspuns: 689 Carti
Scris de: Salajan Razvan din Decembrie 08, 2012, 22:47:57

Uite aici un test pe care pica sursa ta

Cod:

.in: 
1
8 2
2 3 4 5 6 7 8 9

raspunsul e Alice

Titlul: Răspuns: 689 Carti
Scris de: UAIC.VlasCatalin din Decembrie 09, 2012, 15:08:20

Ms mult pentru explicatii si pentru test :ok:
Am facut acum dupa solutia oficiala, dar tot iau incorect pe doua teste, stie cineva care ar fi cauza ?

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Airinei Adrian din Aprilie 06, 2008, 14:32:00