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

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


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

În scopul alimentării cu energie electrică a unui nou cartier de vile, au fost amplasaţi n stâlpi, pentru susţinerea cablurilor care transportă energia electrică. Toţi cei n stâlpi, sunt poziţionaţi de-a lungul unei semidrepte, cu originea în staţia de alimentare. Coordonatele stâlpilor în raport cu staţia de alimentare, sunt numere naturale distincte. O comisie însărcinată cu verificarea lucrărilor a constatat că nu s-au respectat întocmai specificaţiile tehnice privitoare la distanţa minimă, respectiv maximă dintre oricare doi stâlpi consecutivi. Prin urmare, firma care a efectuat lucrările, trebuie să mute o parte dintre cei n stâlpi, astfel încât, distanţa minimă dintre oricare doi stâlpi consecutivi să fie de cel puţin K metri, iar distanţa maximă să nu depăşească P metri. A muta un stâlp, înseamnă, a-l scoate din pământ, a-l deplasa pe o anumită distanţă, pe linia care uneşte poziţiile tuturor stâlpilor, şi a-l fixa în pământ, într-o poziţie finală, a cărei distanţă faţă de staţia de alimentare este exprimată în metri, şi este un număr întreg, pozitiv. Prin urmare, mutarea unui stâlp este o operaţie costisitoare. De aceea, firma are interesul să mute un număr cât mai mic de stâlpi. Să considerăm un sistem unidimensional de coordonate Ox, cu staţia de alimentare plasată în origine. Atunci atât coordonatele iniţiale, cât şi cele finale ale tuturor stâlpilor, vor fi valori întregi, nenegative. Într-o poziţie oarecare, inclusiv în staţia de alimentare, se poate amplasa doar un singur stâlp.

Cerinţă

Determinaţi numărul minim de stâlpi care trebuie mutaţi din poziţiile actuale, pentru a se obţine un amplasament final care respectă specificaţiile tehnice.

Date de intrare

Fişierul stalpi.in conţine pe prima linie numerele naturale n, K, P separate prin câte un singur spaţiu. Pe linia a doua este scrisă o secvenţă strict crescătoare de n numere naturale x1, x2, ... xn despărţite prin câte un spaţiu. Al i-lea număr din secvenţă reprezintă distanţa exprimată în metri, la care se găseşte stâlpul i în raport cu staţia de alimentare.

Date de ieşire

Fişierul stalpi.out va conţine pe prima linie numărul natural S, reprezentând numărul minim de stâlpi care trebuie să fie mutaţi.

Restricţii

1 ≤ n ≤ 2500
0 ≤ x1 < x2 < ... < xn ≤ 2500
1 ≤ K ≤ 10
K ≤ P ≤ 50

Exemple

stalpi.instalpi.outExplicaţii
3 2 4 2 3 4 1 Se mută stâlpul 2, dincolo de stâlpul 3, la o distanţă de cel puţin 2 metri faţă de acesta.
5 2 4 1 6 7 9 14 2 O variantă posibilă: se mută stâlpul 3 de coordonată 7, între stâlpii 1 şi 2, la distanţa 2 sau 3 de stalpul 1, iar apoi se mută stâlpul 5 la distanţa 2, 3, sau 4 metri de stalpul 4.

autor: Prof. Constantin Gălăţan
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Finala .campion 2007: bitslang, kfactor, np, cutie2, bete, hperm, nr2
De acelaşi autor: ozn, pod, numere, vikingi, furtuna, livada, teatru, iepuras2, kimberley, novel, friends2, tabara, sport, randuri, panouri, powerpuff, cartele, joc15, stalpi1, autostrazi, telecab, pseudobil, harta2
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, 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