Lista de probleme 208

Prin convenţie numim expresie aritmetică ponderată o expresie construită astfel:

• expresia conţine numere întregi de cel mult 2 cifre despărţite prin virgulă;
• numim k-șir o enumerare de k numere despărţite prin virgulă (k≥1);
• o expresie poate conţine unul sau mai multe k-şiruri;
• expresia foloseşte paranteze rotunde şi paranteze drepte.

Fiind dată o expresie aritmetică ponderată să se determine:

• câte numere întregi conţine expresia aritmetică;
• care este valoarea expresiei aritmetice.

Pasiunea Mirunei este să coloreze. Vacanţa trecută şi-a petrecut-o la bunica ei la ţară şi pentru că se cam plictisea s-a gândit să vopsească gardul de la casa bunicii.

1. Dacă o scândură era vopsită cu alb, următoarea scândură o vopsea obligatoriu cu albastru
2. Dacă o scândură era vopsită cu albastru, atunci următoarea scândură o vopsea cu alb sau roşu
3. Dacă o scândură era vopsită cu roşu, atunci următoarea scândură o vopsea cu albastru sau verde
4. Dacă o scândură era vopsită cu verde, atunci următoarea scândură o vopsea cu roșu sau galben
5. Dacă o scândură era vopsită cu galben, atunci următoarea scândură o vopsea obligatoriu cu verde

După ce a și-a terminat treaba Miruna își admira “opera de artă” și se întreba în câte moduri diferite ar fi putut să vopsească gardul bunicii.

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.

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.

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.

Se consideră algoritmul:

citeşte  k , n;
s = 0;
for (i1 = 1 ; i1 ≤ k ; i1++)
  for (i2 = 1 ; i2 ≤ i1 ; i2++)
    for (i3 = 1 ; i3 ≤ i2 ; i3++)
      ........................................
        for (in = 1 ; in ≤ in-1 ; in++)
          s = s + in;
scrie s;
stop.

Să se scrie un program care implementează algoritmul de mai sus.