Lista de probleme 9

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

Se dă un şir cu n elemente, numere întregi. Determinaţi secvenţa de elemente cu suma maximă.

#3281 sminus

Fie un șir a1, a2, …, aN de numere întregi. În acest șir se alege o pereche de indici (x, y), 1 ≤ x ≤ y ≤ N și se inversează semnul tuturor componentelor secvenței ax, ax+1, …, ay. Să se determine o pereche de indici x y astfel încât după inversarea semnului componentelor secvenței ax, ax+1, …, ay suma elementelor din vector să fie minimă.

#1804 ursulet

Ursuleţul Grizzlyuță are de parcurs zone de diferite altitudini, care sunt numere întregi. Atunci când trece dintr-o zonă în alta oboseala ursuleţului creşte cu o valoare egală cu altitudinea zonei în care trece. Să se determine zonele în care acesta acumulează oboseală maximă.

#3844 KSum

După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N și K apoi un vector cu N elemente, din acest vector care este suma maximă a unei secvențe (elemente adiacente) de lungime cel puțin K. A zis să vă întrebe pe voi cum se face.

#3846 KSum2

După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N și K apoi un vector cu N elemente, din acest vector care este suma maximă a unei secvențe (elemente adiacente) de lungime cel puțin K. A zis să vă întrebe pe voi cum se face.

Se dă o matrice de numere întregi cu n linii și n coloane. Să se determine suma maximă care se poate obține dintr-o submatrice.

Se consideră un șir A cu N elemente întregi nenule. Numim secvență a șirului A orice succesiune de elemente aflate pe poziții consecutive în șir: Ai, Ai+1, …, Aj cu 1 ≤ i < j ≤ N. Prin lungimea secvenței înțelegem numărul de elemente care o compun.

Pentru orice secvenţă Ai, Ai+1, …, Aj, vom numi split-point un indice k, i ≤ k < j, care împarte secvența în două subsecvențe nevide: Ai, Ai+1, …, Ak, respectiv Ak+1, Ak+2, …, Aj.

Fie Dmax valoarea absolută maximă a diferenței sumelor elementelor celor două subsecvențe separate de un split-point, luând în considerare toate secvenţele Ai,Ai+1,…,Aj posibile şi fie Lmax lungimea maximă a unei secvenţe caracterizată de valoarea Dmax.

Cunoscând N şi valorile elementelor şirului A, să se determine Dmax şi Lmax.

După un rezultat slăbuț la un concurs de informatică, Cristina s-a cam supărat. Dan vrea să-i ridice moralul și știe că cel mai bun mod în care poate face asta este ciocolata. Totuși, Dan nu este dispus să-i ofere Cristinei toată ciocolata pe care o are (și el a avut un rezultat slab la concurs, deci.. și el trebuie să-și ridice moralul).

Astfel, îi propune Cristinei următoarea ofertă: ”Desenează pe o hârtie un caroiaj format din N linii și M coloane pe care îl umple cu valori întregi. Cristina va primi un număr de pătrățele de ciocolată egal cu suma valorilor dintr-un dreptunghi ales de ea.”

Deoarece Cristina este prea bosumflată ca să rezolve această “provocare” și prea obosită ca să-l convingă pe Dan să-i dea ciocolata pur și simplu, vă roagă pe voi să o ajutați. (Poate primiți și voi niște ciocolată dacă rezolvați problema. Poate…)

Cunoscându-se configurația caroiajului, determinați numărul maxim de pătrățele de ciocolată pe care Cristina îl poate obține alegând un dreptunghi din matrice, precum și coordonatele celor patru colțuri ale acestuia

#3582 sotron1

Pe asfalt este desenat cu cretă un şotron, caroiaj format din n*n căsuţe având aceleaşi dimensiuni (câte n căsuţe pe fiecare din cele n rânduri).

În fiecare căsuţă este scris câte un număr întreg din intervalul [-100, 100]. Fiecare jucător are câte o piatră pe care o aruncă într-o căsuţă a şotronului, şi sărind într-un picior, împinge piatra din căsuţă în căsuţă, pe un anumit traseu astfel încât punctajul obţinut din suma numerelor de pe traseul parcurs să fie cât mai mare.

Numerele din căsuţele şotronului sunt scrise cu două culori albastru şi alb, astfel încât să nu existe două căsuţe alăturate (pe cele patru direcţii Nord, Est, Sud, Vest) având numere scrise cu aceeaşi culoare. Întotdeauna, prima căsuţă din primul rând al şotronului are înscris un număr de culoare albastră.

Se stabilesc apoi, următoarele reguli ale jocului:

  • la începutul jocului, piatra poate fi aruncată în oricare căsuţă a şotronului. Din poziţia respectivă jucătorul îşi conduce piatra până la sfârşitul traseului stabilit de el;
  • dintr-o căsuţă în care numărul este scris cu albastru, piatra poate fi deplasată doar în căsuţa vecină pe direcţia Nord;
  • dintr-o căsuţă în care numărul este scris cu alb, piatra poate fi deplasată doar în căsuţa vecină pe direcţia Est;
  • jucătorul poate alege orice căsuţă (inclusiv cea în care a aruncat piatra) pentru a încheia jocul, atâta timp cât piatra nu iese din şotron.

Să se scrie un program care să determine cel mai mare punctaj care se poate obţine jucând şotron după regulile stabilite.