Lista de probleme 100

Se consideră N vectori cu elemente întregi, numerotați de la 1 la N, sortați crescător, fiecare vector având un număr precizat de elemente.

Să se răspundă la Q întrebări de tipul:
a) 1 i j, cu semnificaţia: care este minimul dintre modulele diferențelor oricăror două elemente, primul element aparținând vectorului numerotat cu i, iar cel de al doilea element aparținând vectorului numerotat cu j ?
b) 2 i j, cu semnificația: care este valoarea ce se găsește pe poziția mediană în vectorul obținut prin interclasarea vectorilor având numerele de ordine i,i+1,…,j (i<j).

Manole a învățat de la profesorul de informatică cum să calculeze suma elementelor oricărei matrice A cu N linii și M coloane. El numerotează liniile de la 1 la N și coloanele de la 1 la M. Mai mult, Manole fiind extrem de pasionat de numere, va calcula sumele tuturor subtablourilor din cadrul matricei A. Șirul acestor sume îl scrie pe o hârtie, după ce l-a ordonat crescător.

Prin subtablou el înțelege o zonă dreptunghiulară din matricea A, identificată prin colțul stânga-sus (x1,y1) şi colţul dreapta-jos (x2,y2), elementele subtabloului fiind toate elementele A[i][j] pentru care x1≤i≤x2 şi y1≤j≤y2. Suma unui subtablou este suma tuturor elementelor sale.

La proba de sărituri cu schiurile din cadrul jocurilor olimpice de iarnă participă N concurenți, numerotați cu numere de la 1 la N.

Regulile de desfășurare a probei sunt următoarele:

• concurenții evoluează pe rând, în ordine de la 1 la N;
• fiecare concurent va efectua o singură săritură;
• după efectuarea săriturii fiecare concurent primește un anumit punctaj;
• pe tot parcursul concursului, comisia de arbitri are obligația să alcătuiască o listă cu punctajele obținute de concurenți, în ordinea evoluției lor;
• evoluția unui concurent durează exact un minut;
• nu se face pauză între evoluțiile a doi concurenți care au numere de ordine consecutive;
• afișarea punctajului nu necesită timp suplimentar după efectuarea săriturii;
• proba se încheie la un minut după evoluția ultimului concurent.

Pe tot parcursul concursului se ține în mod neoficial și un clasament parțial, pe baza rezultatelor obținute de concurenții care au evoluat până în acel moment. Asta pentru că șeful comisiei de arbitri are o curiozitate aparte și pune K întrebări sub forma următoare: Câte minute s-a ocupat primul loc din clasament cu un punctaj egal cu X puncte? Dacă nici un concurent nu s-a clasat pe primul loc cu X puncte atunci primește ca răspuns valoarea 0.

Scrieți un program care determină răspunsul pentru fiecare dintre cele K întrebări puse de șeful comisiei de arbitri.

La marginea unei păduri sunt N stupi aşezaţi în linie. Ei au asociate numere de ordine de la 1 la N, în ordinea în care apar. Fiind sezonul florii de salcâm, albinele colectează foarte repede mierea. La finalul fiecărei zile, din satul aflat în apropiere vine un apicultor la volanul unui camion pentru a o recolta. Capacităţile camioanelor pot fi diferite. Procesul de strângere a mierii decurge astfel: camionul pleacă din dreptul stupului 1 şi încarcă întreaga cantitate de miere din acesta, apoi trece la stupul 2 şi procedează la fel şi aşa mai departe. Dacă odată ajuns la un stup camionul nu poate colecta întreaga cantitate de miere din acel stup, acesta întrerupe acţiunea de colectare şi se întoarce în sat. În ziua următoare, albinele din stupii de unde s-a recoltat refac cantitatea de miere din ziua anterioara. În plus, în fiecare stup cantitatea de miere creşte cu un kilogram faţă de ziua anterioară.

Dându-se N, numărul de stupi, cantitatea de miere existentă în fiecare la finalul primei zile, numărul M de zile în care se face colectarea mierii şi capacitatea camionului care trece în fiecare zi, se cere numărul de stupi din care se recoltează miere în fiecare dintre cele M zile.

Un superstring este un şir infinit format din numere naturale nenule scrise fără spaţii între ele, începând cu 1: 1223334444...1010... (fiecare număr x apare de exact x ori).

Să se răspundă la T întrebări de forma: Ce cifră se află în superstring pe poziţia k?

Pentru următorul an școlar admiterea celor N elevi în liceu se va face pe baza unor evaluări complexe. Fiecare dintre viitorii elevi ai clasei a IX-a va primi, în urma testelor și probelor pe care le va susține, un punctaj (număr natural nenul) cu care va participa la admiterea electronică.

Repartizarea fiecărui elev în clase se face în ordinea înscrierii respectând criteriile:

• Primul elev se repartizează în clasa cu numărul de ordine 1.
• În clasa în care este repartizat un elev nu există, până la momentul repartizării sale, nici un punctaj mai mare decât al său.
• Numărul claselor să fie cât mai mic posibil.

Determinaţi:

1. Punctajul primului elev care nu ar mai putea fi repartizat în prima clasă în condițiile în care toți elevii își doresc să fie repartizați în prima clasă(se aplică doar la cerința 1).
2. Numărul claselor ce se vor forma respectând criteriile.

O firmă de construcții imobiliare a achiziționat recent un teren dreptunghiular de forma unei fâșii de dimensiune 1 × N, fiind apoi împărțit în parcele de dimensiune 1 x 1. Pe fiecare dintre cele N parcele de dimensiune 1 × 1 firma poate construi câte o casă, dacă există clienți interesați. Terenul este amplasat pe una dintre cele șapte coline ale unui oraș vestit. Astfel, dacă numerotăm parcelele cu numere consecutive de la 1 la N, altitudinile asociate acestor parcele vor fi în ordine strict crescătoare până la o anumită poziție, unde se atinge altitudinea maximă a acestui teren, iar pentru pozițiile următoare altitudinile sunt în ordine strict descrescătoare, fiind de partea cealaltă a vârfului colinei. Scrieți un program care determină pentru fiecare cerere j (1 ≤ j ≤ M) dacă firma poate îndeplini restricția respectivă, mai exact dacă există măcar o parcelă i (1 ≤ i ≤ N) pentru care hi = qj.

Se dă o matrice binară cu n coloane și m linii. Coloanele sunt numerotate de la stânga la dreapta cu valori de la 1 la n, iar liniile sunt numerotate de jos în sus cu valori de la 1 la m.
Matricea dată are o formă particulară, astfel că pentru fiecare coloană i de la 1 la n toate elementele matricei de pe coloana respectivă au valoarea 1 pentru toate liniile cuprinse în intervalul [1, h[i]] și în rest valoarea 0. Valorile h[i] sunt numere naturale date în ordine crescătoare (h[i-1] ≤ h[i], 1 ≤ i ≤ n).
Să se răspundă la q întrebări de forma: dându-se numerele A, B, C, D se cere suma elementelor din submatricea determinată de zona dreptunghiulară având colțul stânga-jos în coloana A și linia B, iar colțul dreapta-sus în coloana C și linia D.

Micul Prinț a ajuns în țara numerelor palindrom cu număr impar de cifre unde a primit de la sfetnicul regelui o listă care conține N numere naturale, fiecare cu număr impar de cifre. Un număr este palindrom dacă prima lui cifră este egală cu ultima, a doua cu penultima, ș.a.m.d. Acesta i-a transmis că regele este foarte bolnav. Odată cu regele, numerele din listă s-au îmbolnăvit și ele. Sfetnicul i-a spus că lista corectă poate fi obținută prin înlocuirea fiecărui număr din ea cu cel mai mic palindrom mai mare sau egal cu numărul respectiv.
După ce a urmat recomandarea sfetnicului, Micul Prinț a constatat că în lista corectă obținută toate palindromurile sunt distincte. Uitându-se mai cu atenție la palindromurile din această listă, a observat că există perechi de palindromuri în care cel mai mic se poate obține din cel mai mare prin ștergerea aceluiași număr de cifre de la ambele capete. De exemplu pentru perechea 7531357 și 313 palindromul 313 se obține din 7531357 prin eliminarea a câte două cifre de la ambele capete ale sale.
Considerăm un șir de palindromuri din lista corectă și notăm cu X valoarea maximă a acestui șir. Vom spune că șirul este magic dacă toate palindromurile din el se pot obține după metoda descrisă mai sus, din palindromul de valoare X. Un exemplu de șir magic este 4, 53435, 7534357, 89753435798, presupunând că toate aceste numere se regăsesc în lista corectă.

Scrieți un program care citește numerele din lista primită de la sfetnicul regelui și afișează:
1) Lista corectă obținută de Micul Prinț;
2) Numărul de elemente ale celui mai lung șir magic care se poate obține din lista corectă;
3) Palindromurile din care este format cel mai lung șir magic, afișate în ordine crescătoare. Dacă există mai multe astfel de șiruri în lista corectă a Micului Prinț, se va afișa cel în care ultimul număr este cel mai mare.

Dan este un mare pasionat al fructelor, printre preferatele sale fiind strugurii şi pepenii. Însă recent şi-a descoperit și pasiunea pentru legume, în special pentru roşii, dar mai ales roşiile mici. Spre norocul lui, grădina bunicului este plină de roşii. Grădina are forma unei matrice cu N linii și M coloane cu elemente numere naturale, nu neapărat distincte, unde fiecare element din matrice reprezintă dimensiunea unei roşii. Matricea are proprietatea că oricare coloană are valorile ordonate crescător de sus în jos, adică de la prima spre ultima linie. Bunicul său îi cere să rezolve Q sarcini. Pentru fiecare sarcină, Dan primeşte un număr natural x şi trebuie să găsească o submatrice de arie maximă care începe de pe linia 1 a matricei care reprezintă grădina şi are toate elementele mai mici sau egale decât x. Pentru determinarea submatricei cerute, Dan are voie să mute toate valorile unei coloane în fața oricărei alte coloane. De asemenea, îi este permis să facă oricâte mutări de tipul acesta.
Să se calculeze aria maximă a unei submatrice care respectă specificațiile din enunț, pentru fiecare din cele Q sarcini date de către bunic.