Nivelul concursului: Județean
http://olimpiada.info/oji2013/
Grupe
Clasa a V-a Clasa a VI-a Clasa VII-a Clasa VIII-a Clasa a IX-a Clasa a X-a Clasele XI-XII#1038
Zona2
Ionuţ pleacă în drumeţie într-o porţiune de teren de formă pătratică cu latura de N
metri. O hartă a zonei are trasat un caroiaj care împarte zona în N*N
pătrate unitate, cu latura de 1
metru. Astfel harta zonei are aspectul unui tablou pătratic cu N
linii şi N
coloane. Liniile şi coloanele sunt numerotate de la 1
la N
. Elementele tabloului bidimensional corespund pătratelor unitate. Zona poate fi parcursă străbătând oricare dintre laturile pătratelor unitate cel mult o singură dată.
Ionuţ pleacă din punctul aflat în colţul din dreapta jos al pătratului unitate din linia X
, coloana Y
şi se deplasează făcând un pas (parcurgând o latură a unui pătrat unitate) în una din direcţiile Nord, Est, Sud, Vest. Pentru a reţine mai uşor traseul foloseşte următoarea codificare pentru cele 4
direcţii: 1
pentru deplasarea spre Nord, 2
pentru deplasarea spre Est, 3
pentru deplasarea spre Sud, respectiv 4
pentru deplasarea spre Vest.
Ajuns într-alt punct (colţ de pătrat unitate), Ionuţ continuă să se deplaseze fără a trece de mai multe ori pe aceeaşi latură a unui pătrat unitate.
Ionuţ se opreşte în momentul în care ajunge într-un punct prin care a mai trecut. Traseul străbătut între cele două treceri prin acelaşi punct delimitează o zonă de teren formată din pătrate unitate.
Dându-se linia X
şi coloana Y
corespunzătoare poziţiei de plecare a lui Ionuţ, dimensiunea zonei N
, lungimea traseului L
şi traseul determinaţi:
a) Numărul de paşi parcurşi între prima şi a doua trecere prin punctul de oprire.
b) Numărul de pătrate unitate interioare zonei delimitată de traseul străbătut între cele două treceri prin acelaşi punct.
OJI 2013, clasa a X-a
#1037
Calcule
Gigel a studiat recent şirurile cu n
elemente, numere naturale. Pentru un astfel de şir S
, Gigel doreşte să afle răspunsul la întrebările:
a) Care este numărul minim de subşiruri strict crescătoare în care se poate partiţiona S
?
b) Care este numărul de secvenţe, modulo 20011
, cu suma elementelor divizibilă cu k
care se pot obţine din S
?
Dându-se un şir S
cu n
elemente numere naturale şi un număr natural k
se cere să se răspundă la cele două întrebări.
OJI 2013, clasa a X-a
#1042
Subsecvente
Fie n
un număr natural și M={S
1
,S
2
,…,S
n
}
o mulțime de șiruri de caractere nevide. Fie S
k
un șir de caractere din M
. Atunci, orice caracter al lui S
k
aparține mulțimii {'a','b'}
. Notăm prin |S
k
|
numărul caracterelor șirului S
k
sau, echivalent, lungimea sa. O subsecvență S
k
[i:j]
a lui S
k
este formată din caracterele situate pe pozițiile consecutive i, i+1, .., j
. Astfel, dacă S
k
= 'abbbaababa'
, atunci S
k
[3:6] = 'bbaa'
sau subsecvența evidențiată: 'ab
bbaa
baba'
.
Fiind dată o mulțime M
, se cere să se determine lungimea maximă a unei subsecvențe care se găsește în toate șirurile din M
.
OJI 2013, clasele XI-XII
#1041
Biperm
Pentru un număr natural nenul n
, să considerăm toate numerele naturale nenule mai mici sau egale cu n
, luând fiecare număr de câte două ori: 1, 1, 2, 2, 3, 3, ... , n, n
. Aceste numere le amestecăm aleator, şi le aranjăm pe două linii a câte n
elemente. Structura astfel obţinută o vom numi o bipermutare. În figurile 1, 2 şi 3 avem câte un exemplu de bipermutare pentru n=5
.
O bipermutare este perfectă, dacă ambele linii ale structurii reprezintă câte o permutare (vezi figurile 2 şi 3).
Prin mutare pe poziţia p
, înţelegem interschimbarea elementelor de pe aceeaşi coloană p
. În exemplele de mai jos, bipermutarea perfectă din figura 2 s-a obţinut din bipermutarea din figura 1, aplicând o mutare pe poziţa 2
. Bipermutarea perfectă din figura 3 s-a obţinut din bipermutarea din figura 1, aplicând mutări pe poziţiile 1
, 2
, 4
şi 5
.
Cunoscând o bipermutare, determinaţi:
OJI 2013, clasele XI-XII