Lista de probleme 1991

Se dă o permutare A a numerelor de la 1 la N. Operatorul ⊕ din limbajul C/C++ realizează operația XOR (disjuncție exclusivă pe biți). Scrieți un program care să rezolve următoarele două cerințe:
1. Construiți o altă permutare B astfel încât expresia E = (A1 + B1) ⊕ (A2 + B2) ⊕ ... ⊕ (AN + BN) să aibă valoare minimă.
2. Construiți o altă permutare B astfel încât expresia E = (A1 + B1) ⊕ (A2 + B2) ⊕ ... ⊕ (AN + BN) să aibă valoare maximă.

În Sosmania sunt N fabrici de sos, numerotate de la 1 la N. Aceste fabrici folosesc pentru prepararea sosului o mulțime proprie de ingrediente. La nivel național, sunt acceptate M tipuri de ingrediente, numerotate de la 1 la M. Se consideră că o secvență formată din două sau mai multe fabrici este compatibilă, dacă toate fabricile din secvență folosesc cel puțin un ingredient comun. O secvență de fabrici (i, j) (1 ≤ i < j ≤ n) este formată din toate fabricile care au numărul de ordine x astfel încât i ≤ x ≤ j. Cunoscându-se N, M și mulțimea ingredientelor folosite de fiecare dintre cele N fabrici, să se determine numărul de subsecvențe compatibile.

Costin are o matrice pătratică A cu N linii (numerotate de sus în jos de la 1 la N) și N coloane (numerotate de la stânga la dreapta de la 1 la N). Inițial toate elementele matricei sunt egale cu 0. Scrieți un program care, cunoscând N, precum și o succesiune de M operații, afișează matricea rezultată în urma efectuării în ordine a operațiilor din succesiune.

Mugurel a decis să devină în sfârșit cel mai mare antreprenor din Imperiul Rațelor de Cauciuc. Astfel, el și-a deschis o afacere cu fructele sale preferate: portocale și banane.

Acesta primește planul recoltelor de fructe: timp de N zile, în fiecare zi Mugurel primește M grămezi de portocale și M grămezi de banane (alternativ), reprezentate prin numărul lor de kilograme.
Mugurel trebuie să împacheteze toate aceste fructe, însă producătorul său de cutii îi oferă două variante, din care poate alege doar una: fabricarea a K cutii pentru portocale și K cutii pentru banane (împachetare separată), sau fabricarea a K cutii mixte (împachetarea portocalelor și a bananelor împreună).

Însă, totul are un preț. Fie \(c_{port}\), \(c_{ban}\), \(c_{mixt}\) capacitățile cutiilor de portocale, banane respectiv mixte. Atunci, Mugurel va plăti \(A \; maci \cdot c_{port} + B \; maci \cdot c_{ban}\) sau \(C \; maci \cdot c_{mixt}\), în funcție de varianta de împachetare aleasă, unde \(A\), \(B\) și \(C\) vor fi prețuri oferite de producător. Mugurel va alege metoda de împachetare astfel încât suma de bani cheltuită să fie cât mai mică.

După ce plătește și primește cutiile, începe împachetarea. De fiecare dată când închide o cutie, o pune la finalul șirului de cutii deja închise (Mugurel se ocupă mai întâi de grămada de portocale, apoi de cea de banane). La finalul împachetării fructelor, el trebuie să împartă șirul de cutii în două șiruri consecutive, pe care le vom numi loturi.

Loturile vor fi trimise către cele două cetăți ale Imperiului, însă Mugurel nu vrea să pornească un război între cele două cetăți, așadar vrea să le împartă cu grijă. Numim discrepanță a unui lot diferența dintre cutia cu număr maxim de kilograme și cea cu număr minim. Împărțirea trebuie făcută astfel încât suma discrepanțelor celor două loturi să fie minimă, pentru împachetare.

Cu atâtea responsabilități pe cap, Mugurel vă roagă să-l ajutați cu afacerea.

între Juventus Torino și AC Milan și a notat pe o foaie cele N goluri în ordinea în care ele au fost marcate. La fiecare gol marcat de Juventus a scris pe foaie cifra 1 și la fiecare gol marcat de Milan a scris pe foaie cifra 2.

Scorul meciului, la un moment dat, se exprimă prin două numere, primul reprezentând numărul total de goluri marcate până la acel moment de prima echipă, Juventus Torino, iar al doilea reprezentând numărul total de goluri marcate până la acel moment de a doua echipă, AC Milan.

Scorul este egal dacă cele două numere sunt egale, iar o echipă conduce echipa adversă în joc dacă numărul de goluri marcate de ea este strict mai mare decât cele marcate de echipa adversă.

Scorul final este cel obținut la încheierea jocului.

Spunem că revenirea în forță este o situație în care o echipă, care este condusă, înscrie un număr corespunzător de goluri până când preia conducerea, fără ca echipa adversă să fi marcat vreun gol în tot acest timp.

Cerințe:

1. Determinați scorul final.

2. Determinați numărul de scoruri egale care au fost înregistrate pe parcursul jocului, începând cu cel de pornire. Scorul de pornire, 0 − 0, este considerat egal.

3. Determinați numărul de goluri corespunzător celei mai mari reveniri în forță din joc (numărul maxim de goluri succesive marcate de o echipă la o revenire în forță).

Copiii de la școala din oraș primesc daruri înaintea vacanței. Există o cutie foarte mare care conține 𝑁 bomboane ce le pot fi distribuite tuturor copiilor prezenți la festivitatea care s-a organizat, astfel încât, întotdeauna, toți să primească același număr de bomboane, 𝐵.

Cerințe:

1. Să se determine valoarea maximă a lui 𝐵, știind că la festivitate sunt prezenți exact 𝑋 copii, iar după distribuire este posibil să fie lăsate unele bomboane în cutie.
2. Să se determine numărul maxim de copii care pot fi prezenți la festivitate, astfel încât să fie distribuite 𝑡𝑜𝑎𝑡𝑒 bomboanele din cutie, iar valoarea lui B să fie mai mare sau egală cu 2.
3. Să se determine numărul minim de bomboane care pot fi lăsate în cutie, după distribuire, astfel încât la festivitate să fie prezenți cel puțin 𝑋 copii, iar valoarea lui 𝐵 să fie mai mare sau egală cu 𝑌. Corespunzător numărului de bomboane lăsate obținut și condițiilor precizate, se determină, de asemenea, numărul de copii prezenți precum și valoarea lui 𝐵. În cazul în care sunt mai multe variante ce respectă aceste condiții, se alege cea pentru care numărul de copii prezenți este maxim posibil.

Oglinditul unui număr natural x este numărul obținut prin parcurgerea cifrelor lui x de la dreapta la stânga, ignorându-se cifrele nule de pe ultimele poziții ale lui x. De exemplu, oglinditul lui 103 este 301, în timp ce oglinditul lui 2500 este 52. O pereche de numere naturale distincte x și y se numește pereche oglindită dacă atât x este oglinditul lui y, cât și y este oglinditul lui x. De exemplu, numerele x = 42 și y = 24 formează o pereche oglindită, însă numerele x = 1 și y = 100 nu formează o pereche oglindită. Un număr natural x este considerat palindrom dacă x este egal cu oglinditul său. De exemplu, numărul 42124 este palindrom. Din două numere distincte se poate forma un număr nou prin alipirea unuia la dreapta celuilalt. De exemplu, din numerele 124 și 42 se pot obține numerele 12442 (din alipirea lui 42 la dreapta lui 124) și 42124 (din alipirea lui 124 la dreapta lui 42). Fie un șir de numere naturale a[1], a[2], ..., a[n]. Determinați:

1) Numărul perechilor de indici (i, j), cu 1 ≤ i < j ≤ n, având proprietatea că a[i] și a[j] formează o pereche oglindită.
2) Cel mai mare număr palindrom care se poate forma prin alipirea a două numere distincte din șir.

Alex este un băiat căruia îi place să citească și care contorizează cât de mult a citit pe parcursul ultimelor n zile. Mai precis, el și-a notat câte pagini a citit în fiecare dintre acestea. Chiar dacă pasiunea lui este literatura, își dorește să progreseze și la informatică. Alex și-a pus două întrebări legate de șirul format din numărul de pagini citite de el în ultimele n zile, dar după ce a petrecut câteva zile gândindu-se la ele și-a dat seama că sunt prea dificile pentru el. Ajutați-l să găsească răspunsurile! Fie numărul n, numărul p și acel șir de valori notate de Alex în cele n zile. Determinați răspunsul la următoarele întrebări care îl frământă pe Alex:

1) Câte triplete de numere aflate pe poziții consecutive în șirul dat îndeplinesc condiția ca cel mai mare divizor comun al lor să aibă cel mult p divizori naturali?
2) Care este lungimea maximă a unei secvențe din șirul dat, în care cel mai mare divizor comun al oricărui triplet de numere situate pe poziții consecutive are cel mult p divizori naturali?

În sistemul solar Stelarion sunt 99 de planete. Planeta Hazard găzduiește campionatul de Robotron pe echipe. Jucătorii sunt înregistrați în ordinea sosirii lor, indiferent de planeta de pe care provin. Anul acesta s-au înscris în campionat N jucători de pe M planete. Jucătorul înregistrat al i-lea (cu i de la 1 la N) primește două numere: E[i] — numărul trecut pe ecuson și P[i] — puterea jucătorului. Numărul trecut pe ecuson este format din codul planetei jucătorului CP (numărul format din ultimele două cifre de pe ecuson) și codul jucătorului CJ (numărul format din restul cifrelor).
1) Să se determine numărul M al echipelor participante și codul H al planetei gazdă Hazard, știind că numărul jucătorilor din echipa planetei gazdă este strict mai mare decât numărul jucătorilor oricărei alte echipe.
2) Să se determine codul planetei de pe care provine echipa câștigătoare la runda K și codul jucătorului care aduce victoria acestei echipei la aceasta rundă.

La o conferință MUN (Model United Nations) participă N delegați din întreaga lume. Fiecare delegat primește un cod format din cel puțin una și cel mult 10 litere mari distincte ale alfabetului englez. Delegații din aceeași țară au codul format din exact aceleași litere, eventual dispuse în altă ordine. Codurile a doi delegați din țări distincte diferă prin cel puțin o literă care apare în unul, dar nu și în celălalt.

1) Să se determine D, numărul delegațiilor, adică numărul de țări reprezentate la conferință de cel puțin un delegat.

2) Să se determine două numere naturale, S și V, S reprezentând numărul minim de delegați care pot primi statut de supervizor, iar V numărul de vorbitori corespunzător numărului S determinat.

3) Să se afișeze codurile corespunzătoare numărului maxim de vorbitori ce pot sta la masa rotundă, în ordinea așezării la masă, începând de la oricare dintre ei, astfel încât dacă sunt mai multe posibilități de aranjare se va afișa cea mai mică din punctul de vedere lexicografic.