Lista de probleme 685

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#722 Cifru

Alibaba trebuie să descopere cifrul care deschide cufărul cu comoara cea mare. Cifrul este foarte greu de găsit. El a descoperit mai multe pietre, fiecare piatră având o altă culoare, pe fiecare piatră fiind scris un număr natural cu cel mult 4 cifre. Alibaba observă că numerele de pe fiecare piatră sunt distincte două câte două. Regula după care se formează cifrul este una foarte simplă, şi Alibaba a reuşit să o obţină destul de uşor: cifrul este format din alăturarea într-o anumită ordine a tuturor pietrelor. Ceea ce Alibaba mai ştie este că pe poziţia p din cifru se găseşte cu siguranţă cifra k.

Scrieţi un program care determină numărul de variante de cifruri pe care va trebui să le încerce Alibaba. Numărul fiind foarte mare se va calcula modulo 46337.

Lot Juniori, Focsani, 2010

#721 CD

Ionică a strâns foarte multe CD-uri cu jocuri, muzică, filme, etc. pe care le are aşezate în n cutii, codificate prin 1, 2, …, n. Pe la Ionică vine în vizită vărul lui, Florin, care tocmai câştigase un concurs de matematică. Ca să-i mai taie din elan, Ionică îi propune lui Florin să pună o parte din CD-uri într-o ladă mai mare, astfel încât să se ia din fiecare cutie cel puţin câte un CD şi la sfârşit să rămână în fiecare cutie cel puţin un CD.

Pentru a complica problema, Ionică nu îi spune lui Florin câte CD-uri sunt în fiecare cutie, ci îi spune că are în total S CD-uri şi că, dacă ia din fiecare cutie un număr de CD-uri şi le pune în altă cutie va obţine în final acelaşi număr de CD-uri în toate cutiile.

Să se scrie un program care cunoscând n, S şi numărul de CD-uri mutate din fiecare cutie, determină numărul k de modalităţi distincte de introducere a CD-urilor în ladă, respectând regula din enunţ.

Lot Juniori, Focsani, 2010

#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