Lista de probleme 20

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.

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

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.

Yamada, cel mai bun jucător al jocului Forest of Savior, se pregătește pentru a participa într-o bătălie împreună cu coechipierii săi. Pentru a câștiga această luptă, Yamada trebuie să se folosească de diverse obiecte magice pe care le-a obținut de-a lungul timpului. Ajutați-l pe Yamada să determine:
1. Dintre toate obiectele avute la dispoziție, care este cea mai puternică carte de vrăji, care este cea mai puternică poțiune și care este cea mai puternică nestemată.
2. În ce ordine ar trebui să se folosească de obiectele magice astfel încât, la final, puterea personajului său să fie maximă.
3. Care este puterea maximă pe care o poate atinge personajul său. Fiindcă acest număr poate fi foarte mare, Yamada vrea doar să afle care ar fi restul împărțirii acestui număr la 1.000.000.007.

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.

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

Stadionul pe care Taylor Swift concertează în cadrul Turului Eras poate fi reprezentat cu ajutorul unei matrice cu N linii și M coloane, numerotate începând de la 1. În fiecare celulă (i, j), de pe linia i și coloana j (1 ≤ i ≤ N și 1 ≤ j ≤ M), se află câte un scaun pe care pot fi așezate brățări ale prieteniei. Înainte de concert, pe fiecare dintre dintre cele N x M scaune, nu se află nicio brățară. Pe durata concertului, Steven efectuează, în ordine, U modificări, care pot fi de două tipuri:

• tipul (L, a, v) cu semnificația că pe fiecare dintre cele M scaune de pe linia a sunt așezate câte v brățări noi (1 ≤ a ≤ N);
• tipul (C, a, v) cu semnificația că pe fiecare dintre cele N scaune de pe coloana a sunt așezate câte v brățări noi (1 ≤ a ≤ M).

După ce toate modificările au fost efectuate, Caroline îi pune lui Steven, în ordine, Q întrebări. Pentru fiecare întrebare, se consideră un număr natural K și descrierile a K submatrice. Steven trebuie să determine câte brățări sunt, în total, pe scaunele ce se află în cel puțin una dintre cele K submatrice considerate. Ajutați-l pe Steven să răspundă corect la toate cele Q întrebări puse de Caroline!

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.

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.