#1110
Spion1
Spionul 008 vrea să găsească o locație secretă în junglă, având asupra lui un dispozitiv de localizare. Iniţial spionul se află la intrarea în junglă pe nivelul 1
şi cu fiecare pas, el avansează de la nivelul i
la nivelul i+1
, ajungând la locaţia secretă, aflată pe ultimul nivel, în poziţia u
faţă de marginea stângă a nivelului curent. Pentru a ajunge în locaţia secretă, el poate să se deplaseze cu o poziţie spre Sud-Est (codificat cu caracterul E
) sau spre Sud-Vest (codificat cu caracterul V
), trecând de pe nivelul i
pe nivelul i+1
cu viteză constantă. Numărul de poziţii de pe un nivel creşte cu unu faţă de nivelul anterior, conform imaginii alăturate. Numim traseu o succesiune formată din caracterele E
sau V
, corespunzătoare deplasării spionului de pe nivelul 1
la locaţia secretă. Pentru exemplul din figura alăturată succesiunea de caractere VEEVE
reprezintă un traseu ce corespunde locaţiei secrete din poziţia 4
a nivelului 6
.
Cunoscând succesiunea de caractere corespunzătoare unui traseu, determinaţi:
a) poziţia locației secrete de pe ultimul nivel;
b) numărul de trasee distincte pe care le poate urma spionul plecând din poziţia inițială pentru a ajunge în locaţia secretă corespunzătoare traseului dat. Două trasee se consideră distincte dacă diferă prin cel puţin o poziţie.
ONI 2014, Clasa a X-a
#1109
Joc5
Costel are o mare pasiune pentru rezolvarea cubului Rubik, atât de mare încât a început să facă cercetări și calcule diverse pornind de la acest joc. Ultima lui idee, inspirată de cubul Rubik, folosește un cub de latură 2
unități, compus din 8
cuburi cu latura de o unitate (cub unitate), având fețele exterioare colorate. Fiecare cub unitate are 3
fețe exterioare şi fiecare dintre acestea este colorată cu una din cele 10
culori disponibile, codificate prin cifrele de la 0
la 9
.
Figura 1 | Figura 2 |
Identificarea cuburilor unitate se face conform specificaţiilor din Figura 1. Cubul care nu este vizibil în Figura 1 are coordonatele (1, 1, 2)
. Cubul lui Costel permite efectuarea următoarelor tipuri de mutări, asemănătoare cu cele din cubul Rubik:
M1: Paralelipipedul 1 conține cuburile unitate de coordonate: (1, 1, 1) ; (1, 2, 1) ; (2, 1, 1) ; (2, 2, 1) . Acesta este un disc așezat orizontal și poate fi rotit cu 90 de grade către dreapta, în sensul acelor de ceasornic.
| |
M2: Paralelipipedul 2 conține cuburile unitate de coordonate: (1, 1, 2) ; (1, 2, 2) ; (2, 1, 2); (2, 2, 2) . Acesta este un disc așezat orizontal și poate fi rotit cu 90 de grade către dreapta, în sens invers acelor de ceasornic.
| |
M3: Paralelipipedul 3 conține cuburile unitate de coordonate: (1, 1, 1) ; (2, 1, 1) ; (1, 1, 2) ; (2, 1, 2) . Acesta este un disc așezat vertical și poate fi rotit cu 90 de grade către planul îndepărtat, în sens invers acelor de ceasornic.
| |
M4: Paralelipipedul 4 conține cuburile unitate de coordonate: (1, 2, 1); (2, 2, 1); (1, 2, 2); (2, 2, 2). Acesta este un disc așezat vertical și poate fi rotit cu 90 de grade către planul îndepărtat, în sensul acelor de ceasornic.
|
Prin configurație se înțelege memorarea culorii fiecărei fețe exterioare a celor 8
cuburi unitate, deci culorile celor 24
de feţe exterioare. Aplicând o succesiune validă de mutări se obține o altă configurație.
Pentru ușurința memorării unei configurații, Costel utilizează desfășurarea în plan a celor 6
fețe ale cubului său după modelul din Figura 2, care ilustrează modul în care sunt dispuse fețele în desfăşurare. Fiecare faţă a cubului conţine patru feţe exterioare ale cuburilor unitate având, în ordine, coordonatele specificate în figură.
Fiind date o configuraţie iniţială şi o configuraţie finală ale jocului, determinați numărul minim de mutări prin care se poate ajunge de la configurația inițială la configurația finală şi succesiunea corespunzătoare de mutări prin care se poate obţine configuraţia finală.
ONI 2014, Clasa a X-a
#1108
Traseu
Într-un oraș există un hotel de formă cubică, cu N
etaje, numerotate de la 1
la N
. Suprafața fiecărui etaj K
(1 ≤ K ≤ N
) este pătratică și este împărțită în N x N
camere identice alăturate, dispuse pe N
linii și N
coloane, fiecare cameră având drept etichetă un triplet de numere naturale (K L C
) (K=
etajul, L=
linia, C=
coloana, 1 ≤ L, C ≤ N
), ca în imaginea alăturată.
Dintre cele N x N x N
camere ale hotelului, una este specială deoarece în ea locuiește de mult timp un șoricel. Fiind isteț, el știe eticheta camerei în care se află precum și eticheta camerei în care bucătarul hotelului depozitează alimente.
Studiind hotelul, șoricelul a constatat că pe fiecare etaj, din orice cameră poate intra în toate camerele care au un perete comun cu aceasta (existând un mic orificiu pentru aerisire).
De asemenea, șoricelul a constatat că din fiecare cameră (situată la etajele 2
, 3
, …, sau N-1
) poate intra în camera situată imediat deasupra ei și în camera situată imediat sub ea.
Fiind un șoricel binecrescut, el nu intră în nicio cameră ocupată de clienți ca să nu-i deranjeze. Hotelul având mulți clienți, șoricelul trebuie să-și găsească cel mai scurt traseu de la camera lui la camera cu alimente, traseu care să treacă printr-un număr minim de camere, toate neocupate.
Se cere să se determine:
a) numărul de camere prin care trece cel mai scurt traseu al șoricelului de la camera lui la camera cu alimente (inclusiv camera lui şi camera cu alimente);
b) etichetele camerelor prin care trece traseul determinat la punctul a).
ONI 2014, Clasa a IX-a
#1029
Triunghi2
Gigel este un pasionat al triunghiurilor. El colectează beţişoare de diferite lungimi şi le asamblează în diferite triunghiuri. Ieri, el avea 6 beţişoare de lungimi 5, 2, 7, 3, 12
şi 3
. Din aceste bețișoare, Gigel a construit un triunghi de laturi 3, 3
şi 5
, iar beţişoarele de lungimi 2, 7, 12
au rămas nefolosite pentru că aceste lungimi nu pot forma laturile unui triunghi.
Din acest motiv, Gigel s-a hotărât să facă o colecţie de beţişoare, dintre care oricum ar alege 3
elemente, acestea să nu poată forma laturile unui triunghi, proprietate pe care o vom numi în continuare proprietate anti-triunghi. Gigel, pornind de la setul iniţial de lungimi 2, 7, 12,
s-a gândit la două metode de realizare a unei colecţii de 5
beţişoare cu proprietatea anti-triunghi, şi anume:
1.Păstrează cel mai scurt beţişor, cel de lungime 2
, şi creează un set nou adăugând alte beţişoare de lungime mai mare sau egală cu cel iniţial. De exemplu, următoarele 5
lungimi sunt corecte: 2, 2, 12, 50, 30
.
2.Păstreză toate beţişoarele, şi anume 2, 7,12,
pe care le va completa cu alte beţişoare de diferite lungimi (mai scurte sau mai lungi), astfel ca proprietatea anti-triunghi să se păstreze. Următoarele 5
lungimi respectă proprietatea anti-triunghi: 2, 7, 12, 4, 1.
Cunoscând un şir de n numere naturale nenule a 1 ,a 2 ,…,a n având proprietatea
anti-triunghi, şi un număr k (k>n)
, se cere să construiţi un şir de k
numere naturale având proprietatea anti-triunghi, în conformitate cu una dintre următoarele două restricţii:
Varianta 1. Cel mai mic element este identic cu cel mai mic element din şirul iniţial.
Varianta 2. Printre cele k
elemente ale şirului construit se regăsesc toate elementele şirului iniţial.
OJI 2014, Clasa a X-a
#1028
Ferma
Un fermier deține o fermă de formă dreptunghiulară cu lungimea m
metri și lățimea n
metri. Respectând principiul rotației culturilor, fermierul și a realizat un plan pentru semănarea culturilor în noul an. Astfel ,el a desenat un dreptunghi pe care l-a împărțit în m * n
celule, fiecare corespunzând unui metru pătrat, și a colorat în culori diferite zonele care corespund unor culturi diferite. O cultură poate fi semănată pe mai multe parcele. Două celule care au o latură comună aparțin aceleiași parcele dacă au aceeași culoare (sunt însămânțate cu aceeași cultură). Fermierul are posibilitatea să irige o sigură parcelă și dorește să aleagă parcela cu cea mai mare suprafață. Nefiind mulțumit de suprafața rezultată, s-a întrebat dacă ar putea schimba cultura de pe o singură celulă, astfel încât să obțină o parcelă de suprafață mai mare.
Dându-se dimensiunile fermei și pentru fiecare celulă culoarea corespunzătoare culturii semănate, determinați:
OJI 2014, Clasa a X-a
#1091
Expozitie
Ilinca este o fetiţă căreia îi place foarte mult să deseneze; ea a făcut multe desene pe care le-a numerotat de la 1
la d
şi apoi le-a multiplicat (toate copiile poartă acelaşi număr ca şi originalul după care au fost făcute). În vacanţă s-a hotărât să-şi deschidă propria expoziţie pe gardul bunicilor care are mai multe scânduri; pe fiecare scândură ea aşează o planşă (un desen original sau o copie). Ilinca ţine foarte mult la desenele ei şi doreşte ca fiecare desen să apară de cel puţin k
ori (folosind originalul şi copiile acestuia). Ilinca se întreabă în câte moduri ar putea aranja expoziţia. Două moduri de aranjare sunt considerate distincte dacă diferă cel puţin prin numărul unei planşe (de exemplu: 2 1 3 3
este aceeaşi expoziţie ca şi 2 3 1 3
, dar este diferită de 2 1 3 1
şi de 1 3 3 1
).
Cunoscând n
numărul de scânduri din gard, d
numărul desenelor originale şi k
numărul minim de apariţii al fiecărui desen, să se determine în câte moduri poate fi aranjată expoziţia, ştiind că Ilinca are la dispoziţie oricâte copii doreşte.
OJI 2010, Clasa a X-a
#1087
Cuvinte4
Se consideră un şir de cuvinte separate două câte două printr-un spaţiu. Fiecare cuvânt este caracterizat prin numărul de ordine care reprezintă poziţia lui în şirul de cuvinte (primul cuvânt are numărul de ordine 1
). Unui cuvânt i se pot aplica în mod repetat următoarele transformări: primul caracter al cuvântului (cel mai din stânga) se şterge de acolo şi se adaugă după ultimul caracter din cuvânt. Astfel, dintr-un cuvânt s
cu k
caractere se pot obţine alte k-1
cuvinte pe care le numim cuvinte obţinute din transformarea cuvântului s
. De exemplu, dintr-un cuvânt format din 4
caractere c1c2c3c4
, cuvintele obţinute prin transformarea lui sunt: c2c3c4c1
, c3c4c1c2
, c4c1c2c3
.
Se caută în şirul de cuvinte prima pereche de cuvinte vecine (a,b)
, în care al doilea cuvânt din pereche (cuvântul b)
este identic cu un cuvânt obţinut din transformarea lui a
. Dacă există o astfel de pereche, se şterge cuvântul b
din şir. Prin ştergerea cuvântului b
din şir, acesta va avea mai puţin cu un cuvânt! Se repetă operaţia de căutare de mai sus până când în şirul rămas nu mai există o pereche (a,b)
de cuvinte vecine, astfel încât b
să fie obţinut prin transformarea lui a
.
Se ştie că pe parcursul modificărilor, cuvintele nu-şi schimbă numerele de ordine pe care le-au avut iniţial.
Scrieţi un program care să citească şirul de cuvinte şi să afişeze:
a) numărul de ordine al primului cuvânt şters sau valoarea 0
în cazul în care nu se şterge niciun cuvânt
b) numerele de ordine ale cuvintelor rămase după finalizarea operaţiilor de modificare.
OJI 2010, Clasa a VII-a
#1079
Comp
Locuitorii planetei Eudora folosesc o reprezentare mai ciudată a numerelor naturale, astfel că orice număr natural va fi scris notând câte mii, sute, zeci, respectiv unităţi conţine acesta. De exemplu, numărul 3207
se poate reprezenta în mai multe moduri echivalente: 3m2s7u
(3
mii 2
sute şi 7
unităţi), 32s0z7u
(32
sute 0
zeci şi 7
unităţi), 32s7u
, 3207u
, etc.
Pentru a compara două numere naturale, eudorienii folosesc semnele <
şi >
, acestea având semnificaţia cunoscută şi pe Terra, iar pentru a calcula suma a două numere naturale utilizează semnul +
.
Pentru a testa abilităţile pământenilor în privinţa lucrului cu numere naturale, eudorienii au trimis pe Terra un fişier text ce conţine N
linii, fiecare linie fiind o comparaţie de forma:
expresie1>expresie2
sau
expresie1<expresie2
Observaţi că o comparaţie este constituită din două expresii separate prin semnul <
sau prin semnul >
.
O expresie este compusă dintr-un număr natural sau dintr-o sumă de două sau mai multe numere naturale, toate scrise în forma eudoriană. Fişierul nu conţine caractere spaţiu.
Scrieţi un program care determină câte dintre comparaţiile date utilizează semnul <
, precum şi valoarea de adevăr a fiecărei comparaţii dintre cele N
date (afişând 0
dacă acea comparaţie e falsă, respectiv 1
dacă acea comparaţie e adevărată).
OJI 2011, Clasa a VIII-a
#1077
Litere
Algorel a primit un joc care conţine n
jetoane pe care sunt scrise litere mari ale alfabetului. Fiecare literă are asociat un cod format dintr-o singură cifră nenulă. Jetoanele se aşează în ordinea dată iniţial, iar prin citirea literelor de pe acestea, de la primul la ultimul jeton, se formează un cuvânt. Dacă se citesc numerele de pe fiecare jeton, începând de la primul la ultimul, se obţine un număr k
1
. Jocul continuă la fel, dar se aşează jetoanele începând de la al doilea la ultimul, obţinându-se un nou număr k
2
. Apoi, se aşează jetoanele începând de la al treilea la ultimul, obţinându-se un nou număr k
3
, ş.a.m.d. până se ajunge la aşezarea doar a ultimului jeton, caz în care se obţine numărul k
n
.
Scrieţi un program care citeşte numărul n
de jetoane, cele n
litere asociate jetoanelor, precum şi codurile asociate literelor, în ordinea apariţiei lor şi afişează:
a) numărul de perechi de litere consecutive din cuvântul iniţial care au proprietatea că o literă este vocală şi cealaltă este consoană (ordinea lor nu contează);
b) numărul k
1
, format din aşezarea iniţială a jetoanelor;
c) suma k
1
+k
2
+…+k
n
.
OJI 2011, Clasa a VII-a
#1067
Expresie7
Prin convenţie numim expresie aritmetică ponderată o expresie construită astfel:
2
cifre despărţite prin virgulă;k-șir
o enumerare de k
numere despărţite prin virgulă (k≥1
);k-şiruri
;Fiind dată o expresie aritmetică ponderată să se determine:
OJI 2011, Clasa a X-a