TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

poker.cpp    3,656 b      izvorni kod rešenja
poker2.cpp    2,415 b      izvorni kod rešenja
poker.pas    7,189 b      izvorni kod rešenja
poker.checker.pas    551 b      program za testiranje
poker.tests.rar    1,717 b      test primeri

zadatak: Poker

Biznismen Draganče je odlučio da poveća prihode svog kazina tako što će organizovati poker turnire sa milionskim nagradnim fondom. Zato se obratio svom drugu Đuri, direktoru najgledanije televizije koji se odmah oduševio idejom brojeći nove gledaoce koje će ovaj program doneti. Kada je shvatio koliki je iznos licence za takvu emisiju odlučio je da malo promeni pravila. Međutim ovo im je donelo jedan problem: kako izračunati verovatnoću da određeni igrač pobedi samo na osnovu prve dve podeljene karte, što je najinteresantniji detalj za televizijske gledaoce. Pomozite im da reše ovaj problem.

Pravila njihove verzije televizijskog pokera su sledeća: Igra se sa 32 karte, po 8 (A K Q J 10 9 8 7) od svake od 4 boje (P K H T). Karte poređane po jačini: A K Q J 10 9 8 7. Svakom igraču se na početku podele dve karte, a zatim se na sto stavi još pet karata. Svaki igrač bira pet karata od sledećih sedam: dva iz ruke i pet sa stola, tako da one čine najjaču moguću kombinaciju. Na kraju igrač koji je imao najjaču kombinaciju pobeđuje, a ako su dva ili više igrača izjednačeni onda je rezultat partije nerešen. Kombinacije su poređane po jačini na sledeći način, a dodatne napomene date su u zagradama:

  1. fleš rojal: A,K,Q,J,10 u istoj boji (sve boje su ravnopravne) (primer: PA, PK, PQ, PJ, P10)
  2. boja-kenta: pet karata iste boje poređane po redu (najjača karta odlučuje) (primer: HJ, H10, H9, H8, H7)
  3. poker: četiri karte iste vrste (ako dva igrača imaju poker, pobednik je onaj ko je ima poker sastavljen od karata jače vrste) (primer: PA, KA, HA, TA, T8)
  4. ful: tri karte jedne vrste i dve druge vrste (prvo se gleda jačina tri karte, a onda dve karte) (primer: PK, KK, TK, K7, T7)
  5. boja: pet karata iste boje (najjača karta odlučuje) (primer: PQ, PJ, P10, P8, P7)
  6. kenta: pet karata poređane po redu (najjača karta odlučuje) (primer: TQ, HJ, T10, H9, K8)
  7. triling: tri karte iste vrste (ako dva igrača imaju triling, pobeđuje onaj koji ima triling od karata jače vrste) (primer: P10, K10, T10, K7, T9)
  8. dva para: dve karte jedne vrste i dve karte druge vrste (prvo se gleda jači, pa slabiji par) (primer: HA, TA, T8, P8, PJ)
  9. jedan par: dve karte iste vrste (ako dva igrača imaju po jedan par, pobednik je onaj koji ima par od jačih karata) (primer: T8, P8, K7, TQ, HA)

Napomena:

Verovatnoća da određeni igrač pobedi dobija se deljenjem broja ishoda u kojima taj igrač pobeđuje sa ukupnim brojem ishoda. Jedan špil sadrži po jednu od prethodno opisane 32 karte.

Ulaz:

U prvoj liniji ulaznog tekstualnog fajla poker.in nalazi se prirodan broj N (2 ≤ N ≤ 10) , broj igrača. U sledećih 2N linija nalaze se karte koje su podeljene igračima na početku i to u drugoj i trećoj karte prvog igrača, u četvrtoj i petoj drugog... Sve karte su date u obliku boja razmak vrsta, gde su boje označene sa P K H T, a vrste sa A K Q J 10 9 8 7.

Izlaz:

U prvoj liniji izlaznog tekstualnog fajla poker.out ispisati verovatnoću da će pobediti prvi igra, u drugoj drugi... U N+1-voj liniji ispisati verovatnću da će biti nerešeno. Sve verovatnoće iskazati u procentima. Dozvoljeno odstupanje od tačne vrednosti je 0.01.

Primer:

poker.in      poker.out
3
P A
H A
T A
T 8
T 7
H 8
        
