Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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:

HorcsinBalint.pdf


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