Lista de probleme 17

Etichete

#2000 Sir9

Corneluș a învățat să numere. El pornește întotdeauna de la 1, numără din 1 în 1, nu greșește niciodată numărul următor, însă ezită uneori și atunci spune numărul curent de mai multe ori. Sora lui, Corina, îl urmărește și face tot felul de calcule asupra modurilor în care numără fratele ei. Astfel, ea urmărește până la cât numără (U), câte numere spune în total (N) și, pentru a aprecia cât de ezitant este, numărul maxim de repetări (R) ale unei valori.
1) Cunoscând numărul total de numere N și ultimul număr spus U, trebuie să calculați câte șiruri diferite au exact N numere și se termină cu numărul U.
2) Cunoscând numărul total de numere N și numărul maxim de repetări R ale unei valori, trebuie să calculați câte șiruri diferite au exact N numere și fiecare valoare se repetă de cel mult R ori.
Deoarece numărul de șiruri poate fi foarte mare, calculați restul împărțirii acestui număr la 20173333.

#1998 Rover

NASA plănuiește o nouă misiune Rover pe Marte în anul 2020. Principalul obiectiv al acestei misiuni este de a determina, cu ajutorul unui nou Rover, dacă a existat în trecut viață pe Marte. Până când va fi lansată misiunea, Roverul este supus la tot felul de teste în laboratoarele NASA. Într-unul din teste, Roverul trebuie să parcurgă o suprafață de forma unui caroiaj cu N linii și N coloane. Acesta pornește din zona de coordonate (1,1) și trebuie să ajungă în zona de coordonate (N,N), la fiecare pas putându-se deplasa din zona în care se află într-una din zonele învecinate la nord, sud, est sau vest. Pentru fiecare zonă de coordonate (i,j) se cunoaște A[i,j], stabilitatea terenului din acea zonă. Știind că Roverul are o greutate G, o zonă cu stabilitatea terenului cel puțin egală cu G se consideră o zonă sigură pentru deplasarea Roverului, iar o zonă cu stabilitatea terenului mai mică decât G se consideră o zonă periculoasă pentru Rover.

1. Determinați numărul minim posibil de zone periculoase pe care le traversează Roverul pentru a ajunge din zona (1,1) în zona (N,N).
2. Determinați greutatea maximă pe care o poate avea un Rover care să ajungă din zona (1,1) în zona (N,N), fără a traversa nicio zonă periculoasă pentru el.

#1999 Caps

Miruna a descoperit un nou joc. Ea dispune de litere mari și mici ale alfabetului englez și construiește succesiv șiruri de litere din ce în ce mai lungi. Ea definește operația CAPS a unei litere, ca fiind transformarea literei respective din literă mare în literă mică sau invers, din litera mică în literă mare. Pentru fiecare șir S, Miruna asociază un nou șir Sc, numit șir CAPS, care se obține aplicând operația CAPS asupra tuturor literelor din șirul S. Miruna a inventat o altă operație pentru un șir de litere S, numită NEXT, prin care obține un nou șir SN care are structura SScScS (este format în ordine de la stânga la dreapta din literele lui S, apoi de două ori succesiv literele șirului Sc, iar apoi urmează din nou literele șirului S). Miruna vă roagă să răspundeți la Q întrebări de tipul:
„Dacă se dă un număr natural N, ce literă este în șirul final pe poziția N și de câte ori a apărut această literă în șirul final, de la începutul șirului final până la poziția N inclusiv?”.

OJI 2017, Clasa a X-a

Spunem că trei numere a b c sunt în progresie armonică dacă b este media armonică a numerelor a și a, adică
\( b = \frac{2}{\frac{1}{a} + \frac{1}{c}} = \frac{2 \cdot a \cdot c} {a + c} \)

Cunoscând un număr natural b să se determine toate perechile de numere naturale (a,c) pentru care a b c sunt în progresie armonică.

OJI 2017, Clasele XI-XII

#2127 ninjago

După ce eroii ninja l-au învins pe Nadakhan, de ziua celor dispăruți Zane trebuia să păzească cele n păpuși din muzeu. Între aceste păpuși există m coridoare pe care se poate circula în ambele sensuri. Se garantează faptul că pe cele m coridoare Zane poate ajunge la fiecare dintre cele n păpuși. Skulkiu, având la dispoziție 5 tipuri de obstacole A, B, C, D, E, încearcă să-l oprească pe Zane punând pe fiecare coridor câte 4 obstacole. Zane poate distruge obstacolele de tip A, B, C și D, dar nu poate să distrugă obstacolele de tipul E. Pentru a distruge un obstacol de tipul A arma lui Zane are nevoie de 1 unitate de energie, pentru a distruge un obstacol de tipul B de 2 unități de energie, pentru a distruge un obstacol de tipul C de 3 unități de energie, iar pentru a distruge un obstacol de tipul D de 4 unități de energie. Datorită dispozitivului cu care Skulkiu amplasează obstacolele pe coridor, cele patru obstacole de pe acelaşi coridor au o adâncime din ce în ce mai mare, ceea ce implică faptul că pentru a distruge al doilea obstacol amplasat pe coridor este nevoie de 5 ori mai multă energie decât cea obișnuită, pentru a distruge cel de-al treilea obstacol amplasat pe coridor este nevoie de 25 ori mai multă energie decât cea obișnuită, iar pentru a distruge al patrulea obstacol amplasat pe acelaşi coridor este nevoie de 125 de ori mai multă energie decât cea obișnuită. Indiferent de sensul de parcurgere al coridorului de către Zane pentru a înlătura obstacolele, energia consumată este aceeaşi, aceasta depinzând doar de ordinea în care au fost amplasate obstacolele de către Skulkiu. Zane nu va înlătura obstacolele de pe toate coridoarele ci doar strictul necesar pentru a avea acces la fiecare păpușă. Zane dorește să-i lase pe ceilalți ninja să se antreneze așa că face în așa fel încât ajutorul pentru distrugerea obstacolelor de tip E să fie minim și apoi ca el să utilizeze un număr minim de unități de energie. Pentru coridoarele pe care se află obstacole de tip E Zane consumă energie doar pentru obstacolele de tip A, B, C şi D. Inițial Zane se află lângă păpușa 1.

Cerințe:

  1. Precizați la câte dintre cele n păpuși poate ajunge Zane înainte de a cere ajutorul celorlalți ninja.
  2. Precizați pentru eliberarea câtor coridoare trebuie să ceară ajutor extern pentru a reuși să ajungă la toate cele n păpuși și câte obstacole de tip E sunt în total pe aceste coridoare.
  3. Precizați care este numărul minim de unități de energie utilizate.

#2044 Cursuri

Într-o tabără de vară se programează susținerea unor cursuri în K săli de clasă. Sunt N profesori care și-au exprimat dorința de a participa, fiecare dintre ei specificând intervalul de timp [ai, bi] în care își poate susține cursul. Programarea pe săli a profesorilor trebuie să țină cont de faptul că într-o clasă, la un moment dat, nu poate preda decât un singur profesor.

Cunoscându-se faptul că organizatorii doresc susținerea a cât mai multor cursuri, să se determine:

1) Numărul maxim de cursuri care pot fi programate în cele K săli de clasă, ținând cont de restricția indicată.
2) În dorința de a programa toate cursurile, în cele K săli, organizatorii decid să modifice durata cursurilor, păstrând însă neschimbată ora de început a lor. Astfel, ei hotărăsc ca toate cursurile să dureze un interval egal de timp, care însă nu va depăși durata celui mai lung curs propus inițial de unul dintre cei N profesori. Determinați care poate fi durata maximă pe care o pot avea cursurile în aceste condiții.

Definim o permutare dublă de ordin n ca fiind un șir format din primele 2n numere naturale nenule: (a[1], a[2], ... , a[n], a[n+1], a[n+2], ... , a[2n]). Această permutare dublă este de trei ori în creștere, dacă sunt adevărate următoarele trei proprietăți:

  1. secvența formată din primele n elemente este crescătoare: a[1]<a[2]< ... < a[n]
  2. secvența formată din ultimele n elemente este crescătoare: a[n+1]<a[n+2]< ... < a[2n]
  3. perechile ordonate formate din elementele aflate pe poziții identice ale celor două secvențe sunt de asemenea în ordine crescătoare: a[1]<a[n+1], a[2]<a[n+2], ... , a[n]<a[2n].

Pentru simplificare în continuare permutarea dublă de trei ori în creștere se va numi permutare. Vom considera toate permutările de ordin n ordonate lexicografic, numerotate începând cu 1.

Există două tipuri de întrebări:

  1. Ce permutare se află pe o poziție dată?
  2. Pe ce poziție se află o permutare dată?

Să se răspundă corect la un set de întrebări.