Lista de probleme 663

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#718 Sah2

Mihai a primit de ziua sa un joc de şah special. Tabla jocului are forma pătrată, de dimensiune N dar unele poziţii sunt marcate ca obstacole şi ele nu pot fi ocupate cu piese. În plus, jocul său are o singură piesă, numită “nebun”. Două poziţii pe tablă sunt desemnate ca poziţie iniţială şi poziţie finală. Mihai vrea să determine o modalitate de a deplasa nebunul, cu un număr minim de mutări, astfel încât acesta să ajungă din poziţia iniţială în poziţia finală. Mihai va respecta regulile de mutare a nebunului la jocul de şah, adică din poziţia curentă nebunul se poate muta doar pe diagonală, în oricare dintre cele 4 direcţii, oricâte poziţii deodată dar fără a sări peste obstacole. În plus, Mihai are voie la o excepţie de la această regulă: îi este permis să execute cel mult două mutări după regula de avansare a calului pe tabla de şah.

Dată fiind configuraţia tablei de şah precum şi poziţiile iniţială şi finală ale piesei, se cere determinarea numărului minim de mutări pentru a deplasa piesa între cele două poziţii.

Lot Juniori, Resita, 2012

Miriapodul Verone trăieşte cel mult 12 luni, dar nu este nefericit, întrucât viaţa i se pare lungă şi frumoasă. I se spune Verone deoarece corpul său cilindric este alcătuit din segmente colorate, iar fiecare segment poate avea doar una dintre culorile: verde, roşu sau negru.

În prima lună de viaţă, corpul miriapodului este format dintr-un singur segment. În fiecare dintre lunile următoare, fiecare segment s creşte în lungime şi se divide în trei segmente: s1, s2 şi s3. Segmentele s1 şi s3 păstrează culoarea segmentului s, în vreme ce segmentul s2, cel din mijloc, se colorează astfel: dacă s era verde, atunci s2 devine roşu. Dacă s era roşu, atunci s2 devine negru. Dacă s era negru, atunci s2 devine verde.

Cineva a găsit un fragment dintr-un asemenea miriapod, rezultat în urma unei lupte fatale pentru miriapod, cu o altă vieţuitoare.

Cunoscând culoarea unicului segment în prima lună de viaţă a miriapodului şi succesiunea de culori a fragmentului găsit, scrieţi un program care determină vârsta acestuia şi succesiunea de culori a tuturor segmentelor sale înainte de începerea luptei.

Lot Juniori, Botosani, 2012

Gigel se lupta cu ardoare, în jocul primit în vacanţa de Paşti, cu fel şi fel de balauri. Într-una din zile a întâlnit un balaur care nu putea fi răpus cu nici una din armele obişnuite. Lur Ualab, căci aşa îl chema pe balaur, putea fi învins numai dacă cineva reuşea să îi rezolve ghicitoarea.

În fiecare luptă Lur Ualab îi dă lui Gigel un şir foarte lung format doar din litere mici ale alfabetului englez. Gigel trebuie să şteargă toate apariţiile, mai puţin una a fiecărei litere, astfel încât în şirul final obţinut să rămână toate literele distincte din şirul dat. La final, Gigel trebuie să îi dea lui Lur Ualab cel mai mic şir, din punct de vedere lexicografic, ce se poate obţine din şirul primit de el.

Scrieţi un program care să determine cel mai mic şir, din punct de vedere lexicografic, ce se poate obţine dintr-un şir dat, aplicând toate operaţiile de ştergere necesare.

Irinei îi plac numerele naturale. Ea știe că orice număr natural cu cifre nenule se poate reprezenta ca un șir de cifre din mulțimea A={1, 2,..., 9}. Irina își alege o cifră k şi îşi propune să afle câte numere naturale au suma cifrelor egală cu un număr dat S și în același timp se reprezintă folosind doar cifre din mulţimea {1, 2,..., k}.