65.48
9.89
19.64
4.97
rešenje

Zadatak se rešava pravolinijskom simulacijom. Generišu se sve mogućnosti i onda se ispita ishod svake. Međutim, postoje detalji na koje se mora paziti.

Prvi od njih je predstavljanje podataka. Iako se karte mogu pamtiti kao stringovi to je veoma neprakticno zbog poređenja. Mnogo je lakše kodirati ih kao brojeve, poredane po jačini. Pošto od svake vrste ima po 8 karata, A će biti predstavljen sa 7, K sa 6 ... 7 sa 0. Radi lakšeg generisanja kombinacija sve karte ce biti poređane po bojama i kodirane brojevima od 0 do 31. Na primer K 10 ce biti broj 11.

Kombinacije se generišu standardnim algoritmom za generisanje kombinacija bez ponavljanja. Od nepodeljenih karata se bira pet i na onda se računa ishod partije ako su tih pet karata na stolu.

Sad dolazimo do drugog pipavog detalja: kako odrediti pobednika, odnosno kako porediti najbolje kombinacije karata za svakog igrača. Mogli bi napisati po jednu proceduru za svaku kombinaciju karata (par, dva para...) i onda za proveravati za svaku od tih karata da li neki igrač može da je sastavi od svoje dve i pet karata sa stola. Međutim, mnogo je praktičnije za svakog igraca odrediti najbolji ishod i samo njih porediti. Pamćenje tih ishoda se najlakše realizuje kodiranjem u prirodan broj tako da veci broj pokazuje bolji ishod. Na kraju se najbolji ishodi svakog igraca porede i određuje pobednik čiji se broj pobeda poveća za 1. Ako je nerešeno povećava se broj nerešenih partija. Takođe se broji i ukupan broj partija.

Na kraju se u izlazni fajl ispišu verovatnoće koje se dobijaju kad se broj pobeda svakog igrača pomnožen sa 100 podeli sa ukupnim brojem partija.

Prilažemo dva rešenja, pri čemu drugo rešenje (pisano u paskalu) radi znatno sporije, jer proveru radi za sve petočlane podskupove skupa od 7 karata.

fajl: poker.cpp
#include <fstream>
#include <string>
using namespace std;
void init(bool karte[])
{
  for (int i=0;i<32;i++)
    karte[i]=false;  
}
bool karte[32],sto[32];
bool igrac[10][32];
int ukupno,nereseno,n;
int dobio[10];
ifstream fin("poker.in");
ofstream fout("poker.out");
   

int skor(int brojIgraca)
{
  int i,j,k;
  bool pom[32];
  int boja[4];
  for (i=0;i<4;i++) boja[i]=0;
  int vrsta[8];
  for (j=0;j<8;j++) vrsta[j]=0;
  for (i=0;i<32;i++) pom[i]=false;
  for (i=0;i<4;i++)
    for (j=0;j<8;j++)
    if (igrac[brojIgraca][8*i+j]||sto[8*i+j])
    {
      boja[i]++;  //brojimo karte iste boje
    vrsta[j]++;  //brojimo karte iste vrste
    pom[8*i+j]=true;
      }
  for (i=0;i<4;i++)
    if (pom[8*i+7]&&pom[8*i+6]&&pom[8*i+5]&&pom[8*i+4]&&pom[8*i+3])
    return 800; //fles rojal
  for (i=0;i<4;i++)
    if (boja[i]>=5)
    {
      for (j=6;j>3;j--)
      if (pom[8*i+j]&&pom[8*i+j-1]&&pom[8*i+j-2]&&pom[8*i+j-3]&&pom[8*i+j-4])
        return 700+j; //fles, j najjaca karta
    for (j=7;j>=0;j--)
      if (vrsta[j]==4)
        return 600+j; //poker
      for (j=7;j>=0;j--)
      for (k=7;k>=0;k--)
        if ((vrsta[j]==3) && (vrsta[k]>=2) && (j!=k))  //ful
        return 500+10*j+k;
      for (j=7;j>=0;j--)
      if (pom[8*i+j]) //najjaca karta boje
        return 400+j; //boja
    }  
   for (j=7;j>=0;j--)
     if (vrsta[j]==4)
       return 600+j;  //poker, nije bilo boje
   for (j=7;j>=0;j--)
    for (k=7;k>=0;k--)
      if ((vrsta[j]==3) && (vrsta[k]>=2) && (j!=k))  //ful, nije bilo boje
      return 500+10*j+k;
   for (j=7;j>3;j--)
    if (vrsta[j]&&vrsta[j-1]&&vrsta[j-2]&&vrsta[j-3]&&vrsta[j-4])
      return 300+j; //kenta, j najjaca karta   
   for (i=7;i>=0;i--)
     if (vrsta[i]==3)
     return 200+i; //triling
   for (i=7;i>0;i--)
     if (vrsta[i]==2)
   {
     for (j=i-1;j>=0;j--)
       if (vrsta[j]==2)
        return 100+10*i+j; //dva para
   }
   for (i=7;i>=0;i--)
     if (vrsta[i]==2)   
     return 10+i; //par
   return 0; //nista ;-(
}


