Lista de probleme 3

Șoricelul Remy dorește să depoziteze cubulețele de cașcaval pe care le-a adunat. El a construit un depozit pe o suprafață dreptunghiulară și l-a compartimentat în N*M camere identice. În fiecare cameră șoricelul a depozitat o cantitate de cubulețe de cașcaval (ca în Figura A) și a stabilit că va mânca în fiecare zi câte un cubuleț de cașcaval din fiecare cameră în care există cașcaval. Planul său este stricat de John, șoricelul leneș din casa vecină, căruia nu-i place să-și strângă singur cașcaval, așa că s-a hotărât să fure din depozitul lui Remy. Pentru că John este pasionat de matematică s-a hotărât ca în fiecare seară, după ce vecinul său a terminat de mâncat, să se plimbe prin depozit și să fure tot cașcavalul din camerele în care găsește un număr pătrat perfect de cubulețe de cașcaval. John intră în depozit prin camera din colțul stânga sus, de coordonate (1,1), parcurge prima linie de la prima la ultima coloană, apoi a doua linie de la ultima coloană, până la prima și așa mai departe, până când termină de vizitat toate camerele (ca în Figura B).

Scrieți un program care să determine:

1. Numărul de zile în care se va goli depozitul lui Remy și câte camere va goli John în ziua K.
2. Numărul maxim de camere consecutive golite de acesta într-o zi și ziua în care se va întâmpla acest lucru.

Acum iarna s-a terminat și, apropiindu-se sezonul de vară, gospodarii din orașul de pe malul fluviului doresc să pregătească faleza pentru a primi cum se cuvine turiștii. Faleza este sub formă dreptunghiulară cu lungimea de n metri și lățimea de 2 metri. În toamnă ea era pavată cu 2*n dale pătrate cu latura de un metru, lipite una de alta și care acopereau complet zona falezei. În urma iernii grele, unele dale s-au deteriorat și acum se dorește înlocuirea lor.Cum de multe ori oamenii fac treaba doar “pe jumătate”, gospodarii au hotărât să cheltuie cât mai puțin pentru reamenajarea falezei, așa că au decis că nu trebuie neapărat să înlocuiască toate dalele deteriorate, ci doar un număr minim dintre acestea astfel încât să fie posibil să se parcurgă faleza de la un capăt la altul pășind doar pe dale bune (nedeteriorate). De pe o dală pe alta se poate păși doar dacă ele au o latură comună.

Scrieţi un program care să determine numărul minim de dale deteriorate ce trebuie înlocuite astfel încât faleza să
poată fi parcursă de la un capăt la altul.

Ursul: Bună, cumătră! Da cât peşte ai? Dă-mi şi mie, că tare mi-i poftă!
Vulpea: Ia mai pune-ţi pofta-n cui. Dacă vrei pește, du-te şi-ţi înmoaie coada-n baltă şi vei avea ce să mănânci.
Ursul: Învaţă-mă, te rog, cumătră, că eu nu ştiu cum se prinde peştele.
Vulpea: Alei, cumetre! da’ nu ştii că nevoia te-nvaţă ce nici nu gândeşti? Du-te deseară la baltă și bagă-ţi coada-n apă. Stai pe loc, fără să te mişti, până spre ziuă. Între timp, ia foaia aceasta pe care am scris N numere naturale și până dimineață trebuie să procedezi în felul următor:

• elimini exact două cifre alăturate din fiecare număr scris pe foaie, astfel încât, celelalte cifre rămase după eliminare să formeze, de la stânga la dreapta, cel mai mare număr posibil (de exemplu, din numărul 77196, elimini cifrele 7 și 1 pentru a obține cel mai mare număr posibil 796).
• toate cele N numere obținute la pasul anterior, le lipești unul după altul, în ce ordine vrei tu. Uitându-te de la stânga la dreapta la cifrele numerelor lipite, observi că s-a format un nou număr X. Ai grijă cum procedezi, căci până
  dimineață, atâta pește se va prinde de coada ta cât vei obține tu valoarea lui X.

Ajutați-l pe urs să prindă cât mai mult pește posibil.

Scrieți un program care citește N numere naturale și determină:

1. Cel mai mare număr de eliminări efectuate cu aceleași două cifre alăturate.
2. Cel mai mare număr natural X determinat astfel încât ursul să prindă cât mai mult pește.