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

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


Timp maxim de execuţie/test:
0.15 secunde
Memorie totala disponibilă/stivă:
16 MB/1 MB

Micul Gigel se joacă cu N turnuri, fiecare turn fiind format din unul sau mai multe cuburi aşezate unul peste altul. Pentru fiecare turn se defineşte înălţimea lui ca fiind numărul de cuburi care îl formează. Pentru a-i transforma jocul într-o provocare intelectuală, învăţătoarea lui Gigel îi recomandă acestuia să aleagă exact K înălţimi standard şi să reconstruiască turnurile astfel încât noile lor înălţimi să se găsească printre înălţimile standard. Gigel ştie că pentru a elimina un cub dintr-un turn (micşorându-i astfel înălţimea cu o unitate) sau pentru a aşeza un cub la vârful turnului (mărindu-i înălţimea cu o unitate) are nevoie de un minut. Pentru că lucrul la un singur turn poate deveni monoton, Gigel doreşte să aleagă înălţimile standard astfel încât timpul maxim necesar pentru a modifica un turn sa fie cât mai mic posibil.

Cerinta

Scrieţi un program care să determine exact K înălţimi standard astfel încât timpul maxim necesar pentru a modifica un turn să fie minim posibil.

Date de intrare

Fişierul de intrare standard.in conţine pe prima linie două numere naturale N şi K, separate printr-un spaţiu, reprezentând numărul de turnuri şi respectiv numărul de înălţimi standard care trebuie alese. Cea de a doua linie conţine N numere naturale nenule în ordine strict crescătoare, separate prin câte un spaţiu, reprezentând înălţimile celor N turnuri.

Date de iesire

Fişierul de ieşire standard.out va conţine pe prima linie timpul maxim T necesar pentru a modifica un turn, pe cazul optim. Următoarea linie conţine K numere naturale, reprezentând înălţimile standard alese. Dacă sunt mai multe soluţii pentru acelaşi timp T se va afişa cea în care şirul înălţimilor este minim lexicografic.

Restrictii

  • 1 <= K <= N <= 100 000
  • Înălţimile turnurilor şi înălţimile standard vor fi numere naturale nenule mai mici de 2 miliarde
  • Înălţimile standard determinate trebuie să fie distincte două câte două
  • Înălţimile standard nu trebuie să se afle obligatoriu printre înălţimile iniţiale ale turnurilor
  • Spunem că şirul x = (x1 x2 … xk) este mai mic lexicografic decât şirul y = (y1 y2 … yk) dacă există un indice i, cu 1 <= i <= k, astfel încât xi < yi şi xj = yj, pentru orice 0 < j < i

Exemplu

standard.in standard.out Explicatie
6 2
5 7 9 16 20 31
6
10 25

La primul turn se vor adauga 5 cuburi.
La al doilea turn se vor adăuga 3 cuburi.
La al treilea turn se va adăuga 1 cub.
Din al patrulea turn se vor elimina 6 cuburi.
La al cincilea turn se vor adăuga 5 cuburi.
Din al şaselea turn se vor elimina 6 cuburi.


Filip Cristian Buruiana
stud. Facultatea de Automatica si Calculatoare, Universitatea Politehnica, Bucuresti
filipb2001@yahoo.com
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, 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, ic, echilibru, brazi, mat, cubinvers, mobil, distsir, parbit
De acelaşi autor: forum, lac, acop, volei, nori, simetric1, xor2
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Despre căutare binară: gropi, pod, uscat, checkin, 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, 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
surse trimise | ajutor