All submissions for this problem are available.
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.
The first line contains three integers N, K and
P. This is followed by N lines each containing a
You may assume 1 ≤ N ≤ 100000.
A single integer indicating the minimum possible segment sum modulo
P that is at least K.
7 2 17 12 13 15 11 16 26 11
|Time Limit:||0.460123 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, COB, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, kotlin, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, rust, SCALA, SCM chicken, SCM guile, SCM qobi, ST, swift, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.