.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » ic

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
ic


Timp maxim de executie/test:
1 secunda
Memorie totala disponibila/stiva:
16MB/1 MB

Aveti la dispozitie N obiecte, numerotate de la 1 la N. Fiecare obiect i are o greutate wi si un cost ci. O submultime SN a celor N obiecte poate contine fiecare obiect cel mult o data. Greutatea unei submultimi SN este egala cu suma greutatilor obiectelor din SN, iar costul unei submultimi SN este egal cu suma costurilor obiectelor din SN. Fie cmin costul minim al unei submultimi SN a carei greutate este egala cu o valoare data S. Se doreste clasificarea fiecarui obiect i intr-una din urmatoarele 3 categorii:

  • categoria 1: obiectul i face parte din categoria 1 daca apartine fiecarei submultimi avand greutatea egala cu S si costul egal cu cmin (altfel spus, nu exista nicio submultime SN cu greutatea S si costul cmin care sa nu contina obiectul i)
  • categoria 2: obiectul i face parte din categoria 2 daca nu face parte din categoria 1, dar apartine cel putin unei submultimi SN a carei greutate este S si al carei cost este cmin
  • categoria 3: obiectul i face parte din categoria 3 daca nu apartine niciunei submultimi SN avand greutatea S si costul cmin

Cerinta

Scrieti un program care sa determine pentru fiecare obiect i categoria din care face parte acesta.

Date de intrare

Fisierul de intrare ic.in contine pe prima linie numarul natural T, reprezentand numarul de teste descrise in fisier. In continuare sunt descrise cele T teste. Prima linie a fiecarui test contine numerele naturale N si S, separate printr-un spatiu. Urmatoarele N linii descriu cele N obiecte: a i-a dintre aceste N linii contine numerele naturale wi si ci (separate printr-un spatiu).

Date de iesire

In fisierul de iesire ic.out veti afisa T linii. A i-a dintre aceste linii va contine raspunsul pentru al i-lea test dat in fisierul de intrare. Raspunsul pentru un test consta dintr-un sir de N caractere, unde N este numarul de obiecte din testul respectiv. Al j-lea caracter din acest sir reprezinta categoria din care face parte obiectul j. Cele N caractere pot lua una dintre valorile '1', '2' sau '3' si nu sunt separate prin spatii.

Restrictii

  • 1 <= T <= 100
  • 1 <= N <= 200
  • 1 <= S <= 700
  • 1 <= wi <= 10
  • 1 <= ci <= 10
  • Se garanteaza ca, pentru fiecare test dat in fisierul de intrare, va exista cel putin o submultime de obiecte a carei greutate sa fie egala cu S.

Exemplu

ic.in ic.out
2
6 10
3 2
2 6
3 4
4 10
4 11
5 8
2 2
2 3
2 3
122232
22
Asist. univ. dr. ing. Mugurel Ionut Andreica
Facultatea de Automatica si Calculatoare,
Universitatea Politehnica din Bucuresti
mugurel.andreica@cs.pub.ro
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2009: efort, muzeu, bal, seti, basm, dansatori, smith, timer, secvsir, vot, cetati, reziduu, biliard, prefix1, accesibil, dp, jocv, placa, palc, prod3, predecesor, standard, cantor, nkbiti, nori, triti, kperms, sotron1, impozit, tablite, fazan, lanturi, secvpar, tom, joker, matriosca, asociativ, lego, medalii, permutari, cfr, treegame, scanduri, site, fotbal, links, kbiti, segm, album, iepurasi, jucarii, m4, bradut, trmv, colorare, greutati, concat, graphgame, echilibru, brazi, mat, cubinvers, mobil, distsir, parbit
De acelaşi autor: autobuze, bile, complex, balaur, vmem, kreg, ro, jobs, senzori, echipe, agitatie, center, algebra, tgraf, bcast, promo, asmax, sediu, granita, string, poligon1, csir, lsort, zoo, bombo, ab3, soc, rsp, tcast, tj, lanterna, base3, color, trans, xp, v2d, ppcover, carray, asfalt1, module, gxor
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor