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

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


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

Ana a descoperit că are o adevărată pasiune pentru palindroame. Un şir de numere este palindrom dacă se citeşte la fel de la stânga la dreapta şi de la dreapta la stânga (primul număr este egal cu ultimul, al doilea cu penultimul etc). Ea are un şir cu N numere naturale şi vrea ca orice subsecvenţă de lungime impară a şirului să fie palindrom. Pentru a-şi îndeplini dorinţa ea poate efectua asupra şirului mai multe operaţii. O operaţie constă în alegerea unui element din şir şi incrementarea sau decrementarea lui cu o unitate. Bineînţeles, Ana doreşte să utilizeze un număr minim de operaţii pentru ca şirul obţinut să respecte proprietatea amintită mai sus (orice subsecvenţă de lungime impară să fie palindrom).

Cerinţă

Determinaţi pentru Ana numărul minim de operaţii pe care trebuie să-l efectueze pentru ca orice subsecvenţă de lungime impară a şirului obţinut în urma efectuării operaţiilor să fie palindrom. De asemenea aflaţi şi numărul de şiruri finale distincte pe care le poate obţine efectuând acest numar minim de operaţii.

Date de intrare

Fişierul de intrare palind.in va conţine pe prima linie numărul T, reprezentând numărul de seturi de date de intrare care urmează. În continuare urmează seturile de date de intrare, fiecare pe câte două linii. Pe prima linie a unui set de date se află numărul N, având semnificaţia din enunţ. Pe următoarea linie se află elementele şirului iniţial, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire palind.out va conţine T linii, pe linia i aflându-se două numere, reprezentând raspunsul pentru al i-lea set de date de intrare. Primul numar este numarul minim de operaţii, iar al doilea numărul de şiruri distincte finale care se pot obţine efectuând numărul minim de operaţii.

Restricţii

1 ≤ T ≤ 20
1 ≤ N ≤ 10.000
Elementele şirului sunt numere naturale din intervalul [1, 7.000].
Subsecvenţă a unui şir este un subşir de numere care apar pe poziţii consecutive.
Toate testele folosite la evaluare vor avea T = 20.
Pentru 20% din teste, 1 ≤ N ≤ 100
Pentru 20% din teste valoarea maximă din oricare şir este cel mult 500 şi N ≥ 101

Exemple

palind.inpalind.outExplicaţii
1 3 1 2 3 2 3 Pentru singurul test, cele trei şiruri posibile sunt:
1 2 1, 2 2 2 si 3 2 3.

autor: Stud. Adrian Airinei
propunător: Stud. Vlad Manea
Facultatea de Informatică
vlad.c.manea@gmail.com
Probleme recomandate
De la ONI 2008: ab2, iepuras, auto, div, teatru, pm, submat, reteta2, rezervatie, creioane, melci, mere2, felinare, joc3, 2numere, fi, tablou, borcane, mexc, tcast, dep, dist1, stiva, banda, pavare, poarta, aranjare, bile4, subgeom, albinuta1, curent, pviz, atac2, virus
De acelaşi autor: connect3, retea, auto, plopi, minuni, regat, kcons
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, 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, 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
Despre recurenţă: nrbun2, nrbun, grupe, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, maxq, cover, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, flori2, cntgcd, 2sah, matcnt, nmult
surse trimise | ajutor