Lista de probleme 3

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

À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?

Un număr se numește bipătrat dacă este pătrat perfect și, în plus, prin inserarea unei singure cifre numărul obținut este de asemenea pătrat perfect. Inserarea unei cifre se poate face atât între două cifre deja existente ale numărului, cât și la finalul sau la începutul numărului. Fiind dată o secvență de numere naturale, să se verifice dacă numerele respective sunt bipătrate, iar pentru cele ce îndeplinesc condiția să se afișeze în ordine crescătoare toate pătratele perfecte care se pot obține prin inserarea unei cifre.