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.

racuni.cpp    1,869 b      izvorni kod rešenja
racuni.tests.7z    5,999,622 b      test primeri
racuni.checker.cpp    544 b      program za testiranje

zadatak: Računi

Đurica voli da obilazi restorane. Tokom godine je obixao puno restorana, i sad je baš ogladneo i zanima ga u koji sledeći da ode. U svim restoranima koje je Đurica posetio ukupno je naručio k različitih stavki, te se svaki račun može opisati kao

id s1 s2 ... sk.

Vrednost id je oznaka restorana. Svaka oznaka jedinstveno određuje jedan restoran, i svaki restoran je jedinstveno određen jednom oznakom. Vrednost si je 0 ako na tom računu ne postoji i-ta stavka, inače je prirodan broj koji predstavlja koliko je plaćena i-ta stavka. Đurica je sakupio tačno n računa, i njega zanima zbirni račun za svaki restoran. Imajući sve račune za restorane, zbirni račun za restoran id se definiše kao račun sa k stavki gde vrednost za i-tu stavku predstavlja sumu cena i-te stavke na svim računima restorana id.

Jednom kad Đurica ima sve zbirne račune, on smatra da je najbolji restoran u koji sledeći treba otići onaj koji ima leksikografski najmanji zbirni račun stavki. Đurica je gladan i ne može da razmišlja, te pomozite Đurici i za dati spisak računa ispišite lekikografski najmanji račun.
Tokom određivanja i ispisivanja leksikografski najmanjeg zbirnog računa ne treba uzimati u obzir id restorana. Za dva zbirna računa a1 a2 ... ak i b1 b2 ... bk kažemo da je prvi račun leksikografski manji od drugog ako postoji j takvo da ai = bi, i < j, i aj < bj.

Ulaz:

(Ulazni podaci se učitavaju iz datoteke racuni.in.) U prvom redu se nalaze dva prirodna broja n i k (1 ≤ n ≤ 30.000, 1 ≤ k ≤ 30) U narednih n redova su dati opisi računa u formatu

id s1 s2 ... sk.

Odgovarajuća ograničenja su: 1 ≤ id ≤ 1.000.000.000, 0 ≤ sj ≤ 100.000.

Izlaz:

(Izlazni podaci se ispisuju u datoteku racuni.out.) U prvom i jedinom redu ispisati k brojeva koji predstavljaju leksikografski najmanji zbirni račun.

Primer:

racuni.in      racuni.out
4 2
1 3 4
2 5 1
1 0 8
7 3 20
        
3 12

Objašnjenje.

Zbirni računi za restorane 1, 2 i 7 su redom 3 12, 5 1 i 3 20.

Primer:

racuni.in      racuni.out
7 4
11 303 0 0 0
2 10 2 8 0
13 20 3 8 1
11 9 4 0 0
2 9 4 0 1
2 3 0 0 5
13 2 3 0 0
        
22 6 8 1

Objašnjenje.

Restoran sa brojem 13 ima leksikografski najmanji zbirni račun.

fajl: racuni.cpp
#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <cmath>
#include <time.h>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)

using namespace std;

const int MAXN = 30000;
const int MAXK = 30;

struct recipe{
  int id, idx;
  recipe(){
  }
  
  recipe(int _id, int _idx){
    id = _id;
    idx = _idx;
  }
  
  friend bool operator <(const recipe &a, const recipe &b){
    return a.id < b.id;
  }
};

int val[MAXN][MAXK];

recipe recipes[MAXN];

long long sum[MAXN][MAXK];

int main(){
  char filein[32] = "racuni.in";
  char fileout[32] = "racuni.out";
  FILE *fin;
  FILE *fout;
  
  fin = fopen(filein, "r");
  fout = fopen(fileout, "w");
    
  int n, k, id;
  fscanf(fin, "%d %d", &n, &k);
  FOR (i, n){
    fscanf(fin, "%d", &id);
    recipes[i] = recipe(id, i);
    FOR (j, k)
      fscanf(fin, "%d", &val[i][j]);
  }
  
  sort(recipes, recipes + n);
  int idx = 0, j, cntIds = 0;
  while (idx < n){
    FOR (i, k)
      sum[cntIds][i] = 0LL;
    j = idx;
    while (j < n && recipes[idx].id == recipes[j].id){
      FOR (i, k)
        sum[cntIds][i] += val[recipes[j].idx][i];
      j++;
    }
    idx = j;
    cntIds++;
  }
  
  long long ret[k];
  ret[0] = 1LL << 60LL;
  FOR (i, cntIds){
    bool found = false;
    FOR (j, k)
      if (ret[j] > sum[i][j]){
        found = true;
        break;
      }
      else if (ret[j] < sum[i][j])
        break;
    if (found)
      FOR (j, k)
        ret[j] = sum[i][j];
  }

  FOR (i, k)
    fprintf(fout, "%lld ", ret[i]);

  fprintf(fout, "\n");
  fclose(fin);
  fclose(fout);
  return 0;
}