Lista de probleme 93

Gigel a studiat recent şirurile cu n elemente, numere naturale. Pentru un astfel de şir S, Gigel doreşte să afle răspunsul la întrebările:

a) Care este numărul minim de subşiruri strict crescătoare în care se poate partiţiona S?
b) Care este numărul de secvenţe, modulo 20011, cu suma elementelor divizibilă cu k care se pot obţine din S?

Dându-se un şir S cu n elemente numere naturale şi un număr natural k se cere să se răspundă la cele două întrebări.

Gigel este un pasionat al triunghiurilor. El colectează beţişoare de diferite lungimi şi le asamblează în diferite triunghiuri. Ieri, el avea 6 beţişoare de lungimi 5, 2, 7, 3, 12 şi 3. Din aceste bețișoare, Gigel a construit un triunghi de laturi 3, 3 şi 5, iar beţişoarele de lungimi 2, 7, 12 au rămas nefolosite pentru că aceste lungimi nu pot forma laturile unui triunghi.
Din acest motiv, Gigel s-a hotărât să facă o colecţie de beţişoare, dintre care oricum ar alege 3 elemente, acestea să nu poată forma laturile unui triunghi, proprietate pe care o vom numi în continuare proprietate anti-triunghi. Gigel, pornind de la setul iniţial de lungimi 2, 7, 12, s-a gândit la două metode de realizare a unei colecţii de 5 beţişoare cu proprietatea anti-triunghi, şi anume:
1.Păstrează cel mai scurt beţişor, cel de lungime 2, şi creează un set nou adăugând alte beţişoare de lungime mai mare sau egală cu cel iniţial. De exemplu, următoarele 5 lungimi sunt corecte: 2, 2, 12, 50, 30.
2.Păstreză toate beţişoarele, şi anume 2, 7,12, pe care le va completa cu alte beţişoare de diferite lungimi (mai scurte sau mai lungi), astfel ca proprietatea anti-triunghi să se păstreze. Următoarele 5 lungimi respectă proprietatea anti-triunghi: 2, 7, 12, 4, 1.

Cunoscând un şir de n numere naturale nenule a ₁ ,a ₂ ,…,a _n având proprietatea
anti-triunghi, şi un număr k (k>n), se cere să construiţi un şir de k numere naturale având proprietatea anti-triunghi, în conformitate cu una dintre următoarele două restricţii:
Varianta 1. Cel mai mic element este identic cu cel mai mic element din şirul iniţial.
Varianta 2. Printre cele k elemente ale şirului construit se regăsesc toate elementele şirului iniţial.

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ţ.

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.

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.

Pentru un şir de caractere S, vom nota cu lmax[S] lungimea maximă a unei secvenţe palindromice conţinută în şirul S. Astfel, pentru şirul S=”abAabaabC”, lmax[S]=4, iar pentru şirul S=”a”, lmax[S]=1.

Prin secvenţa palindromică a unui şir S înţelegem un subşir de caractere aflate pe poziţii consecutive, ce formează un palindrom.

Date fiind N şiruri de caractere S[1], S[2],…, S[n] şi o valoare naturală L, se cere să se determine numărul de secvenţe de şiruri de caractere de forma: S[i], S[i+1], … , S[j], cu i<=j, pentru care lmax[S[i]]+lmax[S[i+1]]+... +lmax[S[j]]=L.

Nici nu ştiţi cât de greu este să fii funcţionar. Zeci de rapoarte de întocmit, sute de cereri ce trebuiesc redactate, mii de semnături, sute de mii de hârtii de înregistrat. Circuitul nesfârşit al hârtiilor este cunoscut sub numele de birocraţie. În instituţia noastră sunt angajaţi N funcţionari, numerotaţi de la 1 la N.

Fiecare dintre ei trebuie să înregistreze un număr considerabil de documente. Acesta este motivul pentru care în fiecare zi, încă de la prima oră, funcţionarii se aşază la coadă la secretariat, în ordine de la 1 la N. Modalitatea de înregistrare a documentelor este următoarea: funcţionarul se aşează la coadă, aşteaptă până îi vine rândul, înregistrează un singur document, apoi, dacă mai are alte documente se reaşează la coadă, ş.a.m.d. Din păcate, serviciul de secretariat înregistrează într-o zi cel mult M documente.

Dacă se cunoaşte, pentru fiecare din cei N de funcţionari, numărul de documente pe care trebuie să le înregistreze la secretariat, determinaţi numărul de ordine al funcţionarilor care nu au reuşit semnarea tuturor documentelor până la încheierea zilei de muncă.

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

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.

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.