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. 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