|
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.
|
logo by Igor Antolović
|
|
|
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:
- fleš rojal: A,K,Q,J,10 u istoj boji (sve boje su ravnopravne) (primer: PA, PK, PQ, PJ, P10)
- boja-kenta: pet karata iste boje poređane po redu (najjača karta odlučuje) (primer: HJ, H10, H9, H8, H7)
- 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)
- 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)
- boja: pet karata iste boje (najjača karta odlučuje) (primer: PQ, PJ, P10, P8, P7)
- kenta: pet karata poređane po redu (najjača karta odlučuje) (primer: TQ, HJ, T10, H9, K8)
- 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)
- 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)
- 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.
|
|
|