Lista de probleme 1991

Am un cablu cu N leduri (numerotate de la 1 la N) aşezate echidistant. Inițial, unele leduri sunt aprinse, iar altele sunt stinse. Ledurile sunt legate între ele astfel încât atingerea fiecărui led produce modificarea atât a stării lui, cât şi a ledurilor vecine lui. Deci, dacă se atinge ledul i (2≤i≤N-1) atunci se modifică stările ledurilor i-1, i și i+1. Dacă se atinge ledul 1, atunci se modifică stările ledurilor 1 și 2, iar dacă se atinge ledul N, atunci se modifică stările ledurilor N-1 și N. Vreau să modific starea ledurilor astfel încât să semene cu cablul cu N leduri pe care îl are Ionuț, prietenul meu (două cabluri seamănă dacă pentru orice i=1..N stările ledurilor de pe poziția i sunt identice).

Cunoscând cum arată cablul lui Ionuț, ajutați-mă să determin numărul minim de atingeri ale unor leduri astfel încât cablul meu să arate ca și cablul lui Ionuț.

Se consideră o matrice cu L linii și C coloane care memorează doar valori din mulțimea {0,1,2}. O submatrice nevidă (formată din cel puțin o linie și cel puțin o coloană) a acestei matrice o numim omogenă dacă numărul valorilor de 0 este egal cu numărul de valori de 1 și egal cu numărul valorilor de 2.

Să se determine câte submatrice nevide omogene există.

Un grup de N cercetași, numerotați de la 1 la N, se află în tabără la munte. Pentru ei, organizatorii au pregătit N scaune, de asemenea numerotate de la 1 la N, așezate în cerc, astfel încât fiecare cercetaș să aibă locul său (locul cercetașului i este pe scaunul i, 1≤i≤N).

Pentru desfășurarea următoarei activități, organizatorii au decis ca M dintre cercetași să prezinte diferite exerciții. Numărul M este egal cu cea mai mare putere a lui 2 cu proprietatea că numărul N de cercetași aflați în tabără se poate scrie ca sumă de M numere consecutive în mulțimea numerelor impare. Cei M cercetași care vor prezenta sunt cei numerotați cu numerele impare consecutive a căror sumă este N. De exemplu, dacă N=8, atunci M este 2, iar exercițiile vor fi prezentate de cercetașii numerotați cu 3, respectiv cu 5.

Din joacă, micii cercetași s-au așezat pe scaune la întâmplare. Organizatorii au nevoie pentru a desfășura activitatea ca cel puțin cei M cercetași care vor prezenta exercițiile să se afle pe locurile lor. Pentru aceasta, o parte dintre cercetași trebuie să-și schimbe locul și organizatorii invită micii cercetași să participe la jocul numit ”Mutare”. Acest joc se desfășoară astfel: unul dintre cercetașii care nu se află pe locul lor se ridică și merge în interiorul cercului. Cercetașul numerotat cu numărul scaunului rămas liber își va ocupa locul, iar locul ocupat de el anterior rămâne astfel liber. Jocul continuă până când scaunul cercetașului aflat în interiorul cercului se eliberează și el se așază pe locul său.

Fiind dat numărul N, precum și ordinea în care s-au așezat cercetașii pe scaunele numerotate de la 1 la N, scrieți un program care să determine:

• numărul M de cercetaşi care vor prezenta exerciţii în cadrul activităţii;
• numerele de identificare ale celor M cercetaşi care vor prezenta exerciţiile, în ordine strict crescătoare;
• numărul minim de cercetași care își vor schimba locul, astfel încât toţi cei M cercetași care vor prezenta exercițiile să se afle pe locurile lor.

Fie un şir a[1], a[2], …, a[n] de numere naturale, unde n este impar. Avem la dispoziţie o singură operaţie admisă şi anume: putem aduna la două poziţii diferite din şir o aceeaşi valoare naturală nenulă.

Cerințe:

1. Să se verifice dacă șirul poate să aibă toate elementele egale după aplicarea unei singure operații.
2. Folosind de mai multe ori operaţia admisă, să se obţină șirul cu toate elementele egale, dar valoarea egală obţinută să nu depăşească dublul valorii maxime din şirul iniţial.

Se consideră două numerele naturale K și S și un șir de N numere naturale a[1], a[2],…, a[N]. O secvenţă de lungime K este un subşir format din K elemente aflate pe poziţii consecutive în şir: a[i], a[i+1],.., a[i+k-1]. Parcurgând șirul de la stânga la dreapta, începând cu primul element, se elimină prima secvență de lungime K, cu suma elementelor strict mai mare decât numărul S. În urma ștergerii șirul va avea N-K elemente: a[1], a[2],…, a[N-K]. Operația de ștergere continuă după aceleași reguli până când nu mai există secvențe care pot fi eliminate.

Să se scrie un program care citind numerele N, K, S și cele N elemente din șir rezolvă cerințele:
1) Determină numărul secvențelor care se vor elimina respectând condiția din enunț.
2) Considerând că în șirul citit nu sunt posibile eliminări de secvențe conform condiției din enunț, programul determină numărul de elemente a[i] din șir cu proprietatea următoare: ștergerea lui a[i] conduce la obținerea unui șir în care se mai poate elimina cel puțin o secvență de K elemente cu sumă strict mai mare ca S.

Pentru un număr natural N se consideră șirul a=(1,2,3...,N), deci a[i]=i pentru orice i, 1≤i≤N.

Asupra acestui șir se pot aplica operații de două tipuri:

a) la operația de tipul 1 se specifică două valori i și j, cu 1≤i≤j≤N. Efectul acestei operații asupra șirului este de oglindire a secvenței din șir care începe cu elementul de pe poziția i și se termină cu cel de pe poziția j. De exemplu, dacă în șirul a=(1,2,3,4,5,6,7) se aplică operația 3 6, atunci șirul devine a=(1,2,6,5,4,3,7). Iar în șirul a=(1,4,3,2,5,6,7), dacă se aplică operația 4 6, atunci a=(1,4,3,6,5,2,7).
b) Operația de tipul 2 conține un indice i, 1≤i≤N, și cere să afișăm valoarea elementului care se află în acel moment pe poziția i în șir.

Se consideră M astfel de operații într-o ordine dată.

Scrieți un program care să determine și să afișeze rezultatul pentru fiecare operație de tipul 2.

Ionel și Georgel sunt colegi de clasă și doresc să facă schimb de fișiere prin email. Fiecare dintre ei își arhivează fișierele cu câte o parolă. Fiecare copil își construiește parola pe baza unui șir format din N numere naturale.

Numerele din șir care se folosesc efectiv pentru construirea parolelor sunt doar cele divizibile cu numerele din mulțimea {2,3,4,5,6,7,8,9,10,11,12,13,14,15}. Copiii numără câte din valorile din șir sunt divizibile cu fiecare din aceste numere.

Parola folosită de Ionel se obține prin însumarea numărului de valori din șir care sunt divizibile cu numerele din mulțimea {2,3,4,5,6,7,8,9}. Parola folosită de Georgel se obține prin însumarea numărului de valori din șir care sunt divizibile cu numerele din mulțimea {10,11,12,13,14,15}.

Scrieţi un program care citește șirul celor N numere și determină:

1. câte numere din șir nu se vor folosi în construirea parolelor celor doi copii;
2. parola construită de Ionel;
3. parola construită de Georgel.

• notează fiecare putere a lui 2, strict mai mică decât 226, cu o literă a alfabetului, astfel:

• reprezintă fiecare număr ca un șir de cifre și litere obținut din scrierea acelui număr ca sumă de puteri ale lui 2; dacă o putere este folosită de mai multe ori în descompunerea numărului atunci ea va fi precedată în șir de numărul de utilizări.

Un număr poate fi reprezentat astfel în mai multe moduri. De exemplu, pentru numărul 100 printre variantele de reprezentare avem:

• 100 = cfg = 22+25+26 = 4+32+64 = 100
• 100 = 2ab2cde2f = 2*20+21+2*22+23+24+2*25 = 2*1+2+2*4+8+16+2*32 = 100
• 100 = 16bcg = 16*21+22+26 = 16*2+4+64 = 100

Scrieți un program care rezolvă următoarele cerinţe:

1. cunoscând s numărul de stele dintr-o galaxie, determină o reprezentare codificată a acestui număr formată doar din litere mici distincte ordonate alfabetic;
2. cunoscând g, reprezentând numărul de galaxii și g numere în scriere codificată, reprezentând numărul de stele din fiecare galaxie, determină scrierea zecimală a numărului total de stele din cele g galaxii.

Se consideră un număr natural par N și șirul ordonat crescător X format din primele N numere naturale nenule:

X[1] = 1, X[2] = 2, …., X[N] = N.

Pozițiile numerelor din șir se pot modifica doar conform regulii A,după cum urmează:

• dacă X[1] este număr impar, atunci se interschimbă X[1] cu X[2], X[3] cu X[4], …, X[N-1] cu X[N];
• dacă X[1] este par atunci se interschimbă X[2] cu X[3], X[4] cu X[5], …, X[N-2] cu X[N-1], iar X[N] cu X[1].

Aplicând de R ori regula A șirului X se transformă șirul dat într-un șir “A sortat”.

Cunoscându-se numerele naturale N, R, K și T, scrieți un program care să determine:
1) Numărul situat pe poziția K în șirul “ A sortat” obținut prin aplicarea de R ori a regulii “ A ” șirului X.
2) Predecesorul și succesorul numărului T în șirul “ A sortat” .

Gigel este un mare pasionat al cifrelor. Orice moment liber şi-l petrece jucându-se cu numere. Jucându-se astfel, într-o zi a scris pe hârtie 10 numere distincte de câte două cifre şi a observat că printre acestea există două submulţimi disjuncte de sumă egală. Desigur, Gigel a crezut că este o întâmplare şi a scris alte 10 numere distincte de câte două cifre şi spre surpriza lui, după un timp a găsit din nou două submulţimi disjuncte de sumă egală. Date 10 numere distincte de câte două cifre, determinaţi numărul de perechi de submulţimi disjuncte de sumă egală care se pot forma cu numere din cele date, precum şi una dintre aceste perechi pentru care suma numerelor din fiecare dintre cele două submulţimi este maximă.