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

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


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

Se consideră un şir cu N numere naturale a1, a2,…, aN. Asupra unui element ai, din şir, se pot efectua operaţii de incrementare (adunare cu 1: ai=ai+1) sau decrementare (scădere cu 1: ai=ai-1). Fiecare element din şir poate fi incrementat sau decrementat de oricâte ori.

Cerinţă

Dat fiind şirul celor N numere naturale, să se determine:
a. numărul total minim de operaţii necesare pentru a transforma toate numerele din şir în numere prime;
b. numărul minim de operaţii (incrementări şi decrementări) ce trebuie să fie efectuate asupra elementelor şirului astfel încât să existe o secvenţă de lungime K formată numai din numere prime.

Date de intrare

Fişierul de intrare secvp.in conţine pe prima linie numerele naturale N şi K, iar pe următoarea linie N numere naturale. Numerele scrise pe aceeaşi linie sunt separate prin spaţii.

Date de ieşire

Fişierul de ieşire secvp.out conţine pe prima linie un număr natural T, reprezentând numărul total minim de operaţii necesare pentru a transforma toate numerele din şir în numere prime. Pe a doua linie vor fi scrise două numere naturale separate prin spaţiu minK nrsK, unde minK reprezintă numărul minim de operaţii ce trebuie să fie efectuate asupra elementelor şirului astfel încât să existe o secvenţă de lungime K formată numai din numere prime, iar nrsK reprezintă numărul de secvenţe de lungime K care se pot obţine cu acelaşi număr minK de operaţii de incrementare/decrementare.

Restricţii

2 ≤ K ≤ N ≤ 100 000
0 ≤ ai ≤ 1 000 000, pentru 1≤i≤N
• O secvenţă din şir este formată din elemente aflate pe poziţii consecutive în şirul dat.
1 nu este număr prim.
• Pentru determinarea corectă a valorii T se acordă 30% din punctajul pe test. Pentru determinarea corectă a valorilor T şi minK se acordă 70% din punctajul pe test. Punctajul integral se acordă pentru determinarea corectă a tuturor celor 3 valori.

Exemple

secvp.insecvp.outExplicaţii
7 3 15 3 8 26 22 10 14 9 3 2 Pentru a transforma 15 în număr prim sunt necesare 2 incrementări
Pentru a transforma 3 în număr prim sunt necesare 0 operaţii
Pentru a transforma 8 în număr prim e necesară 1 decrementare
Pentru a transforma 26 în număr prim sunt necesare 3 decrementări
Pentru a transforma 22 în număr prim e necesară 1 incrementare
Pentru a transforma 10 în număr prim e necesară 1 incrementare
Pentru a transforma 14 în număr prim e necesară 1 decrementare
Numărul total de operaţii necesare este 9.
Numărul minim de operaţii necesare pentru a obţine o secvenţă de lungime K este 3. Cele două secvenţe de lungime K ce necesită 3 operaţii sunt a1, a2, a3 şi a5, a6, a7.

autor: Prof. Eugen Nodea
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONIGIM 2013: cursa1, patrate7, latin, swap, zmax, extraprime, greieri, onigim, divizori1, remi1, tetris3, amestec, sudoku1, eoliene
De acelaşi autor: expresie1, tsunami, antic, nor, compresie, gheizere, poly, unific, cool, qvect, charlie, robotics
Despre divizibilitate: celule, cai, trei, ruleta, an, factori, perechi, anagrame, axa, perspic, scara, programs, iepuras2, fry, policefm, turist, kfactor, cuc, prime, sqr, evaluare, factk, div3, divizor, euclid, stop, matricea, mutare, viteza, ingerasi, prieteni, robinson, romeo, perechi1, sume1, fact, tzigla, cifru2, elfi, vraji, desen2, exponent, trapez, resturi, exp1, ron, spirala1, gardul, tort, poligon3, sume2, smith, biliard, printesa, secvente1, ultime4, padure, multiplu1, 235, iepurasi, numar3, cmmmc, randomizare, divizori, pitag, bileprime, pin, canguri, numar4, jocprim, covor, nivfractie, cmmdcsecv, ai, grupe2, numerus, sport2, fagure, grad2, sumdivprod, oak, sumprod, paisprezece, numere10, proddiv, puncte4, trifoi, cartier, alune, intersectii, divider, minm, numere11, prodnr, boltz, vistiernic, extraprime, divizori1, cumpanit, cntgcd, nrdiv, numere12, daruri, imprimanta, puteri, reflex, tg, sprime, diferenta, concurs4, vapoare, inventie, prime2
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, standard, 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, 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 secvenţe: degrade, hora, simetric, egal, ruleta, ecran, sirag, pasi, firma, br, numere2, termen, div, teatru, repeat, ratb, 2sec, sport, pikachu, suma3, panouri, sir5, mare, hof, resturi, efort, xor1, livada1, diff, popic, guess, albine1, permutare, miere, atelier, obstacole, echilibru1, lcdr, 3max, ksecv, maxbin, meteo1, galbeni, maxp, split, secvente2, ausoara, sminus, munte3, cool, betisoare, unudoi, charlie, lasere, arc, dominant, restaurare, roua
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, subs, pack, obstacole, dag, acoperire, verigi, bradut2, triburi, intervale, mijloc, patru, eliminare, vectori1, calcule, dreapta, colina, ssk, robotics, cabana
Chestionare recomandate
surse trimise | ajutor