Diferente pentru problema/flori5 intre reviziile #7 si #15

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="flori5") ==
După o amorţeală care durase mai bine de 3 luni, Mama Natură îşi dădu seama că primăvara stătea să vină şi florile cu care trebuia curând să umple câmpiile nu erau încă pregătite. Înainte de inceperea iernii, a lucrat să combine nuanţe din care să creeze flori pline de culoare, iar acum are camera plină de discuri de diferite culori, care aşteaptă să fie asamblate in flori viu colorate, fie pe post de mijloc, fie ca şi petale.
După o amorţeală care durase mai bine de 3 luni, Mama Natură îşi dădu seama că primăvara stătea să vină şi florile cu care trebuia curând să umple câmpiile nu erau încă pregătite. Înainte de inceperea iernii, a lucrat să combine nuanţe din care să creeze flori pline de culoare, iar acum are camera plină de discuri de diferite culori, care aşteaptă să fie asamblate în flori viu colorate, fie pe post de mijloc, fie ca şi petale.
Pentru a forma o floare, Mama Natură alege un mijloc de orice culoare şi cel puţin $k$ petale. Totodată, ea nu îşi doreşte să strice ordinea firească a lucrurilor şi de aceea nu va folosi niciodată două culori diferite de petale pentru aceeaşi floare. Ea admite, în schimb, flori cu petalele şi mijlocul de aceeaşi culoare.
 
Deoarece timpul e scurt şi Mama Natură are lucruri mai importante de făcut decât să stea să asambleze flori, ea îşi cheamă în ajutor toate prietenele şi doreşte să îi dea fiecăreia ceva de lucru. Pentru aceasta, ea are la dispoziţie un şir $D$ de n numere, unde numărul de pe poziţia $i$ din şir reprezintă câte discuri de culoarea $i$ a pregătit. Apoi, Mama Natură îşi pune $m$ întrebări de forma $x$ $y$, prin care doreşte să afle care este numărul maxim de flori care se pot forma folosind doar discuri de culori din intervalul [$x$, $y$] din şirul $D$.
Pentru a forma o floare, Mama Natură alege un mijloc de orice culoare şi cel puţin $K$ petale. Totodată, ea nu îşi doreşte să strice ordinea firească a lucrurilor şi de aceea nu va folosi niciodată două culori diferite de petale pentru aceeaşi floare. Ea admite, în schimb, flori cu petalele şi mijlocul de aceeaşi culoare.
Deoarece timpul e scurt şi Mama Natură are lucruri mai importante de făcut decât să stea să asambleze flori, ea îşi cheamă în ajutor toate prietenele şi doreşte să îi dea fiecăreia ceva de lucru. Pentru aceasta, ea are la dispoziţie un şir $D$ de $N$ numere, unde numărul de pe poziţia $i$ din şir reprezintă câte discuri de culoarea $i$ a pregătit. Apoi, Mama Natură îşi pune $M$ întrebări de forma $x y$, prin care doreşte să afle care este numărul maxim de flori care se pot forma folosind doar discuri de culori din intervalul $[x, y]$ din şirul $D$.
h2. Date de intrare
Pe prima linie a fişierului $flori.in$ se vor afla $2$ numere naturale, $n$ şi $k$, separate prin spaţiu, cu semnificaţia din enunţ. Pe urmatoarea linie se vor afla $n$ numere naturale (elementele şirului $D$). Următoarea linie a fişierului va conţine numărul $m$ şi va fi urmată de $m$ linii conţinând perechi de numere întregi $x$ şi $y$, cu semnificaţia din enunţ.
Pe prima linie a fişierului $flori5.in$ se vor afla $2$ numere naturale, $N$ şi $K$, separate prin spaţiu, cu semnificaţia din enunţ. Pe următoarea linie se vor afla $N$ numere naturale (elementele şirului $D$). Următoarea linie a fişierului va conţine numărul $M$ şi va fi urmată de $M$ linii conţinând perechi de numere întregi $x$ şi $y$, cu semnificaţia din enunţ.
h2. Date de ieşire
În fişierul $flori.out$ se vor afişa, pe rânduri separate, $m$ numere naturale, reprezentând răspunsul la fiecare dintre cele $m$ întrebări.
În fişierul $flori5.out$ se vor afişa, pe rânduri separate, $M$ numere naturale, reprezentând răspunsul la fiecare dintre cele $M$ întrebări.
h2. Restricţii
* $1 ≤ n ≤ 10^6^$
* $1 ≤ D[i] ≤ 10^9^, Ɐ i = 1,n$
* $1 ≤ m ≤ 10^5^$
* $1 ≤ x, y ≤ n$
* $1 ≤ N ≤ 10^5^$
* $1 ≤ D[i] ≤ 10^9^, Ɐ i = 1,N$
* $1 ≤ M ≤ 10^5^$
* $1 ≤ K ≤ 1000$
* $1 ≤ x ≤ y ≤ N$
h2. Exemplu
table(example). |_. flori.in |_. flori.out |
table(example). |_. flori5.in |_. flori5.out |
| 4 4
4 2 1 10
2
h3. Explicaţie
Pentru prima întrebare, Mama Natură poate alege o singură floare, cu petale de culoarea $1$ şi mijloc de culoarea $2$ sau $3$.
Pentru a doua întrebare, putem forma $3$ flori:
Pentru a doua întrebare, putem forma $3$ flori:
 
* $3 4 4 4 4$
* $2 4 4 4 4 4 4$
* $2 1 1 1 1$
Alternativa: pentru a doua floare folosim mai puţine petale, rămânând in final doua flori nefolosite de culoare $4$.
 
O alternativă: pentru a doua floare folosim mai puţine petale, rămânând in final două flori nefolosite de culoare $4$.
== include(page="template/taskfooter" task_id="flori5") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.