Lista de probleme 91

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#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).

#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ă.

#1220 Scadere

Fie n un număr natural nenul.

Să considerăm o expresie de forma: x[1]-x[2]-x[3]-...-x[n]

Se ştie că scăderea nu este o operaţie asociativă, adică x[1]-(x[2]-x[3])≠(x[1]-x[2])-x[3].

Ca urmare, prin plasarea unor perechi de paranteze în expresie, putem obţine diferite valori.
Pentru problema noastră, vom denumi scădere o expresie de forma de mai sus în care pot apărea şi paranteze rotunde care se închid corect. Valoarea unei scăderi se obţine efectuând operaţiile de scădere în ordine de la stânga la dreapta; dacă apar paranteze, se efectuează mai întâi operaţiile din paranteze.

Date fiind valorile x[1], x[2], …, x[n] care intervin în scădere, scrieţi un program care să rezolve următoarele două cerinţe:

  1. să se determine valoarea maximă a unei scăderi (obţinută prin inserarea convenabilă a unor paranteze rotunde în expresia x[1]-x[2]-x[3]-...-x[n]), precum şi o scădere având valoare maximă.
  2. să se determine valoarea unei scăderi specificate.

ONI GIM 2015, Clasa a VII-a

#2167 alee

Parcul oraşului a fost neglijat mult timp, astfel că acum toate aleile sunt distruse. Prin urmare, anul acesta Primăria şi-a propus să facă reamenajări. Parcul are forma unui pătrat cu latura de n metri și este înconjurat de un gard care are exact două porți. Proiectanții de la Primărie au realizat o hartă a parcului și au trasat pe hartă un caroiaj care împarte parcul în nxn zone pătrate cu latura de 1 metru. Astfel harta parcului are aspectul unei matrice pătratice cu n linii și n coloane. Liniile și respectiv coloanele sunt numerotate de la 1 la n. Elementele matricei corespund zonelor pătrate de latură 1 metru. O astfel de zonă poate să conțină un copac sau este liberă. Edilii orașului doresc să paveze cu un număr minim de dale pătrate cu latura de 1 metru zonele libere (fără copaci) ale parcului, astfel încât să se obțină o alee continuă de la o poartă la alta. Scrieți un program care să determine numărul minim de dale necesare pentru construirea unei alei continue de la o poartă la cealaltă.

#1099 Insule

Arhipelagul RGB este format din insule care aparţin ţărilor R, G şi B. Putem reprezenta harta arhipelagului ca o matrice cu n linii şi m coloane cu elemente din mulţimea {0, 1, 2, 3}. Un element egal cu 0 reprezintă o zonă acoperită de apă; un element egal cu 1 reprezintă o zonă de pământ aparţinând unei insule din ţara R, iar un element egal cu 2 reprezintă o zonă de pământ aparţinând unei insule din ţara G, iar un element egal cu 3 reprezintă o zonă de pământ aparţinând unei insule din ţara B.

Se consideră că două elemente ale matricei sunt vecine dacă ele au aceeaşi valoare şi fie sunt consecutive pe linie, fie sunt consecutive pe coloană. Două elemente aparţin aceleiaşi insule dacă ele sunt vecine sau dacă se poate ajunge de la un element la celălalt pe un drum de-a lungul căruia oricare două elemente consecutive sunt vecine.

Pentru a încuraja relaţiile de colaborare dintre ţările R şi G, se doreşte construirea unui pod care să unească o insulă aparţinând ţării R de o insulă aparţinând ţării G. Podul trebuie să respecte următoarele condiţii:

  • să înceapă pe o zonă cu apă consecutivă pe linie sau coloană cu o zonă aparţinând ţării R;
  • să se termine pe o zonă cu apă consecutivă pe linie sau coloană cu o zonă aparţinând ţării G;
  • să traverseze numai zone acoperite cu apă;
  • oricare două elemente consecutive ale podului trebuie să fie vecine;
  • lungimea podului să fie minimă (lungimea podului este egală cu numărul de elemente traversate de pod).