void izracunaj()
{
   int i,naj=0,max=0,t;
   bool jednako=true;
   for (i=0;i<n;i++)
   {
     t=skor(i);
   if (t>max)
   {
     max=t;
     naj=i;
     jednako=false;
   }
   else if (t==max)
     jednako=true;
   }
  ukupno++;
  if (jednako) {nereseno++; }
  else dobio[naj]++;
}


void gen(int k,int min)
{
  if (k==5)
    izracunaj();
  else
    for (int i=min;i<32;i++)
    if (!karte[i])
    {
       karte[i]=true;
     sto[i]=true;
     gen(k+1,i+1);
     karte[i]=false;
     sto[i]=false;
    }
}


int main()
{
   int i,t;
   string s;
   fin>>n;
   init(karte);
   ukupno=0;
   nereseno=0;
   for (i=0;i<n;i++)
   {
       dobio[i]=0;
       init(igrac[i]);
     fin>>s;
     t=0;
     switch (s[0])
     {
        case 'T':t+=8;
      case 'H':t+=8;
      case 'K':t+=8;
     }
     fin>>s;
     switch (s[0])
     {
         case 'A':t+=7;break;
       case 'K':t+=6;break;
       case 'Q':t+=5;break;
       case 'J':t+=4;break;
       case '1':t+=3;break;
       default: t+=s[0]-'7';
     }
     igrac[i][t]=true;
     karte[t]=true;
     fin>>s;
     t=0;
     switch (s[0])
     {
        case 'T':t+=8;
      case 'H':t+=8;
      case 'K':t+=8;
     }
     fin>>s;
     switch (s[0])
     {
         case 'A':t+=7;break;
       case 'K':t+=6;break;
       case 'Q':t+=5;break;
       case 'J':t+=4;break;
       case '1':t+=3;break;
       default: t+=s[0]-'7';
     }
     igrac[i][t]=true;
     karte[t]=true;
   }
   fin.close();
   init(sto);
   gen(0,0);
   for (i=0;i<n;i++)
     fout<<dobio[i]*100.0/ukupno<<endl;
   fout<<nereseno*100.0/ukupno<<endl;
   fout.close();
   return 0;
}

fajl: poker2.cpp
#include <iostream>
#include <string>
#include <map>
#include <limits.h>
using namespace std;

#define FOR(i,j) for(int i=0;i<j;i++)
#define FORi(i,j,k) for(int i=j;i<k;i++)
#define C(i) (i<<3)

int cads[32] = {0},table[32] = {0}, player[10][32] = {0}, won[10] = {0};
int total = 0, draw = 0, N;  

int skor(int brojplayera)
{
    int suit[4] = {0}, kind[8] = {0}, hand[32] = {0}, score = 0;
    
    FOR(i,4) FOR(j,8) {
        int b = (player[brojplayera][8*i+j]||table[8*i+j]);
        suit[i]+=b; 
        kind[j]+=b;
        hand[8*i+j]=b;
    }
    
    FOR(i,4) {
        score >?= (hand[8*i+7]&&hand[8*i+6]&&hand[8*i+5]&&hand[8*i+4]&&hand[8*i+3])*800;
        if (suit[i]>=5) {
            FORi(j,4,7) score >?= (hand[8*i+j]&&hand[8*i+j-1]&&hand[8*i+j-2]&&hand[8*i+j-3]&&hand[8*i+j-4]) * (700+j);
            FOR(j,8) score >?= (hand[8*i+j]) * (400+j);
        } 
    }

    FOR(j,8) {
        score >?= (kind[j]==4)*(600+j); 
        FOR(k,8) score >?= ((j!=k) && (kind[j]==3) && (kind[k]>=2)) * (500+10*j+k); 
        score >?= ((j>3)&&(kind[j]&&kind[j-1]&&kind[j-2]&&kind[j-3]&&kind[j-4])) * (300+j); 
        score >?= (kind[j]==3)*(200+j); 
        FOR(k,8) score >?= ((j!=k) && (kind[j]>=2) && (kind[k]>=2)) * (100+10*j+k); 
        score >?= (kind[j]==2) * (10+j); 
    }
    
    return score;
}


