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

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


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

Se consideră toate permutările de N elemente şi subprogramul:
subprogram caută(permutare, stânga, dreapta, căutat):
	dacă stânga ≤ dreapta atunci 
		mijloc ← |(stânga + dreapta) / 2|
		dacă permutare[mijloc] < căutat atunci
			caută(permutare, mijloc + 1, dreapta, căutat)
		altfel 
			dacă permutare[mijloc] > căutat atunci
				caută(permutare, stânga, mijloc – 1, căutat)
			altfel 
				s-a găsit căutat în permutare pe poziţia mijloc
	altfel
		nu s-a găsit căutat în permutare

Fie o permutare P de dimensiune N, un număr natural K şi apelul subprogramului de forma caută(P, 1, N, K).

Cerinţă

Pentru câte permutări de dimensiune N, apelul subprogramului nu duce la găsirea valorii K?

Date de intrare

Pe prima linie a fişierului de intrare binperm.in se găsesc, în această ordine, separate prin spaţiu, N şi K.

Date de ieşire

Pe prima linie a fişierului de ieşire binperm.out se găseşte restul împărţirii numărului la 1.000.003.

Restricţii şi precizări

  • Pentru 40% din teste, 1 <= K <= N < 1.000
  • Pentru 30% din teste, 1 <= K <= N < 10.000
  • Pentru 20% din teste, 1 <= K <= N < 100.000
  • Pentru 10% din teste, 1 <= K <= N <= 1.000.000
  • Prin |x| am notat partea întreagă a lui x

Exemplu

binperm.in binperm.out
4 3
 
10
 

Vlad Manea
Facultatea de Informatică Iaşi
vlad.c.manea@gmail.com
propunător: Administrator .campion
vlad.c.manea@gmail.com
Articole recomandate
Probleme recomandate
De la Festival Neamt 2009: strings, matrx, antipatie, ultime4, padure
De acelaşi autor: strings, matrx, centrala
Despre căutare binară: gropi, pod, uscat, checkin, copaci, aven, br, furtuna, livada, numar, matrice, sume, bacan, toys, chimie2, trafic, ants, multiplu, ghici, sirag1, tabara, puncte1, centru, harta1, salvare, spion, poze, dist1, patrate5, resturi, lanterna, sea2, vot, standard, cantor, medalii, mobil, stalpi1, expo, miere, conferinta, subs, pack, obstacole, dag, acoperire, verigi, bradut2, triburi, intervale, mijloc, patru, eliminare, vectori1, calcule, secvp, dreapta, colina, ssk, robotics, cabana
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, multiplu1, operatii, fotbal, kbiti, jucarii, bradut, expozitie, parbit, kmax, petrecere, 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
Software recomandat
De acelaşi autor: Algoritmul KMP
Chestionare recomandate
De acelaşi autor: Chestionar KMP
surse trimise | ajutor