Trojica okorelih kriminalaca su izveli pljačku veka u dalekoj zemlji Bajtoviji, na
planini Velebajt. Oni su uleteli u rudnik i iz njega izneli N još uvek neobrađenih
dijamanata. Na kraju uspešne akcije, njih trojica treba da podele plen. Pošto su to
kriminalci, to je vrlo komplikovana procedura u kojoj svako želi da dobije što više.
Problem je što svako na svoj način procenjuje svoj udeo u celoj akciji, i ne samo to,
svako na svoj način procenjuje vrednost dijamanata koje su ukrali. Da bi lakše podelili
plen, oni su pozvali programere sa takmičenja.
Morate biti vrlo pažljivi prilikom
podele. Svaki dijamant treba dodeliti tačno jednom od lopova. Potrebno je napraviti
podelu tako da svaki od lopova bude zadovoljan. Lopov će biti zadovoljan ako suma
procenjenih vrednosti dijamanata koji su dodeljeni njemu nije manja od onoga što on
misli da zaslužuje, naravno, sve prema njegovoj proceni. Primera radi, ukoliko jedan
lopov procenjuje sumu vrednosti dijamanata na 10 miliona, i ako smatra da je njegov udeo
37%, onda on neće biti zadovoljan sa podelom u kojoj dijamanti koje on dobija po
njegovoj proceni vrede manje od 3.7 miliona.
Kao nagradu za dobro odrađenu podelu, svaki
od kriminalaca isplatiće u dolarima 5% sume vrednosti dijamanata koju je on dobio,
prema svojoj proceni. Ono što ne želimo, to su nezadovoljni kriminalci, tako da je
potrebno napraviti podelu tako da se niko ne oseća oštećenim, a potom napraviti
takvu podelu da programerski honorar bude što veći.
Ulaz:
(Ulazni podaci se nalaze u datoteci pljacka.in) U prvom redu se nalazi prirodan broj N, ukupan broj dijamanata. U
narednom redu se nalaze 3 prirodna broja A, B i C, razdvojena razmakom. Oni
prikazuju procenjeni udeo za svakog od lopova. U svakom od narednih N redova, nalazi se
po 3 broja, A(i), B(i) i C(i), u milionima dolara, koji govore koliko svaki od 3
lopova procenjuje vrednost i-tog dijamanta.
Izlaz:
(Izlazne podatke upisati u datoteku pljacka.out) U svaki od N redova izlaza, treba ispisati slovo A
, B
ili
C
u zavisnosti od toga koji lopov dobija koji dijamant. Ako ima više rešenja,
štampati bilo koje. Ukoliko nema rešenja, u jednom redu ispisati ODE GLAVA!
.
Ogranicenja:
- Ukupan broj dijamanata: 3 ≤ N ≤ 25
- Subjektivni udeo svakog od lopova (u procentima): 1 ≤ A, B, C ≤ 100
- Procenjena vrednost dijamanata: 1 ≤ A(i), B(i), C(i) ≤ 40
- vremensko ograničenje za izvršavanje programa je 1 s
- memorijsko ograničenje za izvršavanje programa je 32 MB
Primer 1:
pljacka.in
|
|
pljacka.out
|
5
30 30 60
10 5 5
1 5 10
10 5 10
5 10 5
5 5 5
|
|
A
C
C
B
C
|
Primer 2:
pljacka.in
|
|
pljacka.out
|
3
50 50 50
7 7 7
4 5 6
6 5 4
|
|
ODE GLAVA!
|