#1153
VerifNrParCifreDivImp
Se dă un şir cu n
elemente, numere naturale. Folosind metoda Divide et Impera să se verifice dacă toate elementele şirului au număr par de cifre.
#1152
VerificareOrdonatDivImp
Se dă un vector cu n
elemente numere naturale. Folosind metoda Divide et Impera să se verifice dacă are elementele ordonate crescător.
#1151
VerifEgaleDivImp
Se dă un vector cu n
elemente numere naturale. Folosind metoda Divide et Impera să se verifice dacă toate elementele vectorului sunt egale.
#1150
VerifPareDivImp
Se dă un şir cu n
elemente, numere naturale. Folosind metoda Divide et Impera să se verifice dacă toate elementele şirului sunt pare.
#1149
ExistaPrimeDivImp
Se dă un şir cu n
elemente, numere naturale. Folosind metoda Divide et Impera să se verifice dacă în șir există elemente prime.
#1148
ExistaImpareDivImp
Se dă un şir cu n
elemente, numere naturale. Folosind metoda Divide et Impera să se verifice dacă în şir există elemente impare.
#1114
Stiva1
Olivius d’Info a primit de ziua lui o stivă şi s-a bucurat foarte tare. S-a tot gândit ce să facă cu ea şi a inventat un joc de logică pentru colegii lui de clasă.
În prima fază el a scris mai multe bileţele, conţinând fiecare câte o permutare a primelor n
numere naturale nenule: 1
, 2
, 3
, … , n
. Bileţelele scrise conţin permutări pentru diferite valori ale lui n
.
A clasificat aceste permutări în permutări stivuite şi permutări nestivuite.
O permutare este stivuită dacă se poate obţine pe parcursul introducerii în stivă a numerelor 1, 2, 3, ...,n
în această ordine, prin extragerea elementelor, în ordinea indicată în permutare.
O permutare nestivuită este o permutare care NU se poate obţine prin procedeul de mai sus.
Respectând procedeul lui Olivius, pentru n=4
, permutarea stivuită (2,1,3,4)
se obţine astfel:
Succesiunile (3,1,2,4)
şi (4,2,1,3)
sunt permutări nestivuite.
În faza a doua, unele bileţele au fost scurtate din stânga şi/sau din dreapta. Astfel, din permutarea stivuită (2,1,3,4)
se pot obţine succesiuni de lungime mai mică: (1,3,4)
, (2,1,3)
, (1,3)
, (3)
etc.
Orice succesiune care aparţine unei permutări stivuite, poate aparţine şi unei permutări nestivuite. De exemplu, succesiunea (2,1,3)
aparţine atât permutării stivuite (2,1,3,4)
, cât şi permutării nestivuite (4,2,1,3)
.
Dându-se mai multe succesiuni de numere naturale distincte, determinaţi, pentru fiecare dintre acestea, dacă aparţin cel puţin unei permutări stivuite.
ONI 2014, Clasa a X-a
#1113
Rascoala
Suleiman I s-a confruntat în anul 1548 cu mari probleme interne. În acel an, el a primit vestea că într-una din regiunile Imperiului se pregăteşte o răscoală. Harta Imperiului este realizată sub forma unui tablou bidimensional cu n
linii şi m
coloane, iar fiecare element al tabloului corespunde unei regiuni a Imperiului. În fiecare regiune erau deja cantonaţi soldaţi, dar pentru a preîntâmpina răscoala sultanul decide ca toţi cei k
soldaţi din Garda Imperială să fie trimişi în regiuni, întărindu-le pe cele păzite de mai puţini soldaţi. Distribuirea lor respectă următoarele reguli:
Suleiman continuă distribuirea soldaţilor din garda imperială în regiuni conform celor precizate anterior, până la epuizarea soldaţilor din Garda Imperială.
Cunoscându-se n
, m
şi k
reprezentând numărul de linii, numărul de coloane, respectiv numărul de soldaţi din Garda Imperială, precum şi numărul de soldaţi existent deja în regiunile Imperiului, să se determine:
a) numărul de regiuni din Imperiu în care vor fi trimişi soldaţii din Garda Imperială, respectiv numărul minim de soldaţi care se vor găsi într-o regiune, după trimiterea soldaţilor din Garda Imperială;
b) distanța maximă între două regiuni în care au fost trimiși soldaţi ai Gărzii Imperiale. Distanța între o regiune A
și o regiune B
se calculează folosind formula |LA- LB| + |CA- CB|
, unde (LA ,CA)
reprezintă coordonatele regiunii A
, precizate prin numărul liniei și coloanei, respectiv (LB ,CB)
reprezintă coordonatele regiunii B
, precizate prin numărul liniei și coloanei.
ONI 2014, Clasa a X-a
#1112
Puteri4
Nu e un secret pentru nimeni faptul că Mireluş se antrenează în timpul liber cu probleme de algoritmică. De curând a aflat că un număr natural N
, pentru care există două numere naturale nenule A
şi B
(B>1
) astfel încât N = A^B
, se numeşte putere. Mireluş şi-a propus să determine numărul de puteri din intervalul [X, Y]
, unde X
şi Y
sunt numere naturale nenule.
Cum probabil v-aţi imaginat deja, Mireluş nu a reuşit să rezolve această problemă şi a decis să ceară ajutorul Olimpiei D’Info. Pentru a fi sigur că nici ea nu greşeşte, i-a dat un set de intervale şi i-a cerut să determine pentru fiecare interval numărul de puteri corespunzător.
Dându-se numărul de intervale T
şi pentru fiecare din cele T
intervale cele două extremităţi, determinaţi numărul de puteri corespunzător fiecărui interval dat de Mireluş Olimpiei.
ONI 2014, Clasa a X-a
#1111
Zimeria
Olimpia D’Info a găsit o placă gravată ce conţine mai multe cuvinte scrise cu semne grafice necunoscute, fiecare cuvânt fiind format din exact 5
semne grafice. Studiind cu atenție cuvintele, a dedus că în scrierea acestora sunt utilizate 12
semne grafice distincte şi a asociat câte o literă mică din alfabetul englez fiecărui semn. După asociere, a stabilit pentru fiecare semn o complexitate, scriind literele în ordinea crescătoare a complexităților pe care le-a stabilit anterior. Olimpia consideră că această ”complexitate” este cel mai potrivit criteriu de ordonare lexicografică.
Cunoscând ordinea semnelor și cuvintele de pe placă determinaţi:
a) Numărul de cuvinte distincte existente pe placă.
b) Şirul de cuvinte ordonat lexicografic, conform criteriului formulat de Olimpia.
ONI 2014, Clasa a X-a