Lista de probleme 3

Apropiindu-se toamna și fiind în criză de timp din cauza războiului iminent, Ștefan a hotărât să supravegheze personal recoltarea strugurilor de la viile Huși, din apropiere de Vaslui, vie la care Ștefan ținea foarte mult. Strugurii recoltați au fost depozitați în grămezi la marginea fiecărui rând de vie. Se cunoaște, pentru fiecare dintre cele N rânduri, cantitatea (în ocale) recoltată de pe rândul respectiv. Ștefan era un conducător corect astfel încât a hotărât ca toate căruțele disponibile la un moment dat să transporte aceeași cantitate de struguri.
1) Determinați cea mai lungă secvență de grămezi pe care le pot transporta cele N căruțe în prima tură.
2) Determinați o modalitate de transport a tuturor strugurilor la cramă, conform cerințelor lui Ștefan.

Se dă un șir V ce conține N numere întregi numerotate începând de la 1: V[1], V[2], ..., V[N] și două numere naturale nenule K și L, cu proprietatea că: 1 ≤ K ≤ L ≤ N. Mihai studiază doar secvențele de lungime L, adică secvențele formate din exact L elemente situate pe poziții alăturate în acest șir V. El își poate pune următoarea întrebare: “Dacă aș rearanja, în ordine crescătoare, elementele secvenței de lungime L care începe la poziția poz în șirul V, ce valoare s-ar afla pe poziția a K-a în cadrul secvenței rezultate?”. Pentru secvența din șir care începe la poziția poz și are L elemente, adică V[poz], V[poz+1], ..., V[poz+L-1], valoarea elementului de pe poziția a K-a în cadrul secvenței este V[poz+K-1]. Ajutați-l pe Mihai să afle care este răspunsul corect pentru Q întrebări de tipul descris mai sus!

După ce a scăpat de Spân și a devenit împărat, Harap-Alb a decis să își construiască un nou castel în împărăția sa ce poate fi reprezentată cu ajutorul sistemului de coordonate carteziene. El știe că Roș-Împărat a construit N+1 garduri dreptunghiulare, însă știe și că acesta este cam zgârcit și nu a folosit cele mai bune materiale. Harap-Alb a învățat din greșeli, iar acum încearcă să se ferească de pericole cât de mult poate. De aceea, el vrea să își amplaseze castelul într-un punct din sistemul cartezian care să se afle în interiorul a cel puțin N dintre cele N+1 garduri. Fiind date numărul natural nenul N și coordonatele celor N+1 garduri (perechi de colțuri stânga-sus și dreapta-jos), să se determine (în cazul în care există) punctul cel mai apropiat de originea sistemului de coordonate unde Harap-Alb își poate amplasa castelul astfel încât acesta să se afle în interiorul a cel puțin N garduri.