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

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


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

Ministerul organizează o excursie pentru olimpici la Paris. Suntem toţi la aeroport, K olimpici având în total P bagaje. Olimpicii la informatică trebuie să rezolve acum următoarea problemă.
Pentru zborul către Paris au fost deschise N ghişee pentru check-in, numerotate de la 1 la N . La fiecare ghişeu lucrează exact un angajat. Angajatul de la ghişeul i are nevoie de Ai secunde pentru a procesa fiecare bagaj al clientului prezentat la ghişeu şi Bi secunde pentru a emite toate tichetele de îmbarcare solicitate de client (acelaşi timp Bi , indiferent de numărul de tichete solicitate de client).
O persoană poate sta la un singur ghişeu şi poate preda 0, 1 sau mai multe bagaje (acestea vor fi trecute pe numele său). Evident, aceeaşi persoană nu poate sta la mai multe ghişee. De asemenea, o persoană poate să prezinte angajatului de la ghişeu biletele şi paşapoartele altor persoane, astfel că poate solicita emiterea mai multor tichete de îmbarcare. O persoană trebuie să solicite de la ghişeul la care se prezintă cel puţin un tichet de îmbarcare.
Iniţial nimeni nu stă la coadă la ghişeele pentru Paris. Timpul necesar pentru a face check-in-ul (predarea tuturor celor P bagaje şi obţinerea tichetelor de îmbarcare pentru toţi cei K olimpici) depinde de strategia adoptată (alegerea ghişeelor, stabilirea persoanelor care stau la coadă la ghişee şi împărţirea bagajelor). Olimpicii la informatică trebuie să găsească o strategie prin care cei K olimpici pot preda cele P bagaje şi obţine cele K tichete de îmbarcare în cel mai scurt timp.

Cerinţă

Scrieţi un program care să determine timpul minim necesar pentru check-in.

Date de intrare

Fişierul de intrare checkin.in conţine pe prima linie numărul natural N reprezentând numărul de ghişee pentru check-in. Urmează N linii pe care sunt descrise ghişeele. Pe linia i+1 sunt scrise numerele naturale Ai Bi (separate prin spaţiu) reprezentând timpul necesar angajatului de la ghişeul i pentru a procesa un singur bagaj al clientului de la ghişeu, respectiv timpul necesar pentru emiterea tuturor tichetelor de îmbarcare solicitate de clientul de la ghişeu. Pe ultima linie sunt scrise numerele naturale K şi P , separate prin spaţiu, reprezentând numărul de olimpici şi numărul de bagaje pe care le au.

Date de ieşire

Fişierul de ieşire checkin.out va conţine o singură linie pe care va fi scris timpul minim pentru check-in.

Restricţii

1 ≤ N ≤ 1000
1 ≤ Ai , Bi ≤ 1000
1 ≤ K ≤ 10000
0 ≤ P ≤ 10000

Exemple

checkin.incheckin.outExplicaţii
6 10 100 20 80 20 40 40 50 20 10 10 10 4 10 70 O persoană stă la ghişeul 3, predă un bagaj şi ia un tichet de îmbarcare.
O a doua persoană stă la ghişeul 5, predă 3 bagaje şi ia un tichet de îmbarcare.
O a treia persoană stă la ghişeul 6, predă 6 bagaje şi ia 2 tichete de îmbarcare.
A patra persoană nu stă la ghişeu.

autor: Prof. Emanuela Cerchez
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2009: bile, numere, text, reactii, volei, magic2, sirag, taste, tetris, origami, rafturi, joc2, br, reinvent, perspic, tir, patrate2, nrcuv2, matrice, patrate1, pikachu, taxe, cartonas, case, desen2
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre Greedy: lac, sumdif, baby, startrek, placi, gramezi, mese, jobs, politics, joc3, playlist, carte, exam, subperm, piloti, barca1, pitici, bombe, pic, bac, pal, antena, culmi, numar2, lover, sant1, volei1, ab3, camion1, aranjare, popas, reactivi, mesaj2, dp, jocv, segm, calorii, album, kdtree, sport2, telecab, dag, cifre4, micro, triburi, testament, nor, eoliene, vintage, cifre5, agenda, monede2, charlie, scadere, barci
Despre căutare binară: gropi, pod, uscat, copaci, aven, br, furtuna, livada, numar, matrice, sume, bacan, toys, chimie2, trafic, ants, multiplu, ghici, sirag1, tabara, puncte1, centru, harta1, salvare, spion, poze, dist1, patrate5, resturi, lanterna, sea2, vot, standard, cantor, medalii, binperm, mobil, stalpi1, expo, miere, conferinta, subs, pack, obstacole, dag, acoperire, verigi, bradut2, triburi, intervale, mijloc, patru, eliminare, vectori1, calcule, secvp, dreapta, colina, ssk, robotics, cabana
Software recomandat
surse trimise | ajutor