Lista de probleme 471

Filtrare

Dificultate

Operații intrare/ieșire

Etichete

#2710 cuv

Se dau n cuvinte formate doar din litere mici. Trebuie construit un nou cuvânt C de n litere format astfel: prima literă a lui C este din primul cuvânt, a doua literă este din al doilea cuvânt, …, a n-a literă este din cel de-al n-lea cuvânt. În plus, literele cuvântului C trebuie să fie distincte. Să se determine cuvântul C minim lexicografic ce se poate forma utilizând litere distincte extrase din cuvintele inițiale.

#2707 matad

Dându-se o matrice de numere întregi cu n linii și n coloane, să se verifice dacă este sau nu matrice de adiacență asociată unui graf neorientat.

Majoritatea copiilor sunt sociabili și relaționează ușor cu cei de vârsta lor dar sunt și copii mai timizi sau mai puțin atrași de activitățile de grup. În urma studierii comportamentului unui eșantion de n copii, s-a stabilit, pentru fiecare doi copii dacă relaționează sau nu. Pentru serbarea de sfârșit de an, s-a propus realizarea unei scenete și este necesară selectarea unei grupe cât mai numeroase de micuți dar fără a depăși k, numărul maxim de personaje. Rolurile presupun interacțiunea fiecărui copil selectat cu toți ceilalți mici actori care joacă în scenetă. Să se determine cel mai mare număr de copii care pot fi implicați în serbare, știind ca fiecare dintre aceștia trebuie să relaționeze cu toți ceilalți copii din scenetă.

Olimpiada Municipală Iași, clasele XI-XII

#2704 datorii

Pentru a nu intra în faliment, noua conducere a fabricii OLDTRICK a derulat un plan de restructurate în n etape. În fiecare etapă, fabrica a împrumutat de la bancă o sumă ai. La terminarea celor n etape, fabrica a început să restituie împrumuturile astfel: primul împrumut a fost restituit, apoi conducerea fabricii a constatat că nu-și poate achita toate datoriile și a hotărât să restituie doar sume care nu au fost împrumutate în etape succesive. Să se determine care este suma totală maximă pe care o poate restitui fabrica. Cunoscând n – numărul de etape, ai – suma împrumutată în etapa i (1 ≤ i ≤ n), să se determine care este suma totală maximă pe care o poate restitui fabrica, știind că primul împrumut este întotdeauna achitat.

Se dă un șir de n numere naturale. Să se determine numărul minim de subșiruri strict crescătoare în care se poate partiționa șirul.

Se dă un șir de n numere naturale. Să se determine numărul minim de subșiruri strict crescătoare în care se poate partiționa șirul.

#2675 scara1

Domnul G are de urcat o scară cu n trepte. În mod normal, la fiecare pas pe care îl face, el urcă o treaptă. Pe k dintre aceste trepte se află câte o sticlă cu un număr oarecare de decilitri de apă, fie acesta x. Dacă bea toată apa dintr-o astfel de sticlă, forța și mobilitatea lui G cresc, astfel încât, la următorul pas el poate urca până la x trepte, după care, dacă nu bea din nou ceva, revine la “normal”. Sticlele cu apă nu costă nimic. Cantitatea de apă conținută de aceste sticle poate să difere de la o treaptă la alta.
Pe j trepte se află câte o sticlă cu băutura energizantă. Şi pentru aceste sticle, cantitatea de băutură energizantă poate să difere de la o treaptă la alta. Să presupunem că într-una dintre aceste sticle avem y decilitri de băutură energizantă. Dacă bea q (q ≤ y) decilitri dintr-o astfel de sticlă, la următorul pas G poate urca până la 2q trepte, după care şi în acest caz, dacă nu bea din nou ceva, el revine la “normal”. Însă băutura energizantă costă: pentru o cantitate de q decilitri consumaţi, G trebuie să plătească q lei grei.
Pot exista trepte pe care nu se află nici un pahar, dar şi trepte pe care se află atât o sticlă cu apă cât şi una cu băutură energizantă. În astfel de situaţii, nu are rost ca G să bea ambele băuturi deoarece efectul lor nu se cumulează; el poate alege să bea una dintre cele două băuturi sau poate să nu bea nimic.
Determinaţi p, numărul minim de paşi pe care trebuie să îi facă G pentru a urca scara, precum şi suma minimă pe care trebuie să o cheltuiască G pentru a urca scara în p paşi.

#2654 sortall C++

Pentru un șir de numere \( A \) se definește următoarea funcție de cost: \( f(A) = 1 \cdot v_1 + 2 \cdot v_2 + … + k \cdot v_k \), unde \( [v_1, v_2, …, v_k] \) sunt valorile distincte ale lui \( A \), ordonate crescător.

Fiind dat un șir de N numere naturale A, să se calculeze suma aplicării funcției f pe toate subsecvențele lui A (i.e. suma după (1 ≤ i ≤ j ≤ N) din f(A[i...j]), unde A[i…j] este subsecvența de la i la j).

#2631 h4

Spunem că două cuvinte sunt anagrame dacă au aceleași litere, eventual în altă ordine. De exemplu, abac și baca sunt anagrame, dar abac și abbc nu sunt. Dându-se un șir de cuvinte separate prin spații sau enter, vom considera că dacă mai multe cuvinte sunt anagrame, atunci ele fac parte din același grup. Să se determine numărul maxim de cuvinte dintr-un grup.

#2639 radiera

Un numar natural se numeste “numar scara” daca toate cifrele lui sunt ordonate crescator, de la stanga la dreapta. De exemplu 11223569 este un “numar scara”, dar 98873 si 122429 nu sunt. Mihnea primeste o radiera si o foaie pe care este scris un sir de cifre. El trebuie sa stearga cat mai putine cifre cu proprietatea ca daca lipim cifrele ramase in ordinea din sir vom avea un “numar scara”.