Diferente pentru problema/armate intre reviziile #4 si #15

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="armate") ==
bq. The dead will come North first. Enjoy dealing with them. We will deal with whatever is left of you. (Cersei Lannister)
bq. The dead will come North first. Enjoy dealing with them. We will deal with whatever is left of you. - Cersei Lannister
După ce a adunat bogăţii impresionante din afacerile cu negru de fum, Charles a reuşit să adune un număr proporţional de impresionant de inamici. Iar acum, toate cele $N$ armate ale acestora se află pe drumul către capitala regatului lui Charles, Copşa Mică. Armatele sunt dispuse în şir pe drum, a $i$-a armată de pe drum fiind compusă din $S{~i~}$ soldaţi.
Deoarece Charles însuşi e mai pasionat de Blackjack decât de război, el plănuieşte să îţi împuţineze duşmanii făcându-i să se lupte între ei: la un moment dat el poate unelti ca două armate dispuse *adiacent* pe drum să se lupte între ele. Evident, dintre cele două armate va câştiga cea mai numeroasă, dar va pierde atâţia soldaţi câţi avea armata opozantă. Armata mai puţin numeroasă dispare complet. Mai precis, dacă cele două armate au $A$, respectiv $B$ soldaţi, după bătălie va rămâne o singură armată egală cu diferenţa în modul dintre $A$ şi $B$, $|A-B|$. Dacă armatele au acelaşi număr de soldaţi, ambele dispar.
Deoarece Charles e mai pasionat de blackjack decât de război, el plănuieşte să îşi împuţineze duşmanii făcându-i să se lupte între ei: la un moment dat el poate unelti ca două armate dispuse *adiacent* pe drum să se lupte între ele. Evident, dintre cele două armate va câştiga cea mai numeroasă, dar aceasta va pierde atâţia soldaţi câţi avea armata opozantă. Armata mai puţin numeroasă dispare complet. Mai precis, dacă cele două armate au $X$, respectiv $Y$ soldaţi, după bătălie va rămâne o singură armată egală cu diferenţa în modul dintre $X$ şi $Y$, $|X-Y|$. Dacă armatele au acelaşi număr de soldaţi, ambele dispar. Charles poate unelti oricâte astfel de lupte.
Charles se întreabă, pentru fiecare interval $[i, j]$ din şirul de armate, care este numărul minim de soldaţi din armatele $i, i+1, ..., j$ care pot rămâne, dacă Charles poate unelti doar lupte între armatele aflate iniţial în intervalul $[i, j]$.
Charles se întreabă, pentru $Q$ intervale $[a, b]$ din şirul de armate, care este numărul minim de soldaţi din armatele $a, a+1, ..., b$ care pot rămâne, dacă Charles poate unelti doar lupte între armatele aflate iniţial în intervalul $[a, b]$.
h2. Date de intrare
Fişierul de intrare $armate.in$ va conţine pe prima linie numărul $N$ de armate. Pe următoarea linie se vor afla $N$ numere naturale, al $i$-ulea reprezentând numărul de soldaţi $S{~i~}$ din armata $i$.
Fişierul de intrare $armate.in$ va conţine pe prima linie numerele $N$ de armate, respectiv $Q$ de întrebări. Pe următoarea linie se vor afla $N$ numere naturale, al $i$-ulea reprezentând numărul de soldaţi $S{~i~}$ din armata $i$. Pe următoarele $Q$ linii se vor afla $Q$ perechi de numere $a$ şi $b$ reprezentând întrebările lui Charles.
h2. Date de ieşire
În fişierul de ieşire $armate.out$ veţi afişa $N*(N+1)/2$ linii, câte una pentru fiecare interval $[i, j]$, conţinând numărul minim de soldi din armatele $i, i+1, ..., j$ care pot rămâne, dacă Charles poate unelti doar lupte între armatele aflate iniţial în intervalul $[i, j]$. Intervalele sunt considerate în ordine lexicografică: crescător după capătul din stânga, iar în caz de egalitate crescător după capătul din dreapta.
În fişierul de ieşire $armate.out$ veţi afişa $Q$ linii, reprezentând, în ordine, răspunsul la întrerile lui Charles.
h2. Restricţii
* $1 ≤ N ≤ 500$
* $1 ≤ S{~i~} ≤ 500$
* $1 ≤ N ≤ 400$
* $1 ≤ Q ≤ 800$
* $1 ≤ S{~i~} ≤ 400$
* $1 ≤ a ≤ b ≤ N$, pentru fiecare din cele $Q$ întrebări.
* Un interval $[a, b]$ poate apărea în mai mult de o întrebare.
* Pentru teste în valoare de $30$ de puncte, $1 ≤ N ≤ 30$ şi $1 ≤ S{~i~} ≤ 30$.
* Pentru teste în valoare de $60$ de puncte, $1 ≤ N ≤ 100$ şi $1 ≤ S{~i~} ≤ 100$.
* Pentru teste în valoare de $80$ de puncte, $1 ≤ N ≤ 300$ şi $1 ≤ S{~i~} ≤ 300$.
h2. Exemplu
table(example). |_. armate.in |_. armate.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 4 3
16 2 8 10
3 4
1 3
1 4
| 2
6
0
|
h3. Explicaţie
...
Pentru prima întrebare, ne uităm la armatele din intervalul $[3, 4]$, şi anume $(8, 10)$. Uneltim lupta între ele şi obţinem şirul de armate $(2)$. Nu mai putem organiza altă luptă, aşa că răspunsul este $2$.
 
Pentru a doua întrebare, ne uităm la armatele din intervalul $[1, 3]$, şi anume $(16, 2, 8)$. Prima luptă este între armatele $1$ şi $2$, obţinând şirul $(14, 8)$. A doua luptă este între armatele rămase, obţinând şirul $(6)$ care dă şi răspunsul.
 
Pentru a treia întrebare, şirul evoluează astfel: $(16, 2, 8, 10) -> (16, 6, 10) -> (10, 10) -> ()$. Deoarece obţinem şirul vid, răspunsul este $0$.
== include(page="template/taskfooter" task_id="armate") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.