Az S. 167. feladat (2023. január)

S. 167. Egy hegy tetejére \(\displaystyle N\) lépcsőből álló lépcsősor vezet fel. Egy szerzetes \(\displaystyle T\) egymást követő napon felment a hegyre. Első nap az \(\displaystyle l_{1}\) lépcsőfokról indult és minden lépésnél kihagyott \(\displaystyle d_{1}\) lépcsőfokot. Rálépett tehát az \(\displaystyle l_{1}+(d_{1}+1)\), \(\displaystyle l_{1}+ {2(d_{1}+1)}\), \(\displaystyle \ldots\ \) lépcsőfokokra egészen addig, míg fel nem ért a hegycsúcsra. Ha az utolsó lépés magasabbra ért volna, mint \(\displaystyle N\), akkor rálépett az \(\displaystyle N\)-edik fokra és ezzel feljutott a hegycsúcsra.

Az első napot követő napokon az \(\displaystyle l_{i}\) és \(\displaystyle d_{i}\) értékeket a következő szabály szerint változtatta: \(\displaystyle l_{i+1} = (l_{i}+1) \mod L\) és \(\displaystyle d_{i+1} = (d_{i}+1) \mod D\), ahol \(\displaystyle 1\le i\le T-1\). Sajnos a szerzetes már nem emlékszik rá, hogy így hány lépcsőfokra lépett rá felfelé menet. Készítsünk programot, ami meghatározza ezt a számot.

A bemenet első sorában hat egész szám szerepel: a lépcsők \(\displaystyle N\) száma, a napok \(\displaystyle T\) száma, az \(\displaystyle L\) és \(\displaystyle D\) modulusok, illetve az első napon az \(\displaystyle l_{1}\) lépcsőfok, amiről indulunk, és a lépésenként kihagyott lépcsőfokok \(\displaystyle d_{1}\) száma.

A kimenet első és egyetlen sorába írjuk ki, hogy összesen hány lépcsőfokra lépett rá a szerzetes felfelé menet.

Példa:

Magyarázat: az első napon az első fokról indul és minden másodikra lép rá (5 lépés). A második napon a nulladik fokról indul és minden harmadik lépcsőfokra lép rá (4 lépés). A harmadik napon az első fokról indul és minden negyedikre lép rá (3 lépés).

Korlátok: \(\displaystyle 1\le N,T \le 10^9\), \(\displaystyle 1\le L,D \le 400\), \(\displaystyle L,D\le N\), \(\displaystyle 0\le l_{1}< L\), \(\displaystyle 0\le d_1< D\). Időkorlát: 1 mp.

Értékelés: A pontok 40%-a kapható, ha a program helyes kimenetet ad a \(\displaystyle {T\le 10^5}\) bemenetekre.

Beküldendő egy s167.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ó. A dokumentáció tartalmazza a megoldás elméleti hátterét, az esetleg felhasznált forrásokat. Ne tartalmazzon kódrészleteket, azok magyarázata kódkommentek formájában a forrásprogramban szerepeljen.

(10 pont)

A beküldési határidő 2023. február 15-én LEJÁRT.

Statisztika:

2 dolgozat érkezett.
10 pontot kapott:	Szabó Imre Bence.
3 pontot kapott:	1 versenyző.

A KöMaL 2023. januári informatika feladatai