Lista de probleme 18

O matrice se numește cochilie de ordin N, sau mai simplu cochilie, dacă a fost construită în funcție de un număr natural N nenul după următoarea regulă:

• Cochilia este formată inițial dintr-un pătrat de latură 1 cu valoarea 1.
• Pentru fiecare pas I cu valorile 2, 3, …, N la cochilia deja existentă, se va alătura pe rând la DREAPTA, JOS, STÂNGA, SUS, în mod repetat în această ordine, câte un pătrat în care toate elementele au valoarea I, iar lungimea laturii pătratului nou corespunde cu latura cochiliei la care se lipește.

Cunoscând valorile numerelor naturale N și P, va trebui să răspundeți la următoarele întrebări:

• Ce dimensiuni are cochilia de ordin N?
• Ce elemente se află pe linia P a cochiliei de ordin N?

Fermierul Feder cultivă cartofi pe un teren dreptunghiular de lățime N metri și lungime M metri, compartimentat în N * M zone pătratice identice de lungime 1 metru, dispuse alăturat, câte N pe lățime (pe N linii, numerotate de la 1 la N) și câte M pe lungime (pe M coloane, numerotate de la 1 la M).
Scrieți un program care citește numerele N și M (cu semnificația din enunț), iar apoi determină:
1. numărul plantelor din teren care nu au produs niciun cartof;
2. numărul maxim de cartofi care pot fi produși de plantele dintr-o suprafață pătratică din terenul fermierului;
3. pentru fiecare dintre cele Q perechi de numere (A, B) citite, numărul cartofilor produși de plantele aflate în zonele pătratice situate între coloanele cu numerele A și B, inclusiv acestea.

Ne aflăm la un anumit moment al desfășurării campionatului național de fotbal. O parte dintre meciuri s-au jucat, altele urmează să fie disputate. Se cunoaște numărul de puncte acumulate deja de fiecare echipă înaintea desfășurării meciurilor restante. Se cunoaște, de asemenea, că un meci se poate termina egal, caz în care fiecare dintre echipe primește câte un punct, sau cu victoria uneia dintre echipe, iar în acest caz acea echipă primește trei puncte, iar cealaltă zero puncte.
1. Care echipe ar fi pe locul I dacă toate meciurile restante s-ar termina la egalitate? O echipă este pe locul I dacă are număr maxim de puncte.
2. Care echipe depind strict de propriile rezultate pentru a deveni campioane? O echipă devine campioană (câștigă campionatul) dacă termină cu număr de puncte strict mai mare decât oricare dintre celelalte echipe. Spunem că o echipă depinde strict de propriile rezultate pentru a deveni campioană dacă ea devine campioană câștigând toate meciurile pe care trebuie să le mai joace, indiferent de rezultatele celorlalte meciuri.

Se dă un șir format din N numere naturale nenule. Elementele șirului sunt numerotate de la stânga la dreapta începând cu poziția 1.
Scrieți un program care să determine răspunsul pentru întrebări de următoarele tipuri:
1. Care este cea mai din stânga poziție care conține o valoare strict mai mare decât toate cele din dreapta sa? – întrebare de tipul 1
2. Care sunt pozițiile care conțin valori strict mai mari decât toate cele din stânga lor? – întrebare de tipul 2
3. Dacă fiecărui element aflat între prima și ultima apariție a maximului i-am mări valoarea pentru a ajunge egal cu maximul, care este suma totală a valorilor adăugate? – întrebare de tipul 3

Se consideră doi vectori care conțin numere naturale: s cu M elemente și v cu N elemente. Numim secvență i-exclusivă o secvență a vectorului s care nu conține niciuna dintre valorile v[1], v[2], …, v[i]. Scrieți un program care să determine, pentru orice 1 ≤ i ≤ N, lungimea maximă a unei secvențe i-exclusive.

Cercetătorii de la NASA au instalat pe Marte un seismograf cu ajutorul căruia s-au înregistrat mișcările la nivelul solului planetei. Seismograful a trimis în fiecare din cele N secunde ce definesc perioada de timp analizată, câte un semnal pe Pământ ce a fost codificat de cercetători cu valoarea 1, dacă seismograful a detectat mișcare și 0, în cazul în care nu s-a înregistrat mișcare la nivelul solului planetei. Astfel, un seism de pe Marte a fost definit de cercetători ca fiind o perioadă continuă de timp în care seismograful a trimis, din secundă în secundă, câte un semnal codificat cu 1 și care începe după cel puțin două semnale codificate cu 0, iar la sfârșitul ei sunt înregistrate cel puțin două semnale codificate cu 0.
Cunoscând șirul celor N valori transmise în ordine de seismograf, scrieți un program care să determine:
1. Care a fost durata maximă, exprimată în secunde a unui seism;
2. Câte seisme au avut loc în perioada de timp analizată;
3. Din cauza unei erori tehnice, o perioadă continuă de timp seismograful a transmis eronat. Astfel, în șirul inițial format din cele N semnale, trebuie să înlocuim valoarea 0 cu valoarea 1, într-o singură secvență, de lungime nevidă, de elemente nule alăturate. Analizând toate posibilitățile de a face această modificare, determinați durata maximă a unui seism care se obține după modificarea șirului inițial de semnale.

La o cursă de Formula 1, fiecare echipă participantă își construiește propria mașină cu care va concura. Numerotarea mașinilor în concurs este realizată de organizatori cu ajutorul unor stegulețe pătrate ce conțin alternativ, pe fiecare rând (pe orizontală și verticală), pătrățele albe și negre de dimensiuni identice.
Scrieți un program care citește două numere naturale K și N și determină:
1. Câte pătrățele albe și negre sunt în total pe stegulețul mașinii cu numărul K;
2. Notând cu A numărul total de pătrățele albe de pe stegulețele primelor N mașini din concurs, câte pătrățele albe și negre sunt în total pe cel mai mare steguleț care conține cel mult A pătrățele albe.

Dându-se un șir de numere, se vrea să aflăm numărul de moduri de a împărți șirul în cel puțin două subsecvențe, astfel încât sumele elementelor tuturor subsecvențelor să fie egale, prima putând să aibă suma elementelor diferită de a celorlalte.

Se consideră N coșuri numerotate cu numerele distincte de la 1 la 2•N. Coșul 1 conține C1 mere, coșul 2 conține C2 mere,…, coșul 2•N conține C2•N mere. Coșurile vor fi grupate două câte două, rezultând N perechi de coșuri. Diferența de mere din cele două coșuri dintr-o pereche reprezintă excedentul perechii. 1) Determinați numărul minim posibil, respectiv maxim posibil, de mere dintr-o pereche. 2) Stabiliți dacă este posibil să se grupeze cele 2•N coșuri în perechi cu același număr de mere în pereche, iar dacă este posibil determinați și valoarea minimă a excedentelor perechilor din noua grupare.

Costel este pasionat de circuitele logice. El are la dispoziție două tipuri de circuite logice simple: circuit
ȘI, respectiv circuit SAU. Circuitele logice simple au două intrări și o ieșire.
Pentru un CLP dat, cu N nivele și pentru K șiruri de biți date la intrarea circuitului, să se determine, pentru fiecare șir, valoarea calculată la ieșirea din circuit. Pentru un CLP dat, cu N nivele și cunoscând valoarea obținută la ieșire (0 sau 1), să se determine numărul șirurilor de biți distincte ce pot fi date la intrare pentru a se obține valoarea specificată la ieșire. Rezultatul poate fi un număr foarte mare, de aceea el se va afișa modulo 666013.