Submit | All submissions | Best solutions | Back to list |
SNYC1 - Partial Sums |
Given a sequence of positive integers a1, a2, ..., aN, and 1 ≤ i ≤ j ≤ N, the partial sum from
i to j is ai + ai+1 + ... + aj.
In this problem, you will be given such a sequence and two integers P and K. Your task is to find the smallest partial sum modulo P that is at least K.
For example, consider the following sequence of integers:
12 13 15 11 16 26 11
Here N = 7. Suppose K = 2 and P = 17. Then, the answer is 2 because 11 + 16 + 26 = 53 and 53 mod 17 is 2. On the other hand, if K = 0 the answer is 0 since 15 + 11 + 16 + 26 = 68 and 68 mod 17 is 0.
You may assume 1 ≤ N ≤ 100000.
Input
The first line of the input contains the number of test cases, T.
Each test case begins with a line containing three integers, N, K and P. This is followed by the values of a1, a2, ..., aN, one per line.
Output
Output one line per test case, containing the smallest partial sum modulo P that is at least K, as described above.
Example
Input: 1 7 2 17 12 13 15 11 16 26 11 Output: 2Warning: large Input/Output data, be careful with certain languages
Scoring
The shortest code (the less number of bytes) the better. The number of points displayed in the ranking is scaled so that it is equal to 10 for the contestant whose solution is the shortest, and proportionally less for all solutions with longer codes.Added by: | kuszi |
Date: | 2009-12-31 |
Time limit: | 1.440s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP CPP14 C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCALA SCM guile SCM qobi ST TCL TEXT WHITESPACE |
Resource: | Indian Computing Olympiad, Online Programming Contest, July 06 (problem posted by Stephen Merriman as PARTSUM) |