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

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


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

Ovi este un băieţel foarte isteţ căruia îi place să scrie pe asfalt cu creta şi să ţopăie. El desenează cu cretă roşie un dreptunghi de lăţime exact 2 metri şi lungime N metri, pe care îl împarte în pătrate egale de latură 1 metru, unele laturi interioare fiind desenate cu cretă roşie, iar restul laturilor interioare cu cretă albă. Ovi porneşte din pătratul aflat în colţul stânga sus al dreptunghiului, sărind dintr-un pătrat în altul vecin pe linie sau coloană, cu condiţia ca latura care desparte cele două pătrate să nu fie colorată în roşu. El îşi doreşte ca prin sărituri succesive să ajungă în toate pătratele dreptunghiului, dar a observat că numai pentru anumite variante de colorare a laturilor pătratelor reuşeşte acest lucru.
În exemplele de mai jos (cu N=2) liniile interioare îngroşate sunt colorate cu roşu, iar cele punctate sunt colorate cu alb. La exemplul din fig. 1, pornind din colţul stânga sus se poate ajunge în oricare alt pătrat, dar în exemplul din fig. 2 nu se poate ajunge la pătratele din partea dreaptă.


Cerinţă

Ajutaţi-l pe Ovi să numere câte posibilităţi de colorare în roşu a unor laturi interioare ale pătratelor sunt astfel încât plecând din colţul stânga sus să poată ajunge prin sărituri în oricare alt pătrat.

Date de intrare

În fişierul patrate6.in se află un singur număr natural N ce reprezintă lungimea în metri a dreptunghiului.

Date de ieşire

În fişierul patrate6.out va conţine o singură linie pe care veţi scrie un singur număr natural ce reprezintă numărul de posibilităţi cerut.

Restricţii

2 <= N <= 1000

Exemple

patrate6.inpatrate6.outExplicaţii
2 5 Cele 5 posibilităţi sunt:



autor: Prof. Dan Pracsiu
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2004: cuvinte1, gaina, materom, puncte3, rez, sortari, base3, coach, color, magic5, turnuri, invsort, peri, trans, politie, sea, poligon3, sir7, poligon2, logic, coduri, snipers, sablon1, submdisj, v, jetoane, prodmax, printesa, palindrom, reziston
De acelaşi autor: cai, rebus, harta, comun, axa, sir, ocean14, reduceri, div3, 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, maxbin, 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 numere mari: fib, 2sir, test, sort, gray, siruri, vecini, div, sir2, nrcuv2, scor, hanoig, red, matrice3, pavaj, depou, pm, sqr, set, albine, teatru1, descfib, tub, m01, soldati1, euclid, mutare, munte1, bifo, banda10, sg1, cutii, zumzi, numere7, trapez, muguri, impozit, kbiti, m4, numar3, parbit, petrecere, randomizare, radical, ghinion, aliniere, sumb, cavaleri, camera616, numar4, pavari, asfalt, rotund, cos, risipa, xpn, dale, codpatrat, culori1, plus, minm, pomi, cifrab, subsets, doitrei, conjectura, ech, inventie
Despre recurenţă: nrbun2, nrbun, grupe, palind, 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, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, 2ndesc, flori2, cntgcd, 2sah, matcnt, nmult
surse trimise | ajutor