Dată fiind harta arhipelagului să se determine câte insule aparţin fiecărei ţări, precum şi lungimea minimă a unui pod care să satisfacă condiţiile din enunț.

#1066 AI

Institutul Naţional de Robotică Avansată realizează o serie de teste ultimei generaţii de roboţi inteligenţi proiectaţi de specialiştii acestuia. Sistemul de testare se bazează pe o reţea de senzori formată din n segmente egale dispuse orizontal şi n segmente egale dispuse vertical. Distanţa între două segmente alăturate orizontale, respectiv verticale este de 1 metru. Fiecare segment orizontal este în contact cu fiecare segment vertical. Denumim nod un punct în care un segment orizontal şi unul vertical vin în contact. Segmentele sunt numerotate: cele orizontale de sus în jos începând de la 1 iar cele verticale de la stânga la dreapta începând de la 1.

Un nod va fi identificat prin două numere: primul reprezintă numărul segmentului orizontal iar al doilea numărul segmentului vertical care vin în contact în respectivul nod.

Într-unul dintre nodurile reţelei se află o ţintă. În alte două noduri se află câte o sursă ce emite o rază laser. O astfel de sursă emite raza într-o singură direcţie. Raza laser are o grosime neglijabilă. Cele două surse sunt astfel orientate încât raza emisă de fiecare “loveşte” ţinta. Cele două noduri în care sunt plasate sursele sunt astfel alese încât cele două raze nu se intersectează decât în nodul unde se află ţinta.

În alte două noduri ale reţelei se află câte un robot. Fiecare robot se poate deplasa dintr-un nod în cele vecine (cele aflate sus, jos, în stânga şi în dreapta), dar fără să iasă din cadrul reţelei. Roboţii se deplasează cu 1 m/secundă.

Se efectuează experimente în care roboţii sunt programaţi să se deplaseze prin reţea cu scopul de a proteja ţinta faţă de cele două raze laser. Un robot poate proteja ţinta fie ocupând nodul unde se află sursa, fie ocupând un nod prin care trece raza laser în drumul de la sursă către ţintă (razele laser nu “ocolesc” roboţii). Dimensiunea roboţilor este atât de mică încât, în acest al doilea caz, ei protejează ţinta faţă de raza laser doar când nodurile unde sunt sursa, ţinta şi robotul sunt coliniare iar robotul este între sursă şi ţintă. În momentul în care un robot ajunge într-un nod unde protejează ţinta faţă de una dintre raze, el se poate opri sau poate să îşi continue deplasarea. Dacă îşi continuă deplasarea astfel încât noua poziţie ocupată de acel robot şi poziţiile ţintei şi sursei nu mai sunt coliniare, atunci acel robot nu mai protejează ţinta. Din modul în care sunt alese poziţiile nodurilor pentru ţintă şi sursele laser rezultă că nu există nicio poziţie în care un robot să protejeze simultan ţinta faţă de ambele raze.

Fiecare robot este dotat cu o reţea neuronală şi poate învăţa din experimentele anterioare pe unde să se deplaseze. Pentru a mări capacitatea de adaptare a roboţilor, în k noduri ale reţelei sunt aşezate obstacole care fac ca roboţii să nu poată trece prin nodurile respective. Deoarece obstacolele folosite sunt transparente, razele laser pot trece prin acestea fără a le fi afectată intensitatea sau direcţia. Două sau mai multe obstacole dispuse pe acelaşi segment, în noduri alăturate, formează un zid. Lungimea unui zid este egală cu numărul de obstacole din care este alcătuit.

Cerințe:

1) Determinaţi lungimea maximă a unui zid.
2) Determinaţi numărul minim de secunde în care cei doi roboţi pot proteja ţinta faţă de cele două raze laser.

OJI 2011, Clasa a X-a

#1056 Unific

Se consideră un şir A=(A1, A2, ..., AN), format din N numere naturale nenule. Două numere se consideră vecine dacă se află pe poziţii alăturate (Ai are ca vecini pe Ai-1 şi Ai+1, pentru orice 1<i<N, A1 are ca vecin doar pe A2, iar AN are ca vecin doar pe AN-1).

Dacă două elemente vecine Ai, Ai+1 (1≤i<N) au cel puţin o cifră comună, ele se pot unifica. Procedeul de unificare constă în eliminarea din numerele Ai şi Ai+1 a tuturor cifrelor comune şi adăugarea prin alipirea numărului obţinut din Ai+1 la numărul obţinut din Ai, formându-se astfel un nou număr. Numărul Ai va fi înlocuit cu noul număr, iar numărul Ai+1 va fi eliminat din şir.

De exemplu, numerele Ai=23814 şi Ai+1=40273 au cifrele 2, 3, 4 comune, după unificare obţinem Ai=817, iar Ai+1 este eliminat; observaţi că dacă după eliminarea cifrelor comune, numerele încep cu zerouri nesemnificative, acestea vor fi eliminate, apoi se realizează alipirea.

Dacă în urma eliminării cifrelor comune, unul dintre numere nu mai are cifre, atunci numărul rezultat va avea cifrele rămase în celălalt. Dacă în urma eliminării cifrelor comune atât Ai cât şi Ai+1 nu mai au cifre, atunci ambele numere vor fi eliminate din şir, fără a fi înlocuite cu o altă valoare.

Ordinea în care se fac unificările în şir este importantă: la fiecare pas se alege prima pereche de elemente vecine Ai Ai+1 care poate fi unificată, considerând şirul parcurs de la stânga la dreapta. (De exemplu, considerând Ai=123, Ai+1=234, Ai+2=235, se unifică Ai cu Ai+1 => Ai=14, iar unificarea cu următorul număr nu mai este posibilă).

Cunoscându-se şirul celor N numere naturale, să se determine:

a) cifra care apare cel mai frecvent în scrierea tuturor celor N numere; dacă există mai multe cifre cu aceeaşi frecvenţă de apariţie maximă, se va reţine cea mai mică cifră.
b) şirul obţinut prin efectuarea unui număr maxim de unificări, după regulile descrise în enunţ.

#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

#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:

  • Cerința 1: Suprafața maximă a unei parcele în planul inițial.
  • Cerința 2: Numărul liniei, respectiv al coloanei celulei pe care va semăna o altă cultură și culoarea corespunzătoare noii culturi în vederea obţinerii celei mai mari parcele posibile.

OJI 2014, Clasa a X-a

#1133 Charlie

Charlie a decis să se joace cu literele dintr-un șir de caractere, șir ce conține doar literele mici ale alfabetului englez ’a’…’z’. Jocul constă în a elimina litere din șir după următoarea regulă: fie L1, L2, L3 trei litere aflate pe poziții consecutive în șir, atunci litera L2 poate fi eliminată dacă și numai dacă este strict mai mică lexicografic decât literele L1 și L3.

Pentru a face jocul mai interesant, Charlie atașează eliminării literei L2 un cost egal cu valoarea maximă dintre ō(L1) și ō(L3), unde prin ō(litera) înțelegem numărul de ordine al literei respective în alfabet (ō(’a’)=1, ō(’b’)=2,…, ō(’z’)=26). Charlie aplică în mod repetat procedeul de eliminare și calculează suma costurilor eliminărilor efectuate.

Fiind dat un șir de caractere să se determine:

a) Lungimea maximă a unei secvențe de litere alternante, adică o secvență pentru care literele aflate pe poziții consecutive sunt de forma: Li > Li+1 < Li+2 > Li+3 < Li+4 > … < Lj.
b) Suma maximă pe care o poate obține Charlie aplicând în mod repetat procedeul de eliminare a literelor, precum și șirul obținut în final.