void izracunaj()
{
    int naj=0,max=0,t,jednako=0;
    FOR(i,N) {
        t=skor(i);
        jednako |= (t==max);
        if (t>max) {
            max=t;
            naj=i;
            jednako=0;
        }
    }
    total++;
    draw += jednako;
    won[naj] += 1 - jednako;
}


void gen(int k,int min) {
    if (k==5)
        izracunaj();
    else
        FORi(i,min,32)
            if (!cads[i]) {
                cads[i]=table[i]=1;
                gen(k+1,i+1);
                cads[i]=table[i]=0;
            }
}


int main()
{   
    map<char,int> M; M['A']=7;M['K']=6;M['Q']=5;M['J']=4;M['1']=3;M['9']=2;M['8']=1;M['7']=0;
    map<char,int> Q; Q['T']=24;Q['H']=16;Q['K']=8;Q['P']=0;
   
    string p,q;
    cin >> N;
    FOR(i,2*N) {
     cin >> q >> p;
     int t = M[p[0]]+Q[q[0]];
     player[i/2][t] = cads[t] = 1;
    }
        
    gen(0,0);
    
    FOR(i,N) cout<<won[i]*100.0/total<<endl;
    cout<<draw*100.0/total<<endl;

    cout << total << endl;
    
    cin >> N;
    return 0;
}

fajl: poker.pas
const
   fin = 'poker.in';
   fout = 'poker.out';
   MaxN = 10;

