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

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


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

Un fermier trebuie sa transporte cu trenul o cireada formata din N vaci. Pe fiecare animal este pictat un numar de ordine, cuprins intre 1 si N, astfel incat oricare doua animale au numere distincte.
Trenul este format din K vagoane si, evident, o locomotiva care este irelevanta pentru problema noastra. In fiecare vagon pot fi incarcate cel mult M vaci. Vacile stau cuminti la coada, in ordinea crescatoare a numerelor lor de ordine (vaca numerotata cu 1 se va urca in tren prima). La un moment dat sunt incarcate intr-un vagon un numar oarecare de vaci (care nu depaseste M), de la inceputul cozii, dupa care vagonul este incuiat, deci nu se mai pot incarca ulterior alte vaci in vagonul respectiv.
Se stie ca exista perechi de animale care se antipatizeaza si daca sunt incarcate in acelasi vagon se vor bate, iar cel mai puternic il va omori pe celalalt. Se stie de asemenea ca exista perechi de animale care se simpatizeaza si daca animalul mai slab este atacat, cel mai puternic il va proteja.
Dupa ce vagonul se inchide animalele incep sa se atace. Transportul dureaza suficient de mult, astfel incat toate conflictele sa se epuizeze.

Cerinta

Scrieti un program care sa determine o modalitate de incarcare a animalelor in vagoane, astfel incat sa ajunga la destinatie un numar maxim de animale vii.

Date de intrare

Fisierul de intrare transport.in contine pe prima linie numerele naturale N K M, separate prin spatii. Pe cea de a doua linie numarul natural D, care reprezinta numarul de perechi de animale care se antipatizeaza. Pe fiecare dintre urmatoarele D linii exista 3 numere naturale distincte A B C, cu semnificatia: perechea de vaci (A, B) se antipatizeaza, iar perechea de vaci (C, B) se simpatizeaza. In ambele perechi animalul al doilea (B) este cel mai slab.
Cel mai puternic animal dintr-o pereche de animale care se antipatizeaza nu poate sa apara intr-o alta astfel de pereche ca al doilea animal (adica cel mai slab). Animalul slab dintr-o pereche de animale care se simpatizeaza are exact un protector mai puternic (adica C este unic determinat de A si B).

Date de iesire

Fisierul de iesire transport.out contine pe prima linie numarul de animale ajunse vii la destinatie (maxim posibil).

Restrictii

  • 1 <= N, K <= 1000
  • 1 <= M <= 20

Exemple

transport.in transport.out
5 2 3
2
1 2 3
1 3 2
5

 

transport.in transport.out
8 3 3
6
4 6 2
5 6 4
7 8 6
5 3 6
7 6 5
2 3 4
5

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Şansa de a deveni campion 2002: adevar, marcare, joc10, prieteni1, bare, soricel1, traseu, zapezi, banda10, soricel2, masina2, excursie1, asmax, salvare, perechi1, culmi, tramvai1, numar2, sume1, raft, bloc, schi, joc12, sediu, soricel3, ferma, fni, sah1, suma3, granita, nr4, fractie, blockout, join, cod3, tunel, lover, trip, pepsi, string, medii, tren3, avion, prime1, poligon1, monkey, premii1, garaj, carti2, gramada, microvirus, tv, gramezi1, puncte2, benzina, aranjari, numere5, fat, izo, cafea, top, echipe1, zoo, secvente
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, checkin, 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, 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 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, 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, ic, 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
Software recomandat
surse trimise | ajutor