 |
Az S. 144. feladat (2020. május) |
S. 144. Az asztalon \(\displaystyle N\) kockát találunk, az \(\displaystyle n\)-edik kocka élének hossza \(\displaystyle a_{n}\) egész szám, térfogata \(\displaystyle V_{n}\) (a kockákat 0-tól indexeljük). A kockákkal \(\displaystyle Q\) műveletet hajtunk végre egymás után. Az \(\displaystyle i\)-edik műveletben megváltoztatjuk az összes kocka élének hosszát az \(\displaystyle [l_{i},r_{i}]\) tartományban \(\displaystyle b_{i}\)-vel. Minden művelet után adjuk meg a kockák térfogatainak összegét modulo \(\displaystyle {10}^{9}\mathbf{+}7\).
Bemenet: az első sor tartalmazza az \(\displaystyle N\) és \(\displaystyle Q\) számot. A következő sor \(\displaystyle N\) pozitív számot tartalmaz: a kockák éleinek hosszát sorrendben, ezek legfeljebb \(\displaystyle {10}^{9}\) nagyságúak. A következő \(\displaystyle Q\) sor mindegyike tartalmaz egy \(\displaystyle l_{i}\), \(\displaystyle r_{i}\) és \(\displaystyle b_{i}\) egész számot (\(\displaystyle 0\le l_{i}\le r_{i}<N\), \(\displaystyle |b_{i}|\le {10}^{9}\)). A változtatások során a kockák éle mindig pozitív marad.
Kimenet: adjuk meg minden változtatás után a \(\displaystyle \bigg(\sum\limits_{n=0}^{N-1} V_{n}\bigg)\) modulo \(\displaystyle 10^{9}+7\) értéket.
Példa:
| Bemenet (a / jel sörtérést helyettesít) | Kiment |
| 5 2 1 1 1 1 2 0 1 1 / 4 4 -1 | 26 19 |
Korlátok: \(\displaystyle 1\le N, Q\le {10}^{5}\). Időkorlát: 0,4 mp.
Értékelés: a pontok 50%-a kapható, ha \(\displaystyle N, Q\le 100\).
Beküldendő egy s144.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.
(10 pont)
A beküldési határidő 2020. június 10-én LEJÁRT.
Statisztika:
6 dolgozat érkezett. 10 pontot kapott: Horcsin Bálint. 7 pontot kapott: 2 versenyző. 1 pontot kapott: 3 versenyző.
A KöMaL 2020. májusi informatika feladatai