var
   n : Integer;
   c : array[1..MaxN, 1..2] of Integer;
   p : array[0..MaxN] of Double;



   procedure Solve;
   var
      t : array[1..5] of Integer;
      t1, t2, t3, t4, t5 : Integer;

      function CalcPower(t6, t7 : Integer) : Integer;
      var
         q : array[1..7] of Integer;
         s : array[1..5] of Integer;
         maxPower : Integer;

         function Evaluate : Integer;
         var
            i, j : Integer;
            k : Integer;

            count : array[0..7] of Integer;
            flush, straight : Boolean;
            c4, c3, c2h, c2l, c1 : Integer;
         begin
            // counting numbers
            for i := 0 to 7 do
               count[i] := 0;
            for i := 1 to 5 do
               inc(count[s[i] mod 8]);

            // flush test
            flush := true;
            for i := 2 to 5 do
               if (s[i] div 8) <> (s[1] div 8) then
               begin
                  flush := false;
                  break;
               end;

            // straight test
            straight := true;
            k := 0;
            for i := 0 to 7 do
            begin
               if count[i] = 1 then
                  inc(k)
               else
                  if (count[i] > 1) or ((k > 0) and (k < 5)) then
                  begin
                     straight := false;
                     break;
                  end;
            end;

            c4 := -1; c3 := -1; c2h := -1; c2l := -1;
            for i := 0 to 7 do
            begin
               if count[i] = 4 then c4 := i;
               if count[i] = 3 then c3 := i;
               if count[i] = 2 then
               begin
                  c2l := c2h;
                  c2h := i;
               end;
               if count[i] > 0 then c1 := i;
            end;


            if flush and straight and (c1 = 7) then begin Evaluate := 9 * 64 +   0 * 8 +   0; exit; end;
            if flush and straight              then begin Evaluate := 8 * 64 +  c1 * 8 +   0; exit; end;
            if (c4 <> -1)                      then begin Evaluate := 7 * 64 +  c4 * 8 +   0; exit; end;
            if (c3 <> -1) and (c2h <> -1)      then begin Evaluate := 6 * 64 +  c3 * 8 + c2h; exit; end;
            if flush                           then begin Evaluate := 5 * 64 +  c1 * 8 +   0; exit; end;
            if straight                        then begin Evaluate := 4 * 64 +  c1 * 8 +   0; exit; end;
            if (c3 <> -1)                      then begin Evaluate := 3 * 64 +  c3 * 8 +   0; exit; end;
            if (c2h <> -1) and (c2l <> -1)     then begin Evaluate := 2 * 64 + c2h * 8 + c2l; exit; end;
            if (c2h <> -1)                     then begin Evaluate := 1 * 64 + c2h * 8 +   0; exit; end;
            Evaluate := 0;
         end;

         procedure EvaluateSubset(p, k : Integer);
         var
           j, t : Integer;
         begin
            if k = 5 then
            begin
               t := Evaluate;
               if t > maxPower then
                  maxPower := t;

               exit;
            end;

            for j := p to 3 + k do
            begin
               s[k+1] := q[j];
               EvaluateSubset(j + 1, k + 1);
            end;
         end;

      var
         i : Integer;

      begin
         q[1] := t1; q[2] := t2; q[3] := t3; q[4] := t4; q[5] := t5;
         q[6] := t6;
         q[7] := t7;

         maxPower := 0;
         EvaluateSubset(1, 0);
         CalcPower := maxPower;
     end;

   var
      used : array[0..31] of Boolean;
      i, h : Integer;
      power : array[1..MaxN] of Integer;
      wins : array[0..MaxN] of Longint;
      total : Longint;
      maxPower : Integer;
      bestPlayer : Integer;
   begin
      for i := 0 to 31 do
         used[i] := false;

      for i := 1 to n do
      begin
         if c[i, 2] < c[i, 1] then
         begin
            h := c[i, 1];
            c[i, 1] := c[i, 2];
            c[i, 2] := h;
         end;

         used[c[i, 1]] := true;
         used[c[i, 2]] := true;
         wins[i] := 0;
      end;
      total := 0;

      for t1 := 0 to 31 - 4 do
      if not used[t1] then
      begin
         used[t1] := true;

         for t2 := t1 + 1 to 31 - 3 do
         if not used[t2] then
         begin
            used[t2] := true;

            for t3 := t2 + 1 to 31 - 2 do
            if not used[t3] then
            begin
               used[t3] := true;

               for t4 := t3 + 1 to 31 - 1 do
               if not used[t4] then
               begin
                  used[t4] := true;

                  for t5 := t4 + 1 to 31 do
                  if not used[t5] then
                  begin
                     for i := 1 to n do
                        power[i] := calcPower(c[i, 1], c[i, 2]);

                     maxPower := -1;
                     for i := 1 to n do
                     begin
                        if power[i] > maxPower then
                        begin
                           maxPower := power[i];
                           bestPlayer := i;
                        end else
                           if power[i] = maxPower then
                              bestPlayer := 0;
                     end;

                     inc(total);
                     inc(wins[bestPlayer]);
                  end;

                  used[t4] := false;
               end;

               used[t3] := false
            end;

            used[t2] := false;
         end;

         used[t1] := false;
      end;

      for i := 0 to n do
         p[i] := 100 * wins[i] / total;
   end;



   procedure ReadInput;
   var
      f : Text;
      i : Integer;

      function ReadCard : Integer;
      var
         ch : Char;
         suit, number : Integer;
      begin
         Read(f, ch);
         case ch of
            'P' : suit := 0;
            'K' : suit := 1;
            'H' : suit := 2;
            'T' : suit := 3;
         end;
         Read(f, ch);
         Read(f, ch);
         case ch of
            'A' : number := 7;
            'K' : number := 6;
            'Q' : number := 5;
            'J' : number := 4;
            '1' : begin number := 3; Read(f, ch); end;
            '9' : number := 2;
            '8' : number := 1;
            '7' : number := 0;
         end;
         Readln(f);
         ReadCard := suit * 8 + number;
      end;

   begin
      Assign(f, fin);
      Reset(f);
      Readln(f, n);
      for i := 1 to n do
      begin
         c[i][1] := ReadCard;
         c[i][2] := ReadCard;
      end;
      Close(f);
   end;


   procedure WriteOutput;
   var
      f : Text;
      i : Integer;
   begin
      Assign(f, fout);
      Rewrite(f);
      for i := 1 to n do
         Writeln(f, p[i]:0:2);
      Writeln(f, p[0]:0:2);
      Close(f);
   end;



begin
   ReadInput;
   Solve;
   WriteOutput;
end.