Lista de probleme 21

Etichete

#3744 ELHC

După șase ani de lucru, Charles a terminat de curățat instalațiile pentru producerea negrului de fum din Copșa Mică. Pentru a se ține departe de mesele de Blackjack, el s-a angajat la CERN, unde va lucra la noul accelerator de particule numit Even Larger Hadron Collider (ELHC). ELHC are forma unui tunel circular cu o circumferință de P kilometri, P fiind un număr prim. De-a lungul tunelului sunt plasați P senzori numerotați de la 0 la P - 1, distanța dintre doi senzori consecutivi fiind de exact 1 kilometru.

Un experiment efectuat în ELHC constă în studierea unei particule de tip G, 1 ≤ G < P. Dacă această particulă este ridicată la nivelul de energie k și este lansată din dreptul senzorului 0 în direcția senzorului 1, ea va parcurge exact Gk kilometri prin tunel și apoi se va dezintegra, declanșând în acel moment senzorul s în dreptul căruia are loc dezintegrarea particulei. Se consideră că experimentul are date complete dacă, lansând P - 1 particule de tip G ridicate la toate nivelurile de energie k de la 1 la P - 1, este posibil să declanșăm toți senzorii s numerotați cu valori între 1 și P - 1, adică toți senzorii din tunel mai puțin senzorul 0.

Dându-se T perechi de numere G și P, determinați dacă experimentul pentru studierea particulei de tip G într-un tunel de circumferință P produce date complete.

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

Se consideră un șir cu N elemente numere întregi. Definim următoarele noțiuni:

  • secvență în șir = elemente situate pe poziții consecutive în șir
  • lungimea unei secvențe = numărul de elemente care o formează
  • suma unei secvențe = suma elementelor care o formează
  • secvența nebanală = secvența de lungime cel puțin egală cu 2
  • N-secvență = secvență a cărei sumă este divizibilă cu N (secvența poate fi și banală)
  • N-secvență nebanală = secvență nebanală a cărei sumă este divizibilă cu N.

Scrieți un program care să citească numărul natural N și apoi șirul de N elemente. Programul determină:

  1. numărul de N-secvențe nebanale, din șir;
  2. cea mai mare lungime a unei N-secvențe din șir;
  3. cea mai mare sumă a unei N-secvențe din șir.

Pentru că îi plac cifrele, Skippie, iepurașul norocos, a stabilit cum se obține cifra de control a unui număr: se efectuează suma cifrelor sale, apoi suma cifrelor acestei sume, până când suma obținută este un număr format dintr-o singură cifră. Această ultimă cifră, spune Skippie, poartă numele de cifră de control. Skippie a ascuns în păadure n ouă roșii. Pe fiecare ou a pictat câte un număr natural nenul. Iar acum se întreabă care este suma dintre cel mai mare și cel mai mic număr natural care se pot forma din toate cifrele distincte folosite în scrierea numărului pictat.
1. Pentru fiecare dintre cele n numere pictate de Skippie aflați suma dintre cel mai mare și cel mai mic număr natural care se pot forma din toate cifrele distincte folosite în scrierea numărului pictat.
2. Pentru fiecare dintre cele n numere pictate de Skippie aflați de câte ori apare cifra de control a numărului pictat în scrierea tuturor numerelor naturale mai mici sau egale decât numărul pictat.

ONSEPI, 2021, clasa a V-a

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.

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

Î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

#3758 inno

Se dau numerele naturale n și k, precum și un șir a[1], a[2] ,…, a[n] de numere naturale nenule. Din șir de poate elimina o singură secvență (eventual vidă) a[i], a[i+1], …, a[j] astfel că în șir rămân elementele a[1], a[2], …, a[i-1], a[j+1], …, a[n]. După eliminarea secvenței, elementele rămase formează un șir inno dacă aplicându-se operația & pe biți asupra lor rezultatul este un număr care are cel puțin k biți de 1 în baza 2. Să se determine în câte moduri se poate elimina o secvență astfel încât elementele rămase să formeze șir inno.