SP2127 RAIN3 - Rain

Doctor Jones is a famous archeologist. He did some research on the Tiribaki Islands recently. His most famous discovery was the Meteoronome - a machine with a yellow button used by the Tiribakian highest priest to predict the weather. The Meteoronome had been set up by the gods at the Beginning of Time. Tiribakians pressed the button every day. As a result, the Meteoronome produced a number - the expected rainfall in millimetres for the next day. More precisely, after _i_ button hits (counted since the Beginning of Time) Meteoronome gives the expected rainfall for the day _i_ since the Beginning of Time. Unfortunately, the Meteoronome has not been used for several thousands of years and nobody knows how many steps should be performed to reach the current date. Researchers have spent a lot of effort to find out how the Meteoronome works. A mathematical model has been proposed: The Meteoronome is initialized by a pair of integers, s\[0\] and t\[0\]. For the _i_-th step, the Meteoronome computes the values ``` s[i] = (78901 + 31*s[i-1]) mod 699037 t[i] = (23456 + 64*t[i-1]) mod 2097151 ``` The output of the i-th step is the number ``` a[i]=(s[i] mod 100 + 1) * (t[i] mod 100 + 1) ``` Doctor Jones's friend, Ms. Linda Watson, is now planning a holiday on Tiribaki Islands. She would like to stay there as long as possible but she hates the rain. She can stand no more than M millimetres of rainfall during her entire stay on Tiribaki. Doctor Jones wants to help his friend and to compute the longest period which she can safely stay on Tiribaki. He simulated _N_ steps of the Meteoronome. This way, he obtained a sequence of numbers a\[1\],a\[2\],...,a\[N\] which represent predictions for _N_ subsequent days. Now he wants to find the largest _K_ such that for each period of at most _K_ subsequent days from day _i_ to day _j_ the sum of the predictions a\[i\]+a\[i+1\]+...+a\[j\] is less than or equal to _M_. Linda can be sure that if she stays on Tiribaki for at most _K_ days, she can endure the rain (provided that _N_ is large enough).

N/A

N/A