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

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


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

Se consideră un şir a1, a2, ..., aN de valori binare şi de asemenea se consideră un număr natural K. În şir, unei singure secvenţe de K elemente i se va aplica o transformare astfel încât oricărei componente din această secvenţă i se inversează valoarea (adică 0 devine 1 şi 1 devine 0). De exemplu, considerând şirul 0 0 1 1 0 1 0 0 1 1 1 0 şi K=3, se poate obţine şirul 0 1 0 0 0 1 0 0 1 1 1 0 (dacă secvenţa de lungime 3 aleasă începe la poziţia 2), sau se poate obţine 0 0 1 1 0 0 1 1 1 1 1 0 (dacă secvenţa de lungime 3 aleasă începe la poziţia 6). Poziţia de început P a secvenţei de lungime K se va alege astfel încât întreaga secvenţă să fie în interiorul şirului, adică P <= N – K + 1.

Cerinţă

Scrieţi un program care determină o poziţie P din şir unde se aplică o transformare astfel încât în şirul rezultat să existe o secvenţă de lungime maximă formată doar cu valori de 1. Dacă există mai multe astfel de poziţii P, se alege aceea de indice minim.

Date de intrare

Fişierul de intrare maxbin.in conţine pe prima linie numerele naturale N şi K separate printr-un spaţiu. Pe linia a doua sunt N numere naturale (doar 0 şi 1) separate prin câte un spaţiu, reprezentând elementele şirului.

Date de ieşire

Fişierul de ieşire maxbin.out va conţine pe prima alinie două numere naturale L şi P separate prin spaţiu. L va reprezenta lungimea maximă a unei secvenţe din şir formată doar din valori de 1 după aplicarea transformării, iar P reprezintă poziţia de început a secvenţei de lungime K unde se aplică transformarea.

Restricţii

  • 1 <= K < N <= 100 000
  • Poziţia unde se poate aplica transformarea este în intervalul [1, N–K+1]
  • Prin secvenţă se înţelege o succesiune de elemente aflate pe poziţii alăturate din şir

Exemplu

maxbin.in maxbin.out Explicaţii
12 3
0 0 1 1 0 1 0 0 1 1 1 0
5 6
Se aplică transformarea de lungime 3 începând cu poziţia 6 şi se obţine şirul
0 0 1 1 0 0 1 1 1 1 1 0.
În acest şir lungimea maximă a unei secvenţe formată doar cu valori de 1 este 5.
prof. Dan Pracsiu
Grupul Scolar "Stefan Procopiu" Vaslui
dpracsiu@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2011: ore, pegals, valet, xpn, efect, nrperm, b2k, sumdivprod, nr0, maxviz, oneton, oras1, ksecv, ripstick, antic, oak, nor, nrpomi, sumprod, paisprezece, cover1, prisme, gxor, progresii, anagramabil, zuma, nrpal, sdmin, lista, operatii1, codarb, codpatrat, adprod, puncte4, qtri, reconst, gsm, subsiruri, mijloc, trifoi, cubulete, romb, albine2, probleme, triburi1, megascoala
De acelaşi autor: cai, rebus, harta, comun, axa, sir, ocean14, reduceri, div3, patrate6, vot, reziduu, accesibil, predecesor, permutari, scanduri, ordonare, xor1, paltrei, triunghi1, 123, traseu1, parbit, petrecere, secvbiti, subm, triunghi3, cmmdcsecv, drumuri1, fillmat, secvb, siruri3, acces, segmente, echilibru1, broscute, ksecv, paisprezece, proddiv, perechi2, expeval, maxtri, combcuv, dfs, qtri, blis, probleme, divider, eliminare, minm, genab, grafxy, matd3, azeval, matrixdel, speed, maxp, split, binremove, sminus, subsets, tcif, sprime, sir2dif, ecp, arbsum, robotzi, permtr, unudoi, matcnt, ssdj, dominant
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, 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 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, meteo1, galbeni, maxp, secvp, split, secvente2, ausoara, sminus, munte3, cool, betisoare, unudoi, charlie, lasere, arc, dominant, restaurare, roua
surse trimise | ajutor