Hard Cash Codechef Solution: Chef wants to take Chefina on a date. However, he has to complete one more task before leaving. Since he does not want to be late, he is asking you for help.
There are NN bags with coins in a row (numbered 11 through NN); for each valid ii, the ii-th bag contains AiAi coins. Chef should make the number of coins in each bag divisible by a given integer KK in the following way:
- choose an integer cc between 00 and NN (inclusive)
- take some coins from the first cc bags ― formally, for each ii (1≤i≤c1≤i≤c), he may choose any number of coins between 00 and AiAi inclusive and take them out of the ii-th bag
- move some of these coins to some of the last N−cN−c bags ― formally, for each ii (c+1≤i≤Nc+1≤i≤N), he may place a non-negative number of coins in the ii-th bag
Of course, the number of coins placed in the last N−cN−c bags must not exceed the number of coins taken out from the first cc bags, but there may be some coins left over. Let’s denote the number of these coins by RR. You should find the smallest possible value of RR.
Input
- The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- The first line of each test case contains two integers NN and KK.
- The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
Output
For each test case, print a single line containing one integer ― the smallest value of RR.
Constraints
- 1≤T≤1031≤T≤103
- 1≤N≤1051≤N≤105
- 0≤Ai≤1090≤Ai≤109 for each valid ii
- 1≤K≤1091≤K≤109
- the sum of NN over all test cases does not exceed 105105
Sample Input 1
2 5 7 1 14 4 41 1 3 9 1 10 19
Sample Output 1
5 3
Explanation
Example case 1: One of the possible solutions is to choose c=4c=4, remove 11, 00, 44 and 1313 coins from bags 11, 22, 33 and 44 respectively, and add 1313 coins to bag 55.
Example case 2: The optimal solution is to choose c=3c=3 and remove one coin from each bag.
Hard Cash CodeChef Solution in JAVA
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 0; tc < T; ++tc) {
int N = sc.nextInt();
int K = sc.nextInt();
int[] A = new int[N];
for (int i = 0; i < A.length; ++i) {
A[i] = sc.nextInt();
}
System.out.println(solve(A, K));
}
sc.close();
}
static int solve(int[] A, int K) {
return (int) (Arrays.stream(A).asLongStream().sum() % K);
}
}Hard Cash CodeChef Solution in CPP
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t,n;
cin>>t;
while(t--){
long long k;
cin>>n>>k;
long long a[n];
for (int i=0; i<n; i++){
cin>>a[i];
}
long long ans = 0;
for (int i=0; i<n; i++){
ans += a[i];
}
ans = ans%k;
cout<<ans<<endl;
}
return 0;
}
Hard Cash CodeChef Solution in Python
t = int(input())
for _ in range(t):
n,k = map(int,input().split())
l = list(map(int,input().split()))
s = sum(l)
ans = s%k
print(ans)
Disclaimer: The above Problem is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.
