Lista de probleme 21

Etichete

Un număr puternic este un număr natural mai mare decât 1 care are proprietatea că dacă este divizibil cu numărul prim p atunci este divizibil și cu p2. Scrieți un program care citește un număr natural N și apoi un șir de N numere naturale și determină:
1. Câte numere puternice sunt în șirul dat;
2. Care sunt perechile de numere din șirul rămas după ștergerea numerelor puternice, numere egal departate de capetele șirului, prin concatenarea cărora se obține un număr puternic.

#3745 Oposumi

O familie de oposumi are o vizuină cu N niveluri și N * (N + 1) / 2 camere dispuse în formă de matrice triunghiulară cu N linii. În fiecare cameră poate locui un singur oposum. Vizuina a fost săpată în pământ de către oposumi, iar nivelul 1 (cel mai de sus) este cel mai apropiat de suprafața solului. Pe fiecare nivel I se află I camere. Dacă avem I < J, atunci nivelul I va fi poziționat mai sus decât nivelul J, adică nivelul I va fi mai aproape de suprafața solului decât nivelul J. În familia de oposumi se află exact N * (N + 1) / 2 membri cu vârste cuprinse între 1 și N * (N + 1) / 2, vârste distincte. Regula de bază în vizuina familiei de oposumi este următoarea: în camera de pe linia I și coloana J trebuie să locuiască un oposum mai tânăr decât în camerele de pe pozițiile (I + 1, J) respectiv (I + 1, J + 1). Un oposum de vârsta X se consideră mai tânăr decât un oposum de vârsta Y dacă X < Y. Fiecare oposum vrea să știe care e cel mai de sus nivel pe care se poate poziționa. Din păcate, ei nu au lăbuțele făcute să programeze, așa că membrii familiei de oposumi vă cer vouă ajutorul.
Dându-se numărul natural N ei vă cer să răspundeți la două întrebări:
1. Pentru fiecare oposum să se afle nivelul cel mai de sus (cel mai aproapiat de suprafața solului) pe care se
poate afla respectând regulile de vârstă.
2. Pentru un oposum dat de vârsta K să se afișeze matricea astfel încât oposumul să stea într-o cameră pe un nivel cât mai de sus respectând regulile de vârstă.

#3746 LeMans

Ne aflăm înainte de începutul faimoasei curse de anduranță de la Le Mans. După cum bine stiți, într-o cursă de anduranță mașina care a parcurs cea mai mare distanță pe parcursul cursei este considerată câștigătoare. Anul acesta Federația Internațională de Automobilism (FIA) a făcut câteva schimbări majore cu privire la desfășurarea cursei. Anul acesta cursa va dura exact T secunde și vor participa N echipe, fiecare echipă având câte o mașină, iar fiecare mașină poate pleca de pe oricare dintre cele M poziții din grila de start. De asemenea, FIA a impus câteva reguli care au nemulțumit echipele participante:

  • Fiecare mașină este obligată să se deplaseze cu o viteză constantă pe parcursul întregii curse. Astfel, a i-a mașină se va deplasa cu viteza de v[i] metri pe secundă.
  • Dacă o mașină pleacă de pe o poziție j din grila de start, aceasta se află la o distanță de p[j] metri după linia de start, iar această distanță este luată în considerare ca o distanță deja parcursă în cadrul cursei.

Ca semn de protest asupra noului regulament, echipele au hotărât să se așeze în grila de start astfel încât diferența maximă dintre distanțele parcurse de oricare două mașini să fie cât mai mică posibil.

ONSEPI, 2021, clasa a IX-a

#3747 Bile4

Presupunem că avem două cutii notate A și B. Cutia A conține N bile numerotate cu numerele naturale distincte: 0, 1, 2, . . . , N − 1. Cutia B este goală. Spunem că o bilă dintr-o cutie este bila specială a acestei cutii dacă numărul X cu care este numerotată această bilă este egal cu media aritmetică a numerelor celorlalte bile din cutie. La un moment dat, cineva mută bila cu numărul K din cutia A în cutia B. Vi se cere să alegeți alte K bile, din cutia A, pe care să le mutați în cutia B astfel încât cutia B să conțină K + 1 bile, iar bila cu numărul K să fie bila specială a cutiei B.

În secolul al XXIII-lea, oamenii au început să străbată spațiul intergalactic. Navele cu ajutorul cărora aceștia călatoresc sunt cu adevărat minuni ale tehnologiei, ele folosind un tip foarte exotic de combustibil. Acest tip de combustibil se poate obține prin combinarea a exact doi reactanți, unul stabil cu unul instabil. Fiecare reactant are atribuită o valoare sub forma unui număr natural nenul. Spunem despre un reactant că este stabil dacă valoarea acestuia este un număr prim și că este instabil dacă valoarea acestuia nu este număr prim. Totuși, nu toate tipurile de combustibil sunt la fel de valoroase. După cum v-ați aștepta, prețul unui tip de combustibil este egal cu suma valorilor reactanților din care acesta este compus. Știind că pe piața intergalactică există N reactanți, să se răspundă la T întrebări de tipul: care este prețul celui de-al K-lea cel mai ieftin tip de combustibil care poate fi creat folosind doar reactanții disponibili pe piață.

ONSEPI, 2021, baraj juniori

Se consideră numerele naturale nenule N și D urmate de o secvență S de N numere naturale nenule ordonate crescător, indexate de la 1 la N. Să se determine numărul de cvintete de indici (i1, i2, i3, i4, i5) ce verifică relațiile:

  • a • b • c = D
  • a • x2 + b • y2 = c2
  • a < b < c
  • x ≠ y

unde am notat cu a = S[i1], b = S[i2], c = S[i3], x = S[i4], y = S[i5]. Rezultatul se va afișa modulo 1.000.000.007.

#3762 Butoi

Vară, căldură mare. Gigel se joacă în curte udând florile. După ce a terminat, mama lui îi dă o sarcină mai grea. Gigel trebuie să umple un butoi cu apă de rezervă în caz de secetă. Dar nu oricum! El are la dispoziție un șir de găleți de diferite capacități și trebuie să le folosească doar pe acestea pentru umplerea completă a butoiului. O operație constă în umplerea completă a unei o găleți de la sursa de apă și golirea ei în butoi. Desigur, o găleată se poate folosi de mai multe ori. Butoiul are capacitate de V litri, Gigel are N găleți de capacități c1, c2, …, cN litri, numere întregi și distincte și poate folosi o găleată de cel mult K ori. Ajutați-l pe Gigel să umple butoiul. Scrieți un program care să rezolve următoarele cerințe:
1. Determinați câte modalități de umplere a butoiului există;
2. Determinați o modalitate de umplere a butoiului cu număr minim de operații;
3. O secvență de exact P găleți alăturate se numește norocoasă dacă prin efectuarea operației de același număr de ori pentru fiecare dintre ele, vom putea umple complet butoiul. Determinați secvența norocoasă care permite folosirea celor P găleți de un număr minim de ori pentru umplerea completă a butoiului. Secvența norocoasă se va identifica prin poziția primei găleți folosite. Dacă există mai multe soluții se va afișa cea cu poziția minimă. Gălețile din secvența norocoasă se pot folosi de câte ori este nevoie.

#3761 Pasari

În grădina lui Macarie există N2 pomi fructiferi de diferite înălțimi, plantați sub forma unui caroiaj de N linii și N coloane, numerotate de la 1 la N. Cum există păsări care mănâncă fructele lor, Macarie s-a gândit să plaseze sisteme de supraveghere care asigură protecție într-o oarecare măsură a pomilor situați pe linia și coloana unde a fost amplasat, în toate cele patru sensuri de deplasare Nord, Sud, Est și Vest.
Cunoscând înălțimile tuturor celor N2 pomi, scrieți un program care:
1. Presupunând că Macarie are un singur sistem de supraveghere, determinați pentru o linie dată L care este coloana pomului în care trebuie amplasat sistemul de supraveghere astfel încât să fie protejați un număr maxim de pomi. Dacă există mai multe soluții, se va afișa coloana minimă.
2. Presupunând că Macarie a amplasat în fiecare pom al grădinii sale câte un sistem de supraveghere, determinați linia și coloana pomului protejat de cele mai multe sisteme de supraveghere. Dacă există mai multe soluții se va afișa soluția cu linia minimă, iar în cazul în care liniile sunt egale, cea cu coloana minimă.

#3766 zid

Un zid ornamental de formă dreptunghiulară este alcătuit din N rânduri de cărămizi, fiecare rând având câte M cărămizi identice, așezate una lângă alta. Fiecare cărămidă este colorată într-una dintre culorile {0, 1, 2, ..., Cmaxg}. Un pătrat de latură L în acest zid este constituit din cărămizile situate pe L rânduri consecutive și L coloane consecutive. Spunem că un pătrat este colorat uniform dacă el conține același număr de cărămizi din fiecare culoare care apare în pătratul respectiv. Scrieți un program care, cunoscând configurația zidului, determină în acest zid un pătrat de latură maximă, colorat uniform.

#3764 cat2pal

Prin concatenarea a două numere naturale A și B se pot obține numerele naturale AB și BA. Scrieți un program care să rezolve următoarele două cerințe:
1. Pentru un număr natural nenul A dat, să se calculeze P1, numărul numerelor naturale distincte X, unde 1 ≤ X ≤ 10 * A, astfel încât X concatenat cu A sau A concatenat cu X este palindrom.
2. Date fiind numărul natural N și un șir de N numere naturale v[1], v[2], …, v[N], să se calculeze P2, numărul de numere palindrom distincte care se pot obține prin concatenarea numerelor din perechile (v[i], v[j]), unde 1 ≤ i ≤ N și 1 ≤ j ≤ N.

ONSEPI, 2021, clasa a VII-a