Lista de probleme 18

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.

î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ță).

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.

Macarie a primit o nouă temă la informatică, având următorul enunț: Se consideră un șir de numere naturale nenule, A cu N elemente. Fie șirul crescător D format din toți divizorii naturali, nu neapărat distincți, ai elementelor din A. De exemplu, pentru N = 4 și A = (6,2,3,2), avem șirul D = (1,1,1,1,2,2,2,3,3,6). Cunoscându-se un șir Poz format din Q numere naturale nenule, reprezentând poziții din șirul D să se determine, pentru fiecare dintre acestea, elementul corespunzător din șirul D.

David este mare zugrav și nu se duce nicăieri fără trafaletul său magic. El are la dispoziție o matrice A cu N linii și M coloane, care este colorată în alb și negru, asemenea unei table de șah. Fiecare celulă a matricei conține o valoare asociată. David vopsește o submatrice cu alb sau negru la alegere. Trafaletul adună automat (pentru că este magic) valorile din celulele vopsite care nu își schimbă culoarea, și scade valorile din celulele vopsite care își schimbă culoarea. Rezultatul acestui calcul este punctajul lui David. Cum David nu a reușit până acum să combine zugrăvitul și programarea, vă roagă pe voi să îl ajutați să obțină punctajul maxim!

Se cunosc înălțimile a N vârfuri, plasate de la stânga la dreapta, în cadrul unui lanț muntos. Dacă plasăm o santinelă pe un vârf de o anumită înălțime, aceasta veghează vârful respectiv și maximum K vârfuri la stânga și maximum K vârfuri la dreapta acestuia, dar cu condiția ca înălțimile acestor vârfuri vegheate să fie mai mici sau egale cu înălțimea vârfului pe care se află santinela. Date fiind N, K și înălțimile celor N vârfuri, să se determine:

• Numărul maxim de vârfuri consecutive, începând de la primul vârf al lanțului muntos (inclusiv acest vârf), ce pot fi vegheate cu o singură santinelă.
• Numărul minim de santinele necesare ca toate vârfurile să fie vegheate.

Î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ă.

Pentru un șir de n numere, să se găsească lungimea celei mai lungi secvențe care conține maximum 3 numere distincte. Un exemplu de astfel de secvență este: 9 1 0, dar un exemplu de secvență care nu respectă această regulă este 4 2 1 3 4. Dându-se t șiruri a de n numere, să se găsească lungimea celei mai lungi secvențe care conține maximum 3 numere distincte.

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?

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.