 |
Az S. 146. feladat (2020. október) |
S. 146. Adott egy \(\displaystyle N\) elemű \(\displaystyle T\) tömb 1-től indexelve, amely nemnegatív egész számokat tartalmaz. Kétféle műveletet végzünk a \(\displaystyle T\) tömb elemeivel. Az egyik műveletben hozzáadunk a tömb néhány egymást követő eleméhez egy \(\displaystyle p\) értéket, vagyis adott \(\displaystyle a\) és \(\displaystyle b\) mellett minden \(\displaystyle i\in [a,b]\) indexű \(\displaystyle T[i]\) elem ezután \(\displaystyle T[i]+p\) lesz. Definiáljuk adott \(\displaystyle c\) és \(\displaystyle d\) esetén (ahol \(\displaystyle d-c+1\) páros) a következő szorzatösszeget: \(\displaystyle T[c]\cdot T[c+1] + T[c+2]\cdot T[c+3] + \ldots + T[d-1]\cdot T[d]\), amely a \(\displaystyle [c,d]\) intervallum értéke a \(\displaystyle T\) tömbön. A második műveletben adjuk meg a \(\displaystyle c\) és \(\displaystyle d\) számok által meghatározott intervallum értékét. Mivel egy intervallum értéke nagyon nagy is lehet, ezért a lekérdezés eredményének \(\displaystyle {10}^{9}+7\)-tel vett osztási maradékát kell megadni.
Bemenet: az első sor tartalmazza az \(\displaystyle N\) és \(\displaystyle Q\) számokat. A következő sor \(\displaystyle N\) számot tartalmaz, \(\displaystyle T\) elemeit. A következő \(\displaystyle Q\) sor mindegyike vagy \(\displaystyle 1\ a\ b\ p\) alakú, ami azt jelenti, hogy az \(\displaystyle [a;b]\) intervallumon minden tömbértéket megváltoztatunk \(\displaystyle p\)-vel; vagy \(\displaystyle 2\ c\ d\) alakú, ami azt jelenti, hogy lekérdezzük a \(\displaystyle [c,d]\) intervallum értékét.
Kimenet: minden 2-es típusú kérdésre adjuk meg az intervallum értékét modulo \(\displaystyle {10}^{9}+7\).
Példa:
Korlátok: \(\displaystyle 1\le N,Q\le {10}^{5}\), \(\displaystyle 0\le T[i],p\le {10}^{9}\), \(\displaystyle 1\le a,b,c,d\le N\), \(\displaystyle a\le b\), \(\displaystyle c<d\). Időkorlát: 0,3 mp.
Értékelés: a pontok 50%-a kapható, ha \(\displaystyle N\le 100\).
Beküldendő egy s146.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. november 16-án LEJÁRT.
Észrevehető, hogy két féle lekérdezés lehet az intervallum kezdőpontjának paritása alapján.
Mindkét eset külön kezelhető egy-egy szegmensfával.
Részletes leírás Horcsin Bálint megoldásában:
Statisztika:
12 dolgozat érkezett. 10 pontot kapott: Horcsin Bálint, Varga 256 Péter. 6 pontot kapott: 1 versenyző. 2 pontot kapott: 7 versenyző. 1 pontot kapott: 2 versenyző.
A KöMaL 2020. októberi informatika feladatai