Skip to content

UKSPC Practice Problems » The Meteoronome

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 medicine man to predict the weather. Tiribakians believed that the Meteoronome was set up by the gods at the Beginning of Time. Tiribakians pressed the yellow button every day; as a result, the Meteoronome produced a number representing the expected rainfall in millimeters for the next day. More precisely, after the button is pressed k times, (counted since the Beginning of Time) Meteoronome gives the expected rainfall for the kth day since the Beginning of Time.

Unfortunately, the Meteoronome has not been used for several thousand 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:

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 millimeters of rainfall during her entire stay on Tiribaki.

Doctor Jones wants to help his friend by computing the longest period during 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] ≤ 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).

Input Specification

The input file consists of several blocks of data. The first line of the input file contains the number of blocks. Each block contains 4 integers separated by whitespace:

  1. s[0]
  2. t[0] - the initial values for the Meteoronome
  3. N - the length of the sequence
  4. M - the maximum sum of a subsequence

Output Specification

The output file contains one line for each block of input data. In this line there is a single integer K as specified above.

Sample Input

1
123456 123456 10 10000

Sample Output

2

Note: the sequence produced by the Meteoronome for this input file is 4664, 1248, 267, 4900, 837, 4048, 990, 6935, 1155, 490. No subsequence of length 2 has sum greater than 10000, and there are subsequences of length 3 with a greater sum.