Dându-se S şi k, se cere să se determine ultima cifră a numărului de numere naturale care se reprezintă doar cu cifre din mulțimea {1,...,k} și au suma cifrelor egală cu S.

#700 Labir

Şoricelul Jerry este (pentru a câta oară ?) în labirint. Labirintul poate fi codificat ca o matrice cu n linii şi m coloane formată din n*m celule pătratice identice. Liniile se numerotează de la 1 la n, iar coloanele de la 1 la m. Labirintul este format din celule libere şi din celule ocupate de pereţii labirintului.

La momentul iniţial, Jerry se găseşte într-o anumită celulă liberă şi misiunea lui este să ajungă la destinaţie într-o altă celulă liberă precizată. Șoricelul se poate deplasa din celula curentă în oricare dintre cele patru celule cu care aceasta are în comun o latură şi nu poate ieşi în afara labirintului. Este posibil ca el să nu poată să ajungă de la poziţia iniţială la cea finală trecând doar prin celule libere. În această situație el este nevoit să sfărâme peretele în anumite celule. Jerry şi-a pregătit dinamită în acest scop, pentru că nu i se pare optim să roadă peretele cu dinţii.

Cunoscând dimensiunile n şi m ale labirintului, coordonatele celulei de plecare şi ale celulei destinaţie, precum şi coordonatele celulelor ocupate de pereţi, să se determine numărul minim de celule ocupate, pe care Jerry trebuie să le dinamiteze pentru a putea să ajungă la destinaţie.

Lot Juniori, Deva, 2013

Se consideră N intervale [Ai,Bi], 1 ≤ i ≤ N disjuncte.

Tuturor intervalelor li se aplică o operație de extindere la ambele capete cu o valoare naturală x, astfel încât după extindere cu valoarea x, intervalul [Ai,Bi] va deveni intervalul [Ai-x,Bi+x], 1 ≤ i ≤ N.

După extindere, spunem că intervalele [Ai,Bi] și [Aj,Bj] aparțin aceluiași grup de intervale dacă ele se intersectează sau dacă există un interval [Ak,Bk] astfel încât [Ai,Bi] se intersectează cu [Ak,Bk] iar intervalele [Ak,Bk], [Aj,Bj] aparțin aceluiași grup de intervale.

Să se determine valoarea minimă x cu care vor trebui să fie extinse toate intervalele astfel încât să se formeze un grup cu cel puțin P intervale.

Se dă un șir de N numere distincte a[1],a[2],..a[N]. Orice secvență
a[i],a[i+1],...,a[j-1],a[j], 1 ≤ i + 1 < j ≤ n, pentru care toate valorile a[k],
i < k < j, sunt mai mici decât extremitățile a[i] și a[j], o vom numi în continuare “groapă”.

Scrieţi un program care va determina numărul “gropilor” din șirul dat.

#696 Mario

Jocurile cu Mario sunt jocuri on-line pentru copii de toate vârstele. Acum, Mario-personajul din joc, are nevoie de ajutorul vostru pentru a ajunge din turnul castelului unde se află, la sol, unde îl așteaptă cu nerăbdare prințesa Peach.

Coborârea din turn se face cu ajutorul unor platforme orizontale, de diferite lungimi, fiecare dintre ele aflându-se la o anumită înălțime față de sol. Deplasarea din turn spre sol se va face astfel:

  • Mario își dă drumul în cădere liberă din turn și cade sub efectul greutății sale;
  • dacă în cădere, el ajunge pe o platformă, se va deplasa pe suprafața acesteia spre unul din capetele din stânga sau din dreapta ale acesteia, urmând ca de acolo să procedeze la fel, lăsându-se din nou în cădere liberă spre sol.

Dacă Mario cade pe o distanță mai mare decât H, atunci își pierde toată energia și nu mai poate continua jocul.

Cunoscând poziția în care se află Mario și modul de așezare al platformelor (date în coordonate carteziene), determinați numărul drumurilor distincte pe care le poate parcurge Mario pentru a ajunge la prințesă.

Lot Juniori, Deva, 2013

Undeva, în deșertul Sahara, ilustrul biolog Sahraa Gaea a conceput și construit un sistem de irigații ingenios, sistem cu care își propune să irige o zonă deșertică dreptunghiulară bogată în nutrienți minerali. Zona deșertică este împărțită în N*M pătrate de latură unitate. În fiecare pătrat se află un dispozitiv de picurare ce asigură o anumită cantitate de apă în funcție de comanda primită de la centrul de control al sistemului.

Sistemul de irigare este astfel conceput încât să irige (ude), pe baza unor comenzi automatizate, parcele dreptunghiulare ale regiunii deșertice.

Orice parcelă are laturile paralele cu laturile zonei deșertice și este identificată prin coordonatele colțurilor stânga-sus (x1,y1), respectiv dreapta-jos (x2,y2). La fiecare comandă se specifică parcela care va fi udată și cantitatea de apă (exprimată în litri) cu care va fi irigat fiecare pătrat al acesteia.

Un pătrat al zonei deșertice devine fertil dacă acumulează cel puțin Q litri de apă.

Să se determine aria maximă a unei suprafețe conexe fertile. Prin aria unei suprafețe înțelegem numărul de pătrate ce compun suprafața. Orice două pătrate fertile care au o latură comună fac parte din aceeaşi suprafaţă conexă fertilă.

#688 pixy

Pixy locuieşte într-o ţară colorată. Harta ţării poate fi reprezentată sub forma unui dreptunghi împărţit în celule, organizate în M linii şi N coloane. Liniile sunt numerotate de la 1 la M, începând de la linia de sus, iar coloanele sunt numerotate de la 1 la N începând de la coloana din stânga. Fiecare celulă are o anumită culoare. Culorile sunt codificate cu literele A, B, C, D, E, F (există doar 6 culori).

Casa lui Pixy se găseşte în celula de coordinate (1,1), iar prietena lui, Pixela, locuieşte în celula de coordonate (M,N). Pixy doreşte să ajungă la aleasa inimii sale, însă nu poate păşi decât pe celule de aceeaşi culoare. Ştim că Pixy se poate deplasa doar orizontal, sau vertical cu câte o căsuţă la fiecare pas.

Pentru a putea ajunge la Pixela, Pixy va proceda astfel: alege o culoare şi va recolora celula în care se găseşte casa sa cu culoarea aleasă. Astfel va obţine o zonă de celule adiacente având toate aceeaşi culoare. Două celule se consideră adiacente dacă se învecinează orizontal sau vertical. De exemplu, pentru harta din figura 1, dacă alege culoarea având codul D va obţine zona marcată din figura 2, toate celulele din această zonă având culoarea D.

În continuare Pixy va proceda asemănător: alege o nouă culoare, şi recolorează toată zona obţinută la pasul anterior cu noua culoare, astfel zona pe care poate păşi se lărgeşte. De exemplu, dacă în situaţia din figura 2, Pixy alege acum culoarea cu codul C va obţine situaţia din figura 3.

Procedeul continuă până când celula corespunzătoare casei Pixelei face şi ea parte din zona obţinută de Pixy în urma recolorărilor.

Alegerea culorilor de la fiecare pas trebuie făcută cu mare grijă, astfel încât numărul de recolorări să fie minim.

Acum lui Pixy îi mai rămâne sarcina de a găsi un drum cât mai scurt pe care îl va parcurge până la Pixela, păşind doar pe celulele din zona obţinută în urma recolorărilor succesive, adică celulele de pe parcursul drumului vor avea toate aceeaşi culoare.

Se cere să determinaţi:

a) numărul minim de recolorări
b) lungimea drumului minim de la Pixy la Pixela, parcurs pe zona obţinută în urma recolorărilor de la cerinţa a).

Lot Juniori, Sibiu 2011