Lista de probleme

#686 grad

Se consideră o propoziţie formată din litere mici ale alfabetului englez şi eventual spaţii. Cuvintele sunt formate numai din litere şi sunt separate între ele prin unul sau mai multe spaţii.

Definim numărul asociat unui cuvânt c1c2...ck ca fiind un număr natural nc, obţinut ca produsul puterilor de forma pi, unde p este poziţia în alfabet a literei ci. Astfel cuvântului badab i se asociază numărul nc=21∙12∙43∙14∙25, adică nc=4096.

Definim gradul unui cuvânt c1c2...ck ca fiind numărul nr modulo k, unde nr este numărul de divizori al lui nc. Gradul cuvântului badab este 3, pentru că nr=13 (cei 13 divizori ai lui 4096 sunt: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 şi 4096), k=5 (cuvântul conţine 5 litere) şi 13 modulo 5=3.

Definim gradul unei propoziţii ca fiind suma gradelor cuvintelor existente în ea.

Să se scrie un program care pentru o propoziţie dată determină gradul ei.

Lot Juniori, Sibiu 2011

#687 liste

Numim listă un sir de numere naturale. Avem la dispoziţie mai multe liste aşezate, în ordine, una sub alta. Spunem că două liste L1 şi L2 sunt vecine dacă L1 este imediat deasupra lui L2, sau dacă L2 este imediat deasupra lui L1. Oricare două liste vecine L1 şi L2 pot fi unificate dacă ele au cel puţin un element comun. Prin unificare, noua listă va avea ca elemente toate elementele din L1 la care se adaugă toate elementele din L2. Listele L1 şi L2 vor dispărea şi în locul lor va apărea noua listă.

Determinaţi numărul minim de liste care rezultă după aplicarea unui număr suficient de unificări astfel încât să nu mai existe două liste vecine care să poată fi unificate.

Lot Juniori, Sibiu 2011

#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

#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

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.

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.

Lot Juniori, Deva, 2013

#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

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.

Lot Juniori, Deva, 2013

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.

Lot Juniori, Botosani, 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