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

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


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

După ce ai studiat problema subşirului crescător de lungime maximală, ai adăugat următoarea condiţie:
dacă există mai multe subşiruri crescătoare maximale, atunci se va alege acel subşir care are maximul diferenţelor în modul ale elementelor consecutive cât mai mic posibil.

Mai exact, dacă avem subşirul crescător: Ai1 Ai2 ... Aik atunci maximul diferenţelor este
max (Ai2 – Ai1, Ai3 – Ai2,  ... , Aik – Aik-1). Vom numi acest maxim cost al subşirului.

Cerinţă

Dat fiind un şir de numere, scrie un program care să determine lungimea unui subşir crescător maximal, precum şi costul minim al unui astfel de subşir.

Date de intrare

Fişierul de intrare subs.in va conţine pe prima linie numărul natural N, reprezentând numărul de elemente din şir. Pe a doua linie se află N numere naturale, separate prin spaţii, reprezentând elementele şirului.

Date de ieşire

Fişierul de ieşire subs.out va conţine o singură linie pe care se află două numere naturale separate printr-un spaţiu: lungimea subşirului crescător maximal, respectiv costul minim.

Restricţii

  • 1 ≤ N ≤ 30 000
  • Elementele şirului sunt numere naturale din intervalul [1, 1 000 000 000]
  • Pentru 40% din teste N ≤ 2500.

Exemplu

subs.in subs.out Explicatie
6
2 1 5 4 7 5
3 2

Subşirul crescător maximal căutat este: 2 4 5
Lungimea lui este: 3
Diferenţa maximă este: max (4 - 2, 5 – 4) = 2, care este minim posibilă.
Daca luăm subşirul 1 4 7 diferenţa maxima este 3, ceea ce nu este optim.


stud. Mircea Dima
Universitatea Bucureşti
blasterzm@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2010: greiere, divizori, kdist, pestera, partitie, sokoban, pitag, porumb, cheie, conferinta, chei, stelar, atelier, secv9, ny, radical, arbgraf, select, divk, bileprime, nx, reuniune, cazare, proiect, taler, atletism, echipa, ghinion, oldest, war, aliniere, sumb, cavaleri, joct, fluviu, camera616, aritm, stele, covor, subm, mess, secvnumber, cladire, ssmax, parcela, pion, universitate, el, mahjong, rotund, sirmax, bdotcom, pack
De acelaşi autor: votare, nkbiti, kperms, site, kbiti, kdist, oldest, mess, subsiruri
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, 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, 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
Despre arbori: bonuri, tgv, barfa, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, strict, tree, sub, kinder, firma1, albinuta, rlcs, masina, omizi, concurs1, latime, piloti, barca1, arbnr, sirag1, pikachu, arb, logn, maxq, arbore, bcast, mesaj1, traseu, asmax, salvare, tramvai1, omida, sediu, string, tv, izo, zoo, ratina, vitale, camion1, arbfind, cezar1, tcast, dep, curent, spp, frunze, sea2, culori, color, urgenta, nori, treegame, antipatie, scanduri, minuni, arb1, activ, regat, kdtree, autostrazi, carray, trenuri1, arbgraf, war, mess, secvnumber, posta, radare, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
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, standard, cantor, medalii, binperm, mobil, stalpi1, expo, miere, conferinta, pack, obstacole, dag, acoperire, verigi, bradut2, triburi, intervale, mijloc, patru, eliminare, vectori1, calcule, secvp, dreapta, colina, ssk, robotics, cabana
surse trimise | ajutor