In this problem, you will be given such a sequence and two integers

*P*and*K*. Your task is to find the elements which created 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

You may assume 1 ≤

The first line of the input contains the number of test cases,

Each test case begins with a line containing three integers,

12 13 15 11 16 26 11

Here

*N*= 7. Suppose*K*= 0 the answer is 0 since 12 + 13 + 15 + 11 = 5 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*a*_{1},*a*_{2}, …,*a*, one per line._{N}**Output**

Output one line per test case, containing the elements which created 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:**

11 16 26

solution in c

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include "stdio.h" #include "conio.h" int main() { int i,j,k,br,temp,t,l,n,p,min=9999,test[100],sum=,a[1000],res[100][100]; i=scanf("%d",&t); temp=; while(temp<t) { i=scanf("%d %d %d",&n,&k,&p); br=n; for(i=;i<n;j=scanf("%d",&a[i++])){} for(j=1;j<=n;j++) { for(l=;l<n-j+1;l++) {sum=; for(i=;i<j;i++) { sum+=a[l+i]; test[i]=a[l+i]; } if(sum % p==k && sum<min) { min=sum;br=j; for(i=;i<j;res[temp][i]=test[i++]){} } } if(br!=n) goto A; } A: temp++; } for(i=-1;++i<t;printf("\n")) for(j=;res[i][j]!='\0';printf("%d ",res[i][j++])){} return 1; } |