Devu and Grapes
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Grapes of Coderpur are very famous. Devu went to the market and saw that there were N people selling grapes. He didn’t like it because things were not very structured. So, he gave a task to Dhinwa to make things better. If Dhinwa successfully completes the task, Devu will be happy.
Devu wants to change the number of grapes in a bucket of zero or more sellers in such a way that the GCD of all the number of grapes is divisible by K. Dhinwa can add or remove any number of grapes from each of the buckets. Adding or removing a grape will be counted as an operation. Also after the operation, none of the seller’s bucket should be empty.
Help Dhinwa in finding the minimum number of operations needed to make Devu happy.
- First line of input contains an integer T denoting the number of test cases.
- For each test case, first line will contain an integer N denoting the number of buckets and integer K.
- Next line contains N space separated integers denoting the number of grapes in each of the bucket.
For each test case, print a single integer representing the answer of that test case.
Subtask #1: 10 points
- 1 ≤ T ≤ 10, 1 ≤ N ,K ≤ 10, 1 ≤ number of grapes in a bucket ≤ 10
Subtask #2: 10 points
- 1 ≤ T ≤ 10, 1 ≤ N,K ≤ 100, 1 ≤ number of grapes in a bucket ≤ 100
Subtask #3: 80 points
- 1 ≤ T ≤ 10, 1 ≤ N ≤ 105, 1 ≤ K ≤ 109, 1 number of grapes in a bucket ≤ 109
Input: 2 2 2 3 5 3 7 10 16 18 Output: 2 8
For the first test case, add or remove 1 grape in each of the bucket.
For the second test case, remove three grapes in the first bucket, remove two grapes from the second bucket and add three grapes in the third bucket.
|Tags||amitpandeykgp, cakewalk, gcd, ltime24|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.