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

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


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

Se organizează o petrecere la care participă N băieţi (numerotaţi de la 1 la N) şi N fete (numerotate de la 1 la N). S-a decis ca petrecerea să dureze mai multe minute. În fiecare minut fetele şi băieţii formează o configuraţie de dans, adică N perechi, după una dintre următoarele reguli:
1. băiatul i dansează cu fata i;
2. băiatul i dansează cu fata j şi atunci obligatoriu băiatul j dansează cu fata i.
De exemplu, pentru N=7, două configuraţii de dans posibile sunt:
(1, 1) (2, 2) (3, 7)(4, 5) (5, 4) (6, 6) (7, 3)
(1, 1) (2, 2) (3, 3)(4, 5) (5, 4) (6, 6) (7, 7)
Prin perechea (i,j) s-a notat faptul că băiatul i dansează cu fata j. Două configuraţii sunt distincte dacă ele diferă prin cel puţin o pereche.

Cerinţă

Ştiind că în fiecare minut trebuie formate configuraţii de dans distincte, să se determine câte minute durează petrecerea.

Date de intrare

Fişierul de intrare petrecere.in conţine pe prima linie un singur număr natural N.

Date de ieşire

Fişierul de ieşire petrecere.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând durata în minute a petrecerii.

Restricţii

1 ≤ N ≤ 2000
Răspunsul este un număr natural de maximum 3000 de cifre.
Pentru 20% din teste, vom avea N ≤ 11.
Pentru alte 20% din teste, rezultatul poate fi reprezentat pe 64 de biţi cu semn.

Exemple

petrecere.inpetrecere.outExplicaţii
2 2 Configuraţiile de dans sunt:
(1,1) (2,2)
(1,2) (2,1)
3 4 Configuraţiile de dans sunt:
(1,1) (2,2) (3,3)
(1,1) (2,3) (3,2)
(1,2) (2,1) (3,3)
(1,3) (2,2) (3,1)


autor: Prof. Dan Pracsiu
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2010: diff, kmax, minuni, stalpi1, submatrix1, dreptunghiuri, gaz, xp, triunghi2, cmmmc, simetric1, cern, pesti, plaja, tango, arb1, v2d, xor2, cuiburi, telefon, teroristi
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, 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 combinatorică: manevre, carti, bonuri, test, cub, nspecial, circuit, numere, cs, pluricex, parent, gray, siruri, anagrame, party, net, scaune, sir, monede, aztec, nrcuv2, perm, race, hanoig, red, grup, hperm, depou, grazing, pm, reteta2, playlist, young, pizza1, albine, caramele, teatru1, tub, robot1, sir23, soldati1, concurs1, comb, expresii, arbnr, cod1, munte, shgraf, desc, lex, munte1, maxperm, role, avere, vizibil, prime1, hexa, patrat, carti2, puncte2, pact, aranjari, numere5, borg, acolor, sg1, perfect, cifru2, bile4, pviz, culmi1, piramida1, trapez, frunze, sir7, logic, coduri, jetoane, kperms, tablite, secvpar, lego, permutari, binperm, multiplu1, operatii, fotbal, kbiti, jucarii, bradut, expozitie, parbit, kmax, tango, rege, cd1, cifru3, kcons, bubblesort, hawaii, randomizare, kdist, reuniune, echipa, ghinion, cavaleri, camera616, covor, subm, grupuri, pavari, asfalt, adunscad, rotund, sport2, arbore1, lant1, module, nrperm, oneton, nrpomi, cover1, nrpal, probleme, optim, poly, vot1, sudoku1, flori2, xnumere, showroom, cntgcd, subsets, nkd, nrgraf, spion1, puteri, stiva1, permtr, relatii, 2sah, matcnt, magic7, nmult, roua
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, patrate6, muguri, impozit, kbiti, m4, numar3, parbit, 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, patrate6, kperms, jump, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, 2ndesc, flori2, cntgcd, 2sah, matcnt, nmult
surse trimise | ajutor