Lista de probleme 9

Andrei este elev în clasa a V-a și își dorește mult un smartphone. Tatăl său știe de acest lucru și s-a gândit să-i facă o bucurie de ziua lui. Așa că a hotărât să-l ducă într-un magazin de telefoane să-și aleagă unul.

Fiecare telefon este inscripţionat cu un număr ce reprezintă performanţa acestuia. Cu cât numărul este mai mare, cu atât telefonul este mai bun. Andrei l-a dorit pe cel mai performant (cu numărul cel mai mare) dar tatăl lui i l-a cumpărat pe al doilea ca performanță.

Dându-se numărul n de smatphone-uri și performanța fiecăruia, să se determine:

1. Numărul cu care este inscripționat telefonul dorit de Andrei;
2. Numărul cu care este inscripționat telefonul pe care l-a primit Andrei.

Se dă un şir de N numere naturale. Din acest şir, putem forma un şir comprimat de forma: a[1], b[1], a[2], b[2], …, a[x], b[x], din care înţelegem că numărul a[1] apare pe primele b[1] poziţii, a[2] apare pe următoarele b[2] poziţii…, iar a[x] apare pe ultimele b[x] poziţii.

De exemplu, dacă şirul dat este 1 1 5 5 5 2, atunci şirul comprimat va fi 1 2 5 3 2 1.

Să se determine:

a) Lungimea celei mai lungi secvenţe formată din numere egale.
b) Şirul comprimat pentru şirul dat.

În ograda lui Gigel se găsesc găini și văcuțe. Se dau două numere naturale: C – numărul de capete și P – numărul de picioare din curte.

1. Să se afișeze câte găini și câte văcuțe sunt în ograda lui Gigel.
2. Maria, colega lui Gigel, îl provoacă pe acesta să calculeze numărul de divizori impari pentru numărul C și numărul de divizori pari pentru numărul P. Deoarece Gigel nu este bun la matematică, vă cere ajutorul. Să se afișeze cele două numere calculate.

Păcală a împrumutat fiecărei persoane din satul lui un număr de monezi de aur. Unele persoane sunt credule și Păcală, șiret fiind, doar acestora le-a împrumutat un număr de monezi care, scris invers, este număr prim. Mai târziu, când Păcală vrea să își recupereze banii, persoanelor credule le cere cu s monede mai mult decât le-a împrumutat. Unii săteni creduli sunt prieteni cu primarul și numărul care indică suma de bani împrumutată de ei conține cifra c. Aceste persoane știu de vicleșugul lui Păcală și ei, pentru a nu-l denunța la poliție, îi returnează acestuia cu s monede mai puține decât au primit.

Cunoscându-se numărul n de săteni, cele n valori reprezentând numărul de monede pe care Păcală le-a împrumutat fiecăruia, cifra c și numărul s, se cere să se afișeze:
a) numărul de bani împrumutaţi fiecărui sătean care este prieten cu primarul
b) numărul persoanelor credule și răspunsul la întrebarea dacă Păcală a câștigat monezi în plus față de cele împrumutate: dacă da, se va afișa pe ecran valoarea 1; dacă nu se va câștiga nimic în plus și nici nu va pierde nimic se va afișa valoarea 0, iar dacă va pierde monezi față de cele împrumutate se va afișa valoarea -1.

În Regatul Numerelor, a început războiul civil. Se dau n soldați, reprezentați prin n numere naturale, nu neapărat distincte. Cei n soldați sunt recrutați în două batalioane adverse, după o lege de recrutare. Această lege are un număr asociat, care este egal cu 1 sau 2. Dacă legea este 1, atunci soldații care au ultima cifră egală cu 0, 2, 4, 6 și 8 sunt recrutați de primul batalion, iar ceilalți de cel de-al doilea. Dacă legea e 2, atunci soldații care au suma divizorilor număr par sunt recrutați de primul batalion, iar restul de cel de-al doilea.

Dându-se n, numărul de soldați, L, legea de recrutare, și identificatorii celor n soldați, să se afișeze numărul soldaților din primul, respectiv al doilea batalion.

Se dă un șir de n fracții. Fiecare fracție este dată printr-o pereche de numere reprezentând numărătorul și numitorul fracției. De exemplu 2010 34 reprezintă fracția \( 2010 \over 34\) . O fracție poate fi ireductibilă sau se poate
simplifica. În exemplul precedent, \( 2010 \over 34\) se simplifică prin 2 și rezultă \( 1005 \over 17\).

Să se afișeze, pentru fiecare fracție:

1) Prin câte moduri distincte se poate simplifica.
2) Fracția ireductibilă.

Se dă un număr natural N. Să se calculeze expresia:

\( E = (2^0 +2^1 + 2^2 + 2^3 + … + 2^N ) \% 1 000 000 007 \)

unde x % y reprezintă restul împărţirii lui x la y.

Deoarece vin sărbătorile, elevii de la Liceul de informatică s-au gândit să decoreze laboratorul P1 cu ghirlande legate între ele. Ei au cumpărat N ghirlande numerotate de la 1 la N și vor să le lege împreună apoi să orneze laboratorul. Fiecare ghirlandă are doua culori distribuite astfel încât capetele să aibă culori diferite. Culorile sunt codificate prin numere naturale. Decoraţiunile cumpărate au N-1 culori care apar exact de două ori şi 2 culori care apar doar o singură dată. Pentru a face munca mai distractivă ei s-au gândit că, la legarea a două ghirlande, să unească două capete de aceeaşi culoare.

1) Pentru cerinţa 1 copiii vor să afle suma codurilor culorilor aflate la cele două capete ale lanţului format prin legarea ghirlandelor cumpărate, respectând regulile de îmbinare de mai sus.
2) Pentru cerinţa 2 ajutaţi-i să lege ghirlandele pentru a decora laboratorul P1 respectând regulile menţionate. Trebuie sa afisati numerele de ordine ale ghirlandelor în ordinea în care vor fi legate. La cele doua capete se vor afla
cele doua ghirlande care conțin o culoare ce apare o singura data. Dintre acestea prima va fi cea care are codul culorii mai mic

Andrei este manager la o firmă foarte importantă, la care se lucrează în ture. Aceste ture durează un număr constant de minute (1017 minute), fiecare tură începând la minutul 1. După o tură, Andrei, fiind foarte obosit, doarme până la începutul următoarei ture.

El este foarte ocupat cu o mulțime de ședințe (S ședințe mai exact). Acestea sunt trecute în agenda lui astfel: Minutul de început Durata Minutele necesare pentru pregătire – în minutele de pregătire nu trebuie să îl deranjeze nimeni).

Agenda este foarte dezordonată, iar şedinţele nu sunt notate în ordine cronologică, şi, în plus, acestea se pot suprapune. Ca un bun manager, Andrei doreşte să participe la cât mai multe şedinţe într-o tură cu condiţia să nu se desfăşoare în acelaşi timp. Deoarece nu poate renunța la nicio ședință, el va amâna pentru turele viitoare unele dintre ședințele care se suprapun, păstrând în agendă aceleași informații despre fiecare (început, durată, timp necesar pentru pregătire).

a) Afișați numărul minim de ture în care Andrei poate participa la toate şedinţele.
b) Știind că în prima tură, Andrei poate să ajungă la toate şedinţele (nu se desfăşoară două sau mai multe şedinţe la un moment dat), determinați minutul în care se poate programa începutul pregătirii unei noi şedinţe de durată D şi timp de pregătire P, astfel încât să nu se suprapună cu o alta (dacă există mai multe soluţii se va afişa cea cu momentul de început minim).