#1156
InaltimiQ
Se dau înălțimile a n
copii, numerotați de la 1
la n
, exprimate prin numere naturale. Afișați numerele de ordine ale copiilor în ordinea crescătoare a înălțimii lor.
Pentru sortare se va folosit metoda QuickSort sau MergeSort.
#1154
CautareDivImp
Se dă un vector x
cu n
elemente numere naturale, și un vector y
cu m
elemente, de asemenea numere naturale. Folosind metoda Divide et Impera, verificați pentru fiecare element al vectorului y
dacă apare în x
.
#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