Lista de probleme 18

Etichete

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.

#3718 Tort2

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.

#3733 Cosuri

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.

#3736 sir15

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

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?

#3722 Logic

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.

OJI 2021, clasa a IX-a

#3730 Cartofi

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.

#3731 tunel2 C++

Tommy este un motan alintat care adoră să se plimbe prin orice tunel. De aceea, stăpânii lui i-au construit o nouă jucărie, formată din N tuneluri interconectate (etichetate cu numerele distincte de la 1 la N. Toate tunelurile au aceeași lungime, sunt formate din M elemente unitare identice (numerotate cu numerele distincte de la 1 la M) și au ieșiri la ambele capete. Conectarea dintre două tuneluri alăturate se face printr-un element unitar numit pasaj.

Pentru a fi mai provocator, stăpânii motanului plasează în ultimul element unitar al ultimului tunel o recompensă.

Ajutați-l pe Tommy să ajungă cât mai repede la recompensă respectând regulile jocului!

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 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.