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

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


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

Într-o bibliotecă se află C dulapuri identice aşezate unul lângă altul pe peretele unei încăperi, dulapurile fiind numerotate de la stânga spre dreapta cu numerele naturale de la 1 la C. Fiecare dulap conţine 1000 de rafturi, situate vertical unul deasupra altuia, rafturile fiecărui dulap fiind numerotate de la 1 la 1000 de jos în sus.
Fiecare dulap este prevăzut cu o scară cu care se poate ajunge la orice raft. Dacă bibliotecara urcă scara unui anumit dulap D până la un anumit nivel k, ea va putea aduna orice carte de pe rafturile 1 până la k inclusiv, din dulapul D şi din dulapurile învecinate (dulapul D-1 şi dulapul D+1).
Cunoscând dulapurile şi rafturile de unde trebuie luate cărţi, bibliotecara doreşte să adune toate cărţile cerute, dar suma înălţimilor până la care trebuie să urce să fie minimă.

Cerinţă

Scrieţi un program care să determine suma minimă a înălţimilor până la care trebuie să urce bibliotecara pentru a aduna toate cărţile cerute.

Date de intrare

Prima linie a fişierului de intrare rafturi.in conţine două numere naturale C şi N, separate printr-un spaţiu, reprezentând numărul dulapurilor şi respectiv numărul cărţilor pe care bibliotecara trebuie să le adune.
Următoarele N linii conţin câte două numere naturale a b, separate printr-un spaţiu, reprezentând numărul dulapului, respectiv numărul raftului de unde trebuie luată o carte.

Date de ieşire

Fişierul de ieşire rafturi.out va conţine un singur număr natural reprezentând suma minimă a înălţimilor până la care trebuie să urce bibliotecara pentru a aduna toate cărţile cerute.

Restricţii

1≤ C ≤ 10 000
1≤ N ≤ 50 000

Exemple

rafturi.inrafturi.outExplicaţii
10 4 5 4 1 1 6 2 3 8 11 Bibliotecara urcă astfel:
-pe dulapul 1 la raftul 1
-pe dulapul 4 la raftul 8
-pe dulapul 6 la raftul 2

autor: Prof. Sanda Junea
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2009: bile, checkin, numere, text, reactii, volei, magic2, sirag, taste, tetris, origami, joc2, br, reinvent, perspic, tir, patrate2, nrcuv2, matrice, patrate1, pikachu, taxe, cartonas, case, desen2
De acelaşi autor: patrat1, iepuras1
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, 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, 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
surse trimise | ajutor