Lista de probleme 51

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#2186 barci

Clasa din care faceţi parte merge în excursie! Principalul obiectiv este Lacul Roşu, o locaţie deosebit de frumoasă. Pentru a vă bucura cât mai mult de peisaj toţi elevii se vor plimba cu barca pe lac. Bărcile sunt de maxim două persoane şi au restricţiile următoare:

  • greutatea totală suportată de o barcă este C;
  • dacă în barcă se aşază două persoane, atunci diferența în modul dintre greutățile acestora trebuie să fie maxim B, în caz contrar barca nu este balansată și riscă să se răstoarne.

Dacă o singură persoană se aşază în barcă, nu se aplică restricția a doua. Care este numărul minim de bărci necesare pentru a putea plimba toţi elevii în condiţii de siguranţă?

Olimpiada Municipala de Informatica, Iasi, 2017

#2785 galeti

Avem n găleți numerotate de la stânga la dreapta numere de la 1 la n. Fiecare găleată conține inițial 1 litru de apă. Capacitatea fiecărei găleți se consideră nelimitată. Vărsăm gălețile una în alta, respectând o anumită regulă, până când toată apa ajunge în prima găleată din stânga. Vărsarea unei găleți presupune un anumit efort. Cunoscând numărul de găleți n și un număr natural e, să se determine o succesiune de vărsări în urma căreia toată apa ajunge în găleata cea mai din stânga și efortul total depus este exact e.

#2467 grup1

În școala unde învață, Andrei și Bogdan cunosc alți N elevi, etichetați cu numerele 1, 2, …, N. Dintre cei N elevi, o parte sunt prietenii lui Andrei. O parte dintre cei N elevi sunt dușmanii lui Bogdan. Se cunosc atât tichetele prietenilor lui Andrei, cât și etichetele dușmanilor lui Bogdan. Directorul școlii dorește să organizeze o excursie la care să participe Andrei, Bogdan și S dintre cunoscuții acestora, astfel încât din grupul celor S elevi să facă parte cel puțin K1 dintre prietenii lui Andrei și cel mult K2 dintre dușmanii lui Bogdan. Dorind să evite evenimente neplăcute, directorul va alege cei S elevi astfel încât numărul total al absențelor acumulate de aceștia, notat Sm, să fie minim.

Cunoscând valorile N, S, K1, K2, etichetele prietenilor lui Andrei, etichetele dușmanilor lui Bogdan, precum și numărul absențelor acumulate de fiecare dintre cei N elevi, determinați valoarea Sm obținută pentru un grup ce satisface condițiile de mai sus.

ONI 2018 clasa a X-a

#2473 jbb

Ana şi Bogdan joacă un nou joc – JBB (Jocul „Borcane cu Bomboane”). Pe tabla de joc sunt plasate N borcane cu bomboane. Se ştie câte bomboane se află în fiecare borcan: în borcanul i sunt B i bomboane (1≤i≤N).

Ca de obicei, Ana începe jocul, iar apoi cei doi jucători mută alternativ. Fiind prima la mutare, Ana alege un borcan din care va lua toate bomboanele.

Pe tabla de joc sunt trasate săgeţi care unesc borcanele. Mai exact, de la fiecare borcan i pleacă o singură săgeată către un alt borcan j. Săgeţile indică modul în care jucătorii se deplasează pe tabla de joc. Dacă există săgeată de la borcanul i la borcanul j, iar un jucător a luat bomboanele din borcanul i, atunci adversarul său e obligat să se deplaseze la borcanul j. Dacă în borcanul j va găsi bomboane, este obligat să le ia pe toate. Dacă borcanul j este gol, atunci adversarul poate să aleagă un alt borcan care conţine bomboane şi continuă jocul.

Evident, scopul fiecărui jucător este să aibă, la finalul jocului (atunci când toate borcanele au fost golite) cât mai multe bomboane.

Determinaţi numărul maxim de bomboane pe care Ana le-ar putea obţine respectând regulile jocului. Bineînţeles, atât Ana, cât şi Bogdan joacă optim (adică la orice pas, fiecare jucător va face cea mai bună mutare pe care poate să o facă).

#2485 nxy

Se consideră N, un număr natural nenul. Dorim să-l scriem pe N ca sumă a două numere naturale nenule x și y, astfel încât suma cifrelor numerelor x și y să fie maximă. Scrieţi un program care să rezolve următoarele cerinţe:

1. să determine suma maximă a cifrelor a două numere x și y cu proprietatea că x+y=N;
2. să determine două numere naturale nenule xmax și ymax cu proprietatea că xmax≥ymax, xmax+ymax=N, suma cifrelor lor este maximă, iar diferența xmax-ymax este maximă;
3. să determine două numere naturale nenule xmin și ymin cu proprietatea că xmin≥ymin, xmin+ymin=N, suma cifrelor lor este maximă, iar diferența xmin-ymin este minimă.

Legendarul vrăjitor Merlin se distrează în laboratorul său. El are N poțiuni magice (etichetate cu 1, 2, …, N) aranjate pe o singură linie într-o ordine dată. El dorește să le aranjeze în ordine crescătoare. Se va muta o singură poțiune la un moment dat. Prima poțiune mutată va fi cea etichetată cu 1, apoi cea etichetată cu 2 și așa mai departe. Bineînțeles, pentru a rezolva problema, Merlin va apela la magie. Fiecare poțiune poate fi mutată folosind una sau mai multe vrăji, trecând prin una sau mai multe poziții intermediare. Mutând o poțiune de la poziția I în poziția J, vraja va consuma (I-J)2 unități de energie. De exemplu, dacă există șapte poțiuni aranjate astfel 1, 7, 3, 4, 5, 2, 6 și Merlin mută poțiunea (etichetată cu 2) de la cea de-a șasea poziție la a doua poziție atunci noua aranjare va fi 1, 2, 7, 3, 4, 5, 6 cu (6-2)2 unități de energie consumate. Înainte de a începe distracția, Merlin a stabilit două criterii:
1. El nu dorește să fie prea obosit la sfârșitul zilei, de aceea nu dorește să consume mai mult de E unități de energie.
2. De asemenea el se plictisește repede, de aceea el dorește să rezolve problema cu un număr minim de vrăji. Calculați numărul minim de vrăji pe care le poate folosi Merlin pentru a rezolva problema.

Balcaniada de Informatică 2018, ziua 2

Cătălin lucrează la o firmă de transport de marfă. El se ocupă de planificarea traseelor pe care circulă camioanele. Există N trasee pe care pot merge camioanele, pe fiecare traseu poate circula cel mult un camion, iar acest camion nu poate depăși o limită de greutate ai. Firma deţine M camioane, fiecare camion poate circula pe maxim un traseu şi are o greutate bi. Ajutați-l pe Cătălin să planifice camioanele pe trasee în așa fel încât să poată circula cât mai multe camioane. Determinați numărul maxim de camioane care pot circula în același timp pe trasee și afișați o modalitate de a distribui camioanele pe trasee pentru a obține acest maxim.

Olimpiada Municipală Iași, clasele XI-XII

#2981 Inrudit

Două numere sunt considerate înrudite dacă sunt formate din exact aceleași cifre. Dându-se un număr X, să se găsească al K-lea număr înrudit, mai mare decât el.

#2966 yinyang

Se dă o matrice A cu N linii și M coloane, cu valori cuprinse între 1 și N∙M inclusiv, nu neapărat distincte. O operație constă în selectarea a două linii sau două coloane consecutive și interschimbarea acestora (swap). O matrice yin-yang este o matrice în care A[ i ] [ j ] ≥ A[ i ][ j – 1], pentru orice pereche (i, j) cu 1 ≤ i ≤ N și 2 ≤ j ≤ M și A[ i ][ j ] ≥ A[ i – 1][ j ], pentru orice pereche (i, j) cu 2 ≤ i ≤ N și 1 ≤ j ≤ M.

Să se determine numărul minim de operații necesare pentru a transforma matricea dată într-o matrice yin-yang.

#3049 scara2

Avem N persoane notate cu etichetele 1, 2, …, N, într-o ordine oarecare și o scară cu N trepte. Persoanele sunt așezate în șir indian, cu fața spre locul unde se află scara. Treptele scării sunt inițial neocupate. În mod repetat persoana aflată la acel moment la capătul din dreapta al șirului se poziționează pe scară pe prima treaptă neocupată, iar fiecare dintre persoanele aflate pe treptele inferioare coboară de pe scară și se repoziționează la capătul din dreapta al șirului, începând cu cea de la prima treaptă a scării. Acțiunea se oprește atunci când sunt ocupate toate treptele pe scară. Se cere să se afișeze etichetele persoanelor în ordinea în care acestea sunt așezate pe scară la final.