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

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


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

Adevăratul câstigător al finalei .campion este cel care trece de ultima probă la care sunteţi supuşi de Balaurul Arhirel.
Balaurul vă dă un şir binar (numere 0 sau 1) şi o operaţie. Operaţia constă în alegerea unui element al şirului şi transformarea sa într-un element identic cu cel aflat imediat în stânga lui. Evident că nu ne putem alege primul element, pentru că acesta nu are nimic în stânga lui. Până la urmă tot şirul va avea toate elementele egale cu primul element.
Balaurului i-ar fi plăcut o confruntare directă cu voi, în care să vă măsuraţi puterile într-un joc în care cel care nu va mai avea ce muta pierde, însă îşi dă seama că nu aţi fi avut nici o şansă, iar lui îi place să existe un adevărat învingător.
Astfel vă cere doar numărul de şiruri distincte ce se pot obţine prin această operaţie, aplicată de 0 sau mai multe ori şirului iniţial.

Cerinţă

Aflaţi care este numărul de şiruri distincte ce se pot obţine.

Date de intrare

Pe prima linie a fişierului ivv.in se află un număr natural N reprezentând lungimea şirului. Pe următoarea linie se află N cifre binare, separate de câte un spaţiu, reprezentând şirul iniţial.

Date de ieşire

Fişierul de ieşire ivv.out va conţine o linie cu un singur număr întreg, şi anume numărul de şiruri distincte ce se pot obţine din şirul iniţial.

Restricţii

1 < N < 10 001
Câştigătorul este totuşi cel care obţine cele mai multe puncte în total, însă în ochii balaurului adevăratul câştigător este cel care trece de proba sa.

Exemple

ivv.inivv.outExplicaţii
5 0 1 1 0 0 10 Cele 10 şiruri sunt
0 1 1 0 0, 0 1 1 1 0, 0 1 1 1 1, 0 0 1 1 1,
0 0 0 1 1, 0 0 0 0 1, 0 0 0 0 0, 0 0 1 1 0,
0 0 1 0 0, 0 0 0 1 0

autor: Marius Andrei
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la Finala .campion 2005: barca1, peste, camion, kalah, algola
De acelaşi autor: conflicte, cadere, leaves, na, distanta, aparitii, tabara1, stop, hanoi, logn, cuburi1, viteza, masina3, anticip, cabane, spp, regine, comoara2, perle, cuvinte1, sortari, triti
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, 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
surse trimise | ajutor