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.

pljacka.cpp    2,999 b      izvorni kod rešenja
pljacka.tests.rar    2,307 b      test primeri

zadatak: Pljačka veka

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!
fajl: pljacka.cpp
/*
ZADATAK: pljacka
JEZIK: c++
*/
#include <cstdlib>
#include <fstream>

using namespace std;
const int MAXN = 25;
const int MAXVAL = 40;
const int MAXT = MAXN * MAXVAL + 1;
int n;
int a, b, c, suma, sumb, sumc;
int va[MAXN], vb[MAXN], vc[MAXN];
char sol[MAXN];
bool sol_exists;
short max1[MAXT][MAXT], max2[MAXT][MAXT];
char who[MAXN][MAXT][MAXT];

void input(ifstream& in) {
     in >> n;
     in >> a >> b >> c;
     suma = 0; sumb = 0; sumc = 0;
     for (int i = 0; i < n; i++) {
         in >> va[i] >> vb[i] >> vc[i];
         suma += va[i];
         sumb += vb[i];
         sumc += vc[i];
     }
}

void output(ofstream& out) {
     if (!sol_exists) {
        out << "ODE GLAVA!\n";
        return;
     }
     for (int i = 0; i < n; i++) {
         out << sol[i] << "\n";
     }
}

void solve() {
     for (int j = 0; j < MAXT; j++)
         for (int k = 0; k < MAXT; k++) {
             max1[j][k] = -1;
             max2[j][k] = -1;
         }
     max1[0][0] = 0;
     for (int i = 0; i < n; i++) {
         for (int j = 0; j < MAXT; j++)
             for (int k = 0; k < MAXT; k++)
                 if (max1[j][k] >= 0) {
                    if (j + va[i] <= MAXT)
                       if (max1[j][k] > max2[j+va[i]][k]) {
                          max2[j+va[i]][k] = max1[j][k];
                          who[i][j+va[i]][k] = 'A';
                       }
                    if (k + vb[i] <= MAXT)
                       if (max1[j][k] > max2[j][k+vb[i]]) {
                          max2[j][k+vb[i]] = max1[j][k];
                          who[i][j][k+vb[i]] = 'B';
                       }
                    if (max1[j][k] + vc[i] > max2[j][k]) {
                       max2[j][k] = max1[j][k] + vc[i];
                       who[i][j][k] = 'C';
                    }

                 }
         for (int j = 0; j < MAXT; j++)
             for (int k = 0; k < MAXT; k++) {
                 max1[j][k] = max2[j][k];
                 max2[j][k] = -1;
             }
     }
     int bestj = 0, bestk = 0;
     sol_exists = false;
     for (int j = 0; j < MAXT; j++)
         for (int k = 0; k < MAXT; k++) {
             if (j*100 >= a*suma && k*100 >= b*sumb && max1[j][k] * 100 >= c*sumc)
                if ((!sol_exists) || (j + k + max1[j][k] > bestj + bestk + max1[bestj][bestk])) {
                      bestj = j;
                      bestk = k;
                      sol_exists = true;
                }
         }
     if (sol_exists)
          for (int i = n-1; i >= 0; i--) {
              sol[i] = who[i][bestj][bestk];
              if (sol[i] == 'A')
                 bestj -= va[i];
              if (sol[i] == 'B')
                 bestk -= vb[i];
          }
}

int main(int argc, char *argv[])
{
    ifstream in("pljacka.in");
    ofstream out("pljacka.out");
    input(in);
    solve();
    output(out);
    in.close();
    out.close();
    return 0;
}