#1099
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:
R
;G
;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ț.
OJI 2009, Clasa a X-a
#1621
În Orașul Liniștit un număr de k
tineri prieteni doresc să participe la un miting de protest. Deoarece cartierul în care locuiesc aceștia este mare, ei se vor deplasa spre punctul de întâlnire cu mașinile personale. Fiecare tânăr va aduce cu el o pancartă, pe care a desenat o singură literă din mulțimea A ... Z
. Nu există două pancarte cu litere identice. Cele k
litere formează un cuvânt, să-l notăm cuv
, cunoscut.
Cartierul în care locuiesc tinerii poate fi codificat printr-o matrice cu n*m
zone pătratice, dintre care unele sunt interzise. Se știe că o mașină consumă o unitate de combustibil la trecerea dintr-o zonă în zona vecină și nu consumă combustibil dacă staționează. Două zone sunt vecine dacă au în comun o latură. Pentru a face economie de combustibil, tinerii decid că dacă două mașini se întâlnesc într-o zonă și toate literele aflate în cele două mașini reprezintă o secvență din cuvântul cuv
, atunci ei vor continua drumul cu o singură mașină, luând desigur toate pancartele cu ei. În caz contrar, mașinile își continuă drumul separat.
De exemplu, dacă cuvântul cuv
este JOS
, atunci mașina care transportă litera J
poate prelua tânărul care aduce pancarta cu litera O
, sau invers: mașina având litera O
poate prelua tânărul care aduce litera J
. Apoi se poate continua drumul spre mașina care transportă litera S
. În altă variantă se pot reuni mai întâi literele S
și O
într-o singură mașină, dacă mașinile care le transportau se întâlnesc în aceeași zonă. Totuși, între mașina care transportă doar litera J
și cea care transportă doar litera S
nu se poate realiza un transfer, adică o reunire a literelor.
Cunoscând dimensiunile cartierului n
și m
, cuvântul cuv
, configurația cartierului și pozițiile inițiale ale tinerilor, se cere:
OJI 2016, Clasa a X-a
#1761
Renumitul nostru brutar a avut azi noapte un vis tare ciudat: acesta trăia într-un univers paralel în care nu omul îl mănâncă pe blat ci blatul îl mănâncă pe om… (eh, poate nu chiar atât de paralel). Astfel, brutarul nostru a fost atacat de blatul pe care tocmai îl pregătise (pentru prăjituri, evident) și a încercat să scape. Acesta a ieșit din brutărie și a ajuns în fața unui câmp de formă dreptunghiulară, cu dimensiunile cunoscute, ce poate fi împărțit în celule elementare cu latura de o unitate (exact ca o matrice!). Acesta poate intra pe câmp prin orice celulă a primei linii și trebuie să ajungă în orice celulă a ultimei linii (blatul se va întări până va ajunge acolo). Unele celule îi sunt inaccesibile din cauza diverselor obstacole (pietre, pomi, gropi,etc.)
Brutarul nostru se poate deplasa în 6
moduri:
Nord
, Vest
, Sud
, Est
)Mutările speciale vor fi citite din fișier și o mutare se va codifica astfel: xA yB
, unde x
și y
sunt numere naturale nenule iar A
și B
sunt două caractere ce codifică direcția (A
poate fi 'N'
sau 'S'
de la Nord
respectiv Sud
iar B
poate fi ‘E’
sau ‘V’
de la Est
respectiv Vest
)
O mutare specială se poate face dacă celula destinație nu este ocupată de un obstacol și dacă nu implică ieșirea brutarului din matrice.
Brutarul vă roagă să îi specificați un traseu cu număr minim de celule parcurse, ce pornește de pe prima linie și se termină pe ultima linie, pentru a nu fi blătuit (mâncat de blat).
Concursul EMPOWERSOFT, 2016
#628
Lui Andrei îi plac foarte mult jocurile de tip puzzle. De curând, el a descoperit un joc nou: un cub de dimensiune n
format din n•n•n
cuburi unitate sub forma unor cămăruţe. Cubul poate fi văzut ca o matrice tridimensionala ale cărei elemente sunt cămăruţele. Două cămăruţe se numesc adiacente dacă au o faţă comună. Astfel, o cămăruţă poate fi adiacentă cu maxim 6
cămăruţe. Scopul jocului este acela de a duce o bilă din cămăruţa de coordonate (1,1,1)
în cămăruţa de coordonate (n,n,n)
. Bila poate trece dintr-o cămăruţă în alta doar dacă acestea sunt adiacente, iar noua cămăruţă este accesibilă din cămăruţa curentă.
Cunoscând n
, dimensiunea cubului şi valorile asociate fiecărei cămăruţe, determinaţi:
a) cămăruța cu un număr maxim de cămăruțe ce pot fi accesate din ea;
b) un drum de lungime minimă de la cămăruţa (1,1,1)
la cămăruţa (n,n,n)
.
Grigore Moisil, 2014
#1998
NASA plănuiește o nouă misiune Rover pe Marte în anul 2020. Principalul obiectiv al acestei misiuni este de a determina, cu ajutorul unui nou Rover, dacă a existat în trecut viață pe Marte. Până când va fi lansată misiunea, Roverul este supus la tot felul de teste în laboratoarele NASA. Într-unul din teste, Roverul trebuie să parcurgă o suprafață de forma unui caroiaj cu N
linii și N
coloane. Acesta pornește din zona de coordonate (1,1)
și trebuie să ajungă în zona de coordonate (N,N)
, la fiecare pas putându-se deplasa din zona în care se află într-una din zonele învecinate la nord, sud, est sau vest. Pentru fiecare zonă de coordonate (i,j)
se cunoaște A[i,j]
, stabilitatea terenului din acea zonă. Știind că Roverul are o greutate G
, o zonă cu stabilitatea terenului cel puțin egală cu G
se consideră o zonă sigură pentru deplasarea Roverului, iar o zonă cu stabilitatea terenului mai mică decât G
se consideră o zonă periculoasă pentru Rover.
1. Determinați numărul minim posibil de zone periculoase pe care le traversează Roverul pentru a ajunge din zona (1,1)
în zona (N,N)
.
2. Determinați greutatea maximă pe care o poate avea un Rover care să ajungă din zona (1,1)
în zona (N,N)
, fără a traversa nicio zonă periculoasă pentru el.
OJI 2017, Clasa a X-a
#2184
Un schior profesionist se află pe un platou montan. Harta platoului este împărțită în n
rânduri (numerotate de la 1
la n
) a câte m
parcele (numerotate de la 1
la m
), fiecare parcelă reprezentând o zonă de teren de formă pătrată cu latura de 1
metru. Pe fiecare parcelă de pe hartă este scris un număr, ce reprezintă altitudinea parcelei respective. Schiorul se poate deplasa din parcela curentă în oricare din cele opt parcele învecinate (pe orizontală, verticală sau diagonală), cu condiția ca altitudinea noii parcele să fie mai mică sau egală cu altitudinea parcelei în care se afla anterior. Cunoscând coordonatele parcelei în care se află inițial schiorul, să se determine altitudinea minimă la care poate ajunge acesta.
Olimpiada Municipala de Informatica, Iasi, 2017
#4247
O zonă mlăştinoasă are formă dreptunghiulară, având L
linii (numerotate de la 1
la L
) şi C
coloane (numerotate de la 1
la C
). Ea este formată din celule cu latura de o unitate. O parte din acestea reprezintă uscat, iar altele reprezintă apă, uscatul fiind codificat cu 0
, iar apa cu 1
. Se doreşte să se obţină un drum de pe malul de nord spre cel de sud, trecând doar pe uscat. Deplasarea se poate face cu câte o celulă pe linie, pe coloană, sau pe diagonală. Celulele cu apă pot fi transformate în uscat, paraşutând într-un loc cu apă câte un ponton (o plută) de dimensiunea unei celule. Deoarece paraşutarea este periculoasă, se doreşte să avem un număr minim de paraşutări. Scrieţi un program care determină numărul minim de pontoane şi coordonatele acestora.
ONI 2002, clasa a X-a
#2894
Este anul 2019, dar Zmeul-Cel-Rău și Făt-Frumos luptă în continuare. Zmeul l-a prins pe Făt-Frumos şi l-a închis în una dintre camerele bârlogului său. Un bârlog de zmeu are forma unui tablou bidimensional, în care camerele sunt plasate sub forma a n
linii și m
coloane. Vom numerota liniile de la 1
la n
, iar coloanele de la 1
la m
, astfel că fiecare cameră poate fi identificată prin numărul liniei și al coloanei pe care se află.
Orice cameră are patru pereți și câte o ușă pe fiecare perete prin care poate comunica cu camerele învecinate. Mai exact, camera de pe linia i
și coloana j
poate comunica cu camerele (i-1,j)
, (i,j+1)
, (i+1,j)
, (i,j-1)
(desigur, dacă acestea există). Fiecare cameră are asociat un cod. Ușile din orice cameră se pot deschide cu o cartelă magnetică. Dacă codul camerei este un subșir al cuvântului memorat pe cartela magnetică, atunci ușile din camera respectivă se vor deschide folosind cartela. Ileana Cosânzeana a reușit să-i trimită lui Făt-Frumos o cartelă magnetică.
Scrieți un program care rezolvă următoarele două cerințe:
1. determină numărul de camere în care ar putea ajunge Făt-Frumos folosind cartela primită de la Ileana Cosânzeana;
2. determină numărul minim de camere prin care trece Făt-Frumos pentru a ieși din bârlogul zmeului (adică poate deschide ușa unei camere prin care ajunge în exteriorul bârlogului).
Olimpiada Municipală Iași, clasa a X-a
#2959
Tommy a descoperit bine-cunoscutul joc Minecraft, joc care este axat pe creativitate și construcție, permițând jucătorilor să construiască, folosind o multitudine de cuburi texturate, o lume tridimensională. Harta lumii lui Tommy este o suprafață pătrată, pe care sunt desenate pătrate egale, alăturate, ce pot fi albastre sau verzi. Fiecare pătrat albastru corespunde unui cub albastru și fiecare pătrat verde corespunde unui cub verde. Sursele de apă sunt reprezentate de pătrate de culoare albastră. Fiecare pătrat verde are atașat un cost, reprezentat de lungimea celui mai scurt drum până la o sursă de apă. Două pătrate alăturate aparțin aceluiași drum dacă au o latură comună. Drumul ajunge la o sursă de apă, dacă, ultimul pătrat de pe drum are o latură comună cu pătratul corespunzător sursei de apă. Lungimea drumului este reprezentată de numărul de pătrate care formează drumul. Costul unei suprafețe este reprezentat de suma costurilor pătratelor care formează suprafața.
Cunoscând harta ce corespunde lumii lui Tommy, să se determine:
Prosoft@NT Piatra Neamț 2019
#3056
N x M
. Analizând harta, WALL-E constată că are de-a face cu un labirint extrem de sofisticat. El reușește să identifice următoarele tipuri de celule:
W
– celula unde, la început, se află WALL-E,E
– celula ‘EXIT’ care poate fi accesată de WALL-E și care îl poate teleporta pe acesta instantaneu în afara labirintului, într-un loc sigur,.
– celule libere, care pot fi accesate de WALL-E,#
– celule de tip zid, care NU pot fi accesate de WALL-E,+
– celule de tip ușă, care pot fi accesate de WALL-E, dar continuarea deplasării la o celulă vecină se poate face doar după o așteptare de exact T
secunde,P
– celule de tip portal, care îl teleportează pe WALL-E instantaneu, la întâmplare, într-una dintre celelalte celule de tip portal. Dacă WALL-E accesează o celulă (x1, y1)
de tip portal, atunci el va fi instantaneu teleportat la o altă celulă (x2,y2)
de tip portal, iar mai departe el se va deplasa numai într-o celulă vecină cu (x2,y2)
(nu poate sta pe loc)Comportamentul haotic al portalurilor îl îngrijorează pe WALL-E, astfel că își propune să afle care este numărul minim de secunde în care, cu certitudine, el va putea părăsi labirintul. Dacă nu se poate determina cu certitudine acest lucru, sau dacă WALL-E nu poate părăsi labirintul, răspunsul va fi -1
.
ONI 2019 clasa a X-a