Lista de probleme 19

Într-o minunată zi de primăvară, P răţuşte au ieşit la plimbare pe lac. Un pelican milităros, care stătea pe mal, a decis să facă instrucţie cu nevinovatele raţe. Pentru aceasta, a cartografiat imediat lacul şi l-a reprezentat ca o matrice cu N linii (numerotate de la 0 la N-1 de sus în jos) şi N coloane (numerotate de la 0 la N-1 de la stânga la dreapta). Astfel, poziţia oricărei raţe pe lac poate fi identificată prin linia şi coloana pe care se află raţa. Raţele sunt orientate cu faţa spre una dintre direcţiile Nord, Sud, Est, Vest. Scrieţi un program care, cunoscând poziţia iniţială pe lac a celor P raţe şi succesiunea comenzilor pelicanului, determină poziţia finală a fiecărei raţe.

Ana şi Bogdan au inventat un nou joc, pe care l-au denumit Strips. Este un joc de strategie, dar şi de antrenare a memoriei, deoarece se joacă pe o tablă care nu este vizibilă pentru cei doi jucători în timpul jocului.
Scrieţi un program care citeşte lungimea tablei de joc, numărul de benzi colorate pe care le are fiecare jucător la începutul jocului, lungimea benzilor, precum şi poziţiile specificate de jucători pe parcursul jocului şi rezolvă următoarele două cerinţe:
- determină numărul de puncte de penalizare pentru fiecare dintre cei doi jucători;
- determină pentru fiecare jucător care este lungimea maximă a unei zone de pe tabla de joc colorată în culoarea sa la sfârşitul jocului.

Gigel are în fața sa pe o foaie de matematică un desen obținut prin trasarea mai multor linii orizontale și verticale de lungime 1 de-a lungul modelului foii de matematică. Fiind date dimensiunile n şi m ale foii de matematică, precum şi tabloul bidimensional de dimensiune n x m care conține codificarea foii, să se determine:

• numărul total de pătrate existente pe foaia de matematică în desenul realizat conform codificării
• distribuția numărului de pătrate în ordinea strict crescătoare a lungimii laturilor
• unde poate fi trasată încă o linie astfel încât numărul total de pătrate să crească și să devină maxim posibil

Deși nu obișnuiește să deseneze, Adrian are o pasiune inedită: îi place să schițeze pe hârtie orașe imaginare… mai exact cum ar arăta acestea văzute de sus. În acest an, de ziua lui a primit cadou un pergament! Normal că menirea acestuia va fi ca Adrian să deseneze pe el schița celui mai mare oraș pe care și l-a imaginat până acum. Pergamentul are lățimea unei coli de hârtie, însă lungimea sa este neașteptat de mare. De asemenea, pergamentul este împărțit în pătrate astfel încât pe lungime se află exact N pătrate iar pe lățime se află exact K pătrate. Astfel, Adrian are la dispoziție exact N*K pătrate pe care le poate colora.
Cunoscând numerele N, K, Q, precum și poziționarea celor N străzi orizontale și a celor Q străzi verticale, să se determine numărul de pătrate mov din pergament.

Se dă un număr N, și un șir de N numere naturale nenule. Determinați suma valorilor aflate pe ultimele K poziții în șir (unde K reprezintă valoarea celei mai din dreapta cifre nenule a primei valori din șir). Ne imaginăm împărțirea șirului în secvențe în următorul mod: prima secvență este formată din primele L elemente, a doua este formată din următoarele L-1 elemente, a treia este formată din următoarele L-2 elemente și așa mai departe, ultima secvență este formată dintr-un singur element și acesta coincide cu ultimul element din șir. Considerând suma valorilor fiecărei secvențe, să se determine cea mai mare dintre aceste sume.

Se dă un șir a1, a2, …, an de numere naturale nenule. Să se determine răspunsul pentru una din următoarele cerințe:

• Cel mai mare divizor comun al celor n numere.
• Cel mai mare divizor comun care se poate obține alegând exact n-1 elemente din șir.
• Cel mai mare divizor comun care se poate obține alegând exact n-2 elemente din șir.

Un palilindrom este un număr natural pentru care există o bâlbâială a regelui care îl transformă într-un palindrom. Spre exemplu, 25373552 este un palilindrom, pentru că după o bâlbâială poate deveni 255373552, acesta fiind un număr palindrom. Fiind dat un număr natural nenul X să se determine:

• Câte numere diferite poate genera X după o bâlbâială și câte numere diferite pot deveni X după o bâlbâială.
• Cel mai mare număr palilindrom care se poate forma cu cifrele lui X. Nu este obligatoriu să se folosească toate cifrele lui X.

Se dă un șir de n cifre c1, c2, …, cn, adică 0 ≤ ci ≤ 9. Dintr-un șir de cifre se poate obține un șir de 1 ≤ m ≤ n numere a1, a2, …, am. Cunoscându-se șirul de cifre inițial, să se obțină următoarele rezultate:
- Presupunând că nu se face nici o lipire de cifre, fiecare cifră devenind un număr în șir, adică ai = c1, să se determine câte perechi de numere vecine consecutive există în șir;
- Să se determine o modalitate de lipire a cifrelor astfel încât să se obțină cele mai mari două numere vecine consecutive și să se afișeze primul dintre aceste numere.

Definim un număr liber de pătrate ca fiind un număr natural care nu are ca divizor niciun pătrat perfect mai mare ca 1. Prin convenție, 1 este considerat liber de pătrate.
1) Să se determine câte numere libere de pătrate conține șirul dat.
2) Să se determine cea mai lungă bisecvență din șir formată din numere libere de pătrate, obținută prin eliminarea unui număr care nu este liber de pătrate.

Àles a primit ca temă următoarea problemă: “Fiind dat un șir A cu N numere naturale distincte, să se calculeze suma cifrelor fiecărui element al șirului”. După ce și-a terminat tema, acesta observă că sunt mai multe perechi de indici (i, j) pentru care dacă A[i] < A[j] atunci S[i] > S[j], unde S[i] reprezintă suma cifrelor lui A[i]. El le va numi pe acestea perechi speciale de indici. Terminând prea repede tema, Àles primește o temă suplimentară cu două cerințe:

• Determină două numere aflate în șirul A, pentru care indicii corespunzători formează o pereche specială.
• Câte perechi speciale de indici (i, j) se găsesc în şirul A?