# PBinfo #1784 – Flori3 – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: deivid ## Enunț Cerința 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 începerea 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. Date de intrare Fișierul de intrare flori3.in conține pe prima linie două 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ţ.  Date de ieșire Fișierul de ieșire flori3.out va conține, pe rânduri separate, M numere naturale, reprezentând răspunsul la fiecare dintre cele M întrebări. Restricții și precizări 1 ≤ N ≤ 105 1 ≤ D[i] ≤ 109, Ɐ i = 1,..,N 1 ≤ M ≤ 105 1 ≤ K ≤ 1000 1 ≤ x ≤ y ≤ N Exemplu: flori3.in 4 4  4 2 1 10  2  1 3  1 4  flori3.out 1  3  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:  3 4 4 4 4  2 4 4 4 4 4 4  2 1 1 1 1  O alternativă: pentru a doua floare folosim mai puţine petale, rămânând in final două flori nefolosite de culoare 4. ## Cod sursă C++ ```cpp /* Idea: * * Each flower needs 1 center disc and K surrounding discs. * First observation: there's no point in using more than K * surrounding discs. They don't improve the number of flowers, * and may only prohibit future flowers from being created. * * We split the problem into 2 parts: * 1. Make groups of K same-color surrounding discs first * (as many as possible). We denote this quantity by S. * 2. Each previously created group needs one central disc. * We denote the number of remaining discs by C. * * Now we need to match the K-groups with one central disc each. * Three cases may arise: * * 1. S = C * In this case, there is a bijection between the two sets. * This is the perfect situation, as all discs are used. * Answer = S = C * * 2. S < C * In this case, each K-group can be assigned one central disc. * However, there are some leftover central discs. Since * we started the process by creating all possible K-groups * first, it is guaranteed that the leftover discs are not * sufficient for the creation of a new flower. * Answer = S. * * 3. S > C * In this case, we have created too many K-groups, and there * are not enough central discs to match all of them. * In order to repair the damage, we can do the following: * 3.1 Take an existing K-group. * 3.2 Destroy it. * Now there are S-1 K-groups, and C+K central discs, so we * can complete at most K previously unobtainable flowers. * * Repeat steps 3.1 and 3.2 for as long as they profit us. * The values of S and C will finally reach a balance. * * These process can also be shortened mathematically, so that * the computation reaches constant time. */ #include #define nmax 1000006 using namespace std; long long n, m, k, SP[nmax], CP[nmax], sol=0, x, y, S, C; int main() { ifstream f("flori3.in"); ofstream g("flori3.out"); f>>n>>k; for(int i=1; i<=n; i++) { f>>x; assert(1 <= x && x <= 1000000000LL); SP[i] = SP[i-1] + x / k; CP[i] = CP[i-1] + x % k; } f>>m; assert(1 <= n && n <= 100000); assert(1 <= m && m <= 100000); assert(1 <= k && k <= 1000); while(m--) { f>>x>>y; S = SP[y]; C = CP[y]; if(x-1 >= 0) { S -= SP[x-1]; C -= CP[x-1]; } if(S <= C) sol = S; else { x = (S - C) / (k+1); sol = min(S-x, C+k*x); x++; sol = max(sol, min(S-x, C+k*x)); } g<