Lista de probleme 192

Filtrare

#1431 Points

Fie o mulţime de n puncte diferite în plan cu coordonate naturale. Numim o submulţime nevidă ordonată a acestor puncte subșir descrescător dacă pentru oricare două puncte consecutive Ai(xi, yi) şi Ai+1(xi+1, yi+1) avem xi ≤ xi+1 şi yi ≥ yi+1.

Dându-se cele n puncte, calculaţi numărul de subșiruri descrescătoare care se pot forma.

#2396 arbsum

Se consideră un arbore cu n noduri numerotate de la 1 la n. Se știe că rădăcina arborelui este nodul 1. Fiecare nod i are asociat un număr natural nenul v[i]. Să se determine suma maximă care se poate obține alegând în mod convenabil o submulțime de noduri, astfel încât dacă este ales un nod i, în submulțime nu poate fi nici nodul tată al lui i, nici eventualii fii ai lui i.

Se considera un vector cu n elemente. Sa se afle cate subsiruri strict crescatoare de lungime p se pot forma folosind numerele sale.

Fiind dată o matrice pătratică de dimensiune n cu valori 0 și 1, să se determine dimensiunea maximă a unei submatrice ce conține numai valori 1.

Concursul Interjudețean de Informatică „Memorial Ștefan Dârțu”, ediția a XI-a, 12 decembrie 2015, Vatra Dornei

Gigel, un personaj cunoscut, vrea de data aceasta să își construiască o casă. Astfel, el cumpără un teren, reprezentat sub forma unei matrice binare cu n linii și m coloane, dar datorită lipsei de experiență în tranzacții imobiliare este păcălit, deoarece există pe teren zone afectate în care nu se poate construi, marcate în matrice cu 0. Celelalte zone în care se poate construi sunt marcate cu 1.

Gigel acceptă că a greșit și nu are altceva de făcut decât să își construiască casa unde este posibil. Acesta caută pe terenul achiziționat o bucată de teren pătrată de dimensiune cât mai mare, pentru care toate zonele ce o alcătuiesc să fie utilizabile(marcate cu 1 în matricea binară a reprezentării terenului), în care își va construi casa.

Acesta nu se descurcă singur și vă roagă pe voi să îl ajutați să își rezolve această problemă.

#1463 Tmax

Să se determine câte T-uri de sumă maximă există, precum și această sumă maximă.

#1370 pepeuri

Să se afle câte numere naturale cu n cifre au suma oricăror două cifre alăturate pătrat perfect.

Se consideră un şir format din n numere naturale şi un număr dat k. Să se determine numărul secvenţelor din şir care au proprietatea că suma elementelor secvenţei este de cel puţin de k ori mai mare sau egală decât numărul elementelor secvenţei.

#1548 Minioni

Kevin și-a deschis un nou complex hotelier în Dubai și acesta se compune din M clădiri etichetate de la 1 la M. La inaugurare s-a hotărât să îi invite pe toți prietenii lui, cei N minioni.

Inițial complexul este gol, iar primii invitați vor fi Bob, apoi Stuart. Kevin s-a gândit să invite exact un prieten în fiecare zi pentru a putea organiza o petrecere la fiecare sosire a unui minion în complexul său. Zgomotul petrecerii este egal cu numărul de minioni situați în interiorul clădirii.

În calitate de manager, Kevin nu este deosebit de încântat de reclamațiile cauzate de zgomotul petrecerilor, astfel încât el va goli ocazional o anumită clădire pentru a păstra petrecerile la un nivel de zgomot rezonabil. Când este nevoit să facă această golire, clădirea rămâne goală, toți minionii fiind mutați într-un complex diferit. Conducerea poate decide să facă acest lucru la sfârșitul oricărei zile, dar pentru a limita costurile și-a dat seama că nu poate realiza această schimbare de un număr mai mare de K ori.

Ajutați-l pe Kevin, știind care sunt clădirile unde se vor caza prietenii lui, să determine nivelul minim total de zgomot posibil (suma tuturor nivelurilor de zgomot a celor N petreceri), care poate fi realizat prin golirea unor clădiri de un număr maxim de K ori.

#1679 Euro

După calificarea la campionatul european de fotbal din Franța, având în vizor N jucători din care trebuie să convoace câțiva în echipa națională, selecționerul României a apelat la niște metode mai puțin ortodoxe. Acesta a mers la vrăjitoarele renumite din Craiova pentru a-l ajuta să găsească formula câștigătoare pentru meciul de deschidere cu Franța. Vrăjitoarele, după descântece îndelungate, au ajuns la concluzia că lotul de jucători trebuie sa aibă valoarea exact X și coeficientul de aroganță cât mai mic. Valoarea unui lot de jucători e definită ca suma valorilor jucătorilor ce intră în componența lotului. Coeficientul de aroganță al unui lot de jucători e definit ca diferența dintre valoarea maximă a unui jucător din lot și valoarea minimă a unui jucător din lot. Se mai știe că valoarea lotului nu poate depăși o valoare cunoscută Vmax. Un lot de jucători e definit ca o submulțime nevidă de jucători aleși dintre cei N. Atenție, un lot poate fi format și dintr-un singur jucător.

Se dă numărul N de jucători, numărul Vmax definit mai sus și valoarea fiecărui jucător. Selecționerul României a găsit formula câștigătoare și e curios dacă puteți și voi. Fiindcă nu are încredere totală în vrăjitoare, acesta vă cere să aflați pentru fiecare valoare X din intervalul [1,Vmax] coeficientul de aroganță minim posibil pentru care există cel puțin un lot dintre cei N jucători cu valoare exact X. Dacă nu se poate obține nici un lot de valoare exact X, se consideră ca răspuns -1.