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.

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.

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.

O matrice pătratică A_{ij} de dimensiuni N x N cu N impar se numește matrice spirală dacă respectă următoarele proprietăți când este parcursă în spirală.

• Pentru oricare celulă (i, j) din matrice, fie A[i, j] = 0, fie A[i,j] nu conține cifra 0.
• Fie (i, j) oricare celulă mai puțin cea din centru și (k, l) celula parcursă anterior din matrice, și fie c oricare cifră nenulă, adică de la 1 la 9:
  a) Dacă c divide i + j, atunci A[i, j] conține cifra c dacă și numai dacă A[k, l] nu conține cifra c.
  b) Dacă c nu divide i + j, atunci A[i, j] conține cifra c dacă și numai dacă A[k, l] conține cifra c.
  c) Pentru numărul aflat în celula din centru, fiind prima parcursă, nu avem astfel de restricții.

• Un element din matrice va fi 0 dacă și numai dacă acesta nu are voie să conțină nicio cifră de la 1 la 9 conform regulilor de mai sus.

Dându-se o matrice pătratică A de dimensiune N, trebuie să determinați care este numărul minim de elemente din matrice care ar trebui înlocuite (în celulele respective pot fi scrise orice alte numere naturale) pentru ca A să devină o matrice spirală.

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.