Lista de probleme 29

Etichete

#3046 telefon

Dorel, plictisit de puzzle-ul pe care l-a upgradat ieri, a decis să meargă afară cu ceilalți copii. El îi privește pe cei N copii cum joacă “telefonul fără fir”. Jocul decurge în felul următor:
  • Inițial, copiii se așază pe axa Ox, copilul i la distanța Xi metri față de origine.
  • Copilul cel mai aproape de origine alege un cuvânt secret și îl transmite celui din dreapta lui; cel din dreapta lui îl transmite următorului și așa mai departe până se ajunge la ultimul copil.

1. Care este durata minimă a jocului, dacă Dorel nu ia parte la joc?
2. Care este durata minimă a jocului, dacă Dorel ia parte la joc și se poziționează în mod optim pentru a minimiza durata jocului?

ONI 2019 clasa a IX-a

#3045 pro3

Se consideră 3 progresii aritmetice de numere naturale nenule. Notăm cu Pi, 1 ≤ i ≤ 3, mulțimile formate cu elementele progresiei i. Fie P = P1 \( \bigcup \) P2 \( \bigcup \) P3 reuniunea mulțimilor P1, P2, P3. Să se determine cardinalul mulțimii P.

ONI 2019 clasa a IX-a

#3038 tombola

Aflat într-o vizită cu părinții, Iliuță primește un bilet la tombolă pe care este scris un număr natural S. Pentru a câștiga un premiu, Iliuță trebuie să afle, plecând de la numărul S, un număr câștigător X. Pentru a-l ajuta să ghicească numărul câștigător, mama îi spune lui Iliuță că numărul S de pe biletul său este suma dintre numărul câștigător X și toate numerele obținute plecând de la numărul câștigător X, prin ștergerea cifrei unităților numărului X, apoi, succesiv, prin ștergerea cifrei unităților numărului obținut la pasul anterior, până se ajunge la un număr de o singură cifră.

Cunoscându-se numerele naturale N, S1, A, B, C, D, scrieți un program care rezolvă următoarele cerințe:
1) pentru fiecare dintre termenii șirului S1, S2, …, SN, determină cel mai mare număr natural mai mic strict decât termenul respectiv, pentru care există un număr câștigător; programul va afișa restul împărțirii sumei numerelor obținute la 1018+31;
2) pentru fiecare dintre termenii șirului S1, S2, …, SN, determină câte numere naturale mai mici sau egale cu termenul respectiv NU au număr câștigător; programul va afișa restul împărțirii sumei rezultatelor obținute la 1018+31.

#3040 domino2

Într-un joc de domino, fiecare piesă este împărțită în două zone, în fiecare zonă fiind înscris un număr natural. Dacă jocul are dimensiunea d, în joc vor exista toate piesele distincte care se pot forma cu numere cuprinse între 0 și d. Două piese sunt considerate identice dacă au înscrise aceleași numere, indiferent de ordinea lor. Astfel, piesele (3,7) și (7,3) sunt identice. Suma tuturor numerelor de pe aceste piese este 12. Problema are două cerințe:
1. Dat fiind un șir format din N numere naturale nenule reprezentând dimensiunile unor jocuri de domino, să se determine pentru fiecare joc suma tuturor numerelor înscrise pe piesele din jocul respectiv.
2. Dat fiind un șir format din N numere naturale nenule reprezentând sumele tuturor numerelor de pe piesele unor jocuri de domino, se construiește mai întâi un șir de cifre, notat cu A, scriind în ordine toate numerele din șirul dat, fără spații între ele. Se cere să se construiască un șir strict crescător de numere naturale, notat cu B, parcurgând alternativ cifrele din șirul A de la stânga la dreapta și de la dreapta la stânga.

ONIGIM 2019 clasa a VII-a

#3044 comun1

Tocmai ai primit un șir v de K numere naturale nenule distincte. Plecând de la acest șir, te-ai gândit să construiești un șir w de N numere naturale distincte, astfel încât un număr x este în șirul w dacă și numai dacă exista inițial în șirul v sau se pot alege cel puțin două numere din șirul v astfel încât x este cel mai mare divizor comun al acelor numere. De exemplu, dacă v = {4, 6, 7} atunci w = {1, 2, 4, 6, 7}. Uimit de proprietățile matematice frumoase ale noului șir w, ai uitat din păcate șirul original v de la care ai pornit. Dându-se șirul w, să se găsească un șir posibil inițial v având un număr minim de elemente.

Fie șirul Fibonacci dat prin F1 = 1, F2 = 1 și relația de recurență Fk = Fk-1 + Fk-2, k ≥ 3. Se consideră un număr natural N. Să se scrie un program care determină numărul F al fracțiilor diferite ireductibile subunitare, ce se pot forma utilizând primii N termeni ai șirului Fibonacci.

Zedd a descoperit frumusețea aplicațiilor din domeniul criptografiei. Astfel, el și-a activat abilitățile de hacker și s-a lovit de următoarea problemă: fiind dat un șir format doar din litere mici ale alfabetului englez, Zedd trebuie să găsească secvențe pe care le poate forma fără ca vreo literă să apară de prea multe ori. Cunoscând textul lui Zedd, să se determine:
  • Numărul de secvențe distincte în care fiecare literă poate să apară de maximum k ori. Două secvențe sunt considerate distincte dacă diferă fie prin poziția de început, fie prin cea de final.
  • Cea mai lungă secvență care conține doar litere distincte. Dacă sunt mai multe secvențe de lungime maximă formate din litere distincte se alege prima din punct de vedere lexicografic (alfabetic).

#3068 roata1

Cei N elevi participanți la olimpiadă au fost invitați să admire panorama orașului din roata cu N locuri instalată în Orășelul Copiilor. Fiecare elev poartă un tricou inscripționat cu un număr natural, numerele de pe tricouri fiind diferite două câte două și având valori cuprinse între 1 și N. Inițial, ei ocupă toate cele N locuri din roată, începând cu cel mai de jos scaun și continuând cu următoarele scaune, în sensul acelor de ceasornic. Roata se mișcă circular, în sensul acelor de ceasornic, cu un număr de poziții, se oprește și elevul aflat pe scaunul cel mai de jos coboară. În continuare, ea se rotește în același sens, un număr mai mare de poziții, apoi se oprește și coboară elevul aflat pe scaunul cel mai de jos și așa mai departe până când coboară toți elevii.
Cunoscându-se numărul N de elevi, precum și numerele de pe tricouri, în ordinea în care elevii se află inițial în roată, să se determine N numere reprezentând pozițiile cu care roata se mișcă circular pentru a coborî fiecare elev, astfel încât elevii să coboare din roată în ordinea crescătoare a numerelor de pe tricou. Cele N numere de poziții trebuie să fie în ordine strict crescătoare, iar numărul total de poziții trebuie să fie minim.

#3035 lumini

Privită din spațiu, harta insulei din povestea noastră are forma unui caroiaj pătratic cu L linii și L coloane. Liniile și coloanele sunt numerotate de la 1 la L. În fiecare dintre cele L*L celule se află câte un far. Inițial cel de la poziția 1,1 este aprins și toate respectă regula: orice far are farurile vecine (pe linie și coloană, deci maximum 4) în starea opusă față de starea sa. În urma unei furtuni, s-au întâmplat lucruri ciudate: fulgerele au lovit unul după altul și au afectat starea unor faruri. Sunt trei tipuri de fulgere. Prin schimbarea stării unui far înțelegem că acesta se aprinde dacă este stins și se stinge dacă este aprins.
Se dau date despre fulgere, în ordinea în care acestea acționează. Se cere ca la finalul furtunii să se indice care este starea anumitor faruri, aflate la coordonate precizate de pe insulă.

#3037 virus

Există azi mulți viruși care acționează în diferite moduri asupra informației stocate într-un calculator. Printre aceștia există și unii mai puțin periculoși, care se mulțumesc doar să simuleze o anumită alterare a informației. Să presupunem că dorim să scriem un astfel de virus care acționează doar asupra informației de tip text de pe ecranul calculatorului. În mod text, ecranul este constituit din n linii pe fiecare aflându-se câte m caractere. Caracterele sunt reținute în memoria calculatorului prin codul lor ASCII, reprezentat în binar pe 8 biți. Biții sunt numerotați de la 0 la 7 de la dreapta către stânga, cel din stânga fiind cel mai semnificativ bit. La fiecare secundă, virusul transformă simultan toate caracterele de pe ecran. Cunoscând configurația inițială a ecranului, scrieți un program care să rezolve următoarele două cerințe:
1. determină numărul de caractere inatacabile obținute în prima secundă (adică după prima transformare);
2. determină după câte secunde toate caracterele de pe ecran sunt inatacabile.