Lista de probleme 2001

Maria a primit cadou de ziua ei o cutie cu piese de puzzle, etichetate cu numere naturale. Pentru a-l rezolva trebuie să lipească între ele, în ordinea în care le extrage din cutie, cât mai multe piese, formând astfel grupuri de piese. Cunoscând cele N numere naturale care se găsesc pe etichetele pieselor de joc, în ordinea în care aceste se extrag din cutie, să se determine:
1. Numărul de grupuri pe care le obține Maria după ce rezolvă jocul de puzzle;
2. Cele K numere înscrise pe etichetele grupurilor alese de Maria.

Se dau N numere naturale care conțin în scrierea lor doar cifre din mulțimea {0, 1, 2, 3, 4}. În continuare prin număr special se înțelege un număr natural în care apare cel puțin o cifră impară și fiecare cifră impară apare de număr par de ori.
1. Să se calculeze numărul de elemente din șirul dat care sunt numere speciale.
2. Să se calculeze numărul secvențelor din șirul dat care au lungimea cel mult egală cu K și în care un singur element este număr special.
3. Să se determine și să se afișeze pentru fiecare secvență de lungime K numărul minim de elemente care ar trebui eventual eliminate astfel încât concatenând elementele rămase să obținem un număr special, iar dacă din secvență nu se poate obține un număr special atunci se va afișa -1.

Robin Hood și Little John au hotărât să stabilească care dintre ei este cel mai bun arcaș. Pentru aceasta au construit n ținte așezate în linie dreaptă și numerotate de la 1 la n. Au stabilit apoi distanța de tragere. Cei doi se deplasează prin fața țintelor în linie dreaptă la distanța stabilită de comun acord. Cei doi pot trage simultan în aceeaşi țintă sau într-una deja atinsă. Concursul se încheie în momentul în care fiecare țintă a fost atinsă cel puțin o dată.
1. Se cere să se determine timpul în care se termină concursul.
2. Care sunt țintele atinse exact o dată în timpul concursului.
3. Care sunt țintele atinse de cele mai multe ori în timpul concursului.

Geologul George a descoperit recent în zona Iașiului o peșteră foarte frumoasă, ideală pentru studierea stalactitelor. În peșteră se află N stalactite, așezate în linie dreaptă. După săptămâni de muncă și analizare temeinică a peșterii, George a descoperit că fiecare stalactită este formată din straturi de depuneri cu diverse compoziții chimice. Astfel, dacă are o stalactită cu 4 straturi, cărora le-a asociat numerele prime 2, 11, 2, 3, atunci stalactita respectivă va avea valoarea 132 = 2 • 2 • 3 • 11. Aflați numărul maxim de stalactite care formează o subsecvență obținută prin curățare, care să fie pe gustul lui George.

Se dă un șir A cu N elemente, numere naturale nenule, și un număr natural K. O subsecvență a șirului este un șir format din unul sau mai multe elemente aflate pe poziții consecutive în șirul inițial. Spunem că o valoare x se numește element majoritar al unei secvențe de lungime m, dacă ea apare în aceasta de cel puțin \( \left[ \frac{m}{2} \right] + 1\) ori. Să se afișeze valorile care sunt elemente majoritare pentru cel puțin o subsecvență de lungime mai mare sau egală cu K a șirului A.

Se consideră un număr natural format din n cifre. Inserând între cifrele numărului dat p operatori + şi q operatori - se obţine o expresie aritmetică. Un operator poate fi inserat doar între două cifre, deci înaintea primei cifre a numărului nu se poate plasa un operator.
Scrieţi un program care, pentru un număr dat, determină valoarea maximă a unei expresii aritmetice care se poate obţine inserând p operatori + şi q operatori - între cifrele numărului dat.

Fie x[1], x[2], ..., x[N] un șir de N numere naturale. Două poziții i și j, cu 1 ≤ i ≤ j ≤ N, definesc secvența [i, j] care va conține numerele x[i], x[i + 1], ..., x[j]. O secvență [i, j] cu proprietatea că suma tuturor elementelor din secvență are cifra de control egală cu 9 o vom denumi secv9. Scrieţi un program care, cunoscând N, numărul de elemente din șir, respectiv x[1], x[2], ..., x[N], elementele din șir, rezolvă următoarele două cerințe:

• afișează lungimea maximă a unei secvențe secv9;
• afișează numărul de secvențe secv9 din șir.

Paftenie trăiește într-un oraș pătratic, împărțit în n x n regiuni pătratice, așezate pe n linii, numerotate de la 1 la n, și n coloane, numerotate de la 1 la n. Cum Paftenie este prea distras de micul său dejun englezesc cu cârnăciori și fasole fiartă, apelează la voi pentru a determina:

1) Numărul maxim de cetățeni care iau micul dejun împreună în cea de-a doua zi.
2) Gradul de fericire al orașului său.

În cadrul cercului de lingvistică Ioana a studiat diferite sisteme de codificare a mesajelor, însă i-a atras atenția codificarea par-impar care se aplică numerelor naturale. În această codificare fiecare cifră a unui număr crește cu valoarea 1 dacă cifra este pară, respectiv scade cu valoarea 1 dacă cifra este impară.
1. Dându-se un șir de n numere naturale, să se determine cel mai mic și cel mai mare număr din șir care, prin codificarea par-impar, devin mai mari decât valorile lor inițiale.
2. Să se determine câte numere naturale de k cifre cu prima cifră cif devin palindrom prin codificarea par-impar.

Spunem că o secvență de numere (a[i], a[i + 1], ..., a[j]) este esm dacă are cel puțin 3 elemente și există cel puțin o pereche de numere (a[x], a[y]) în acea secvență, cu i ≤ x < y < j, astfel încât a[x] * a[y] = a[j]. Se dă un șir a[1], a[2], ..., a[n] de numere naturale. Să se determine:

• Numărul de secvențe esm din șir de lungime 3.
• Numărul de secvențe esm din șir care se termină cu elementul de la ultima poziție, a[n].
• Numărul de secvențe esm din șir.