Strange Game

Rajnish

 Problem:-

Alice and Bob are very good friends. They keep on playing some strange games. Today Alice came up with a new game, in which each player gets 

N

 cards at the start. Each card has it’s value printed on it.
The game proceeds as each player chooses a random card and shows it’s value. The player having card with higher value wins. As Alice came up with this game, he wants to ensure his win. So he starts to increase value of some cards using an algorithm. To increase the value of a card by 

1

, the running time of algorithm is 

K

 seconds.
Find the minimum running time of algorithm, ensuring the win of Alice.

Input:
First line of input contains an integer 

T

 denoting the number of TestCases.
First line of Each testcase contains two Integers 

N

 and 

K

.
Next two lines of each TestCase contains 

N

 integers, each denoting value of cards of Alice and Bob respectively.
    
Output:
Print a single line for each TestCase, running time of algorithm to ensure the win for Alice.   

Constraints:
    

1≤T≤100


    

1≤N≤105


    

1≤K≤20


    

0≤Valueofeachcard≤106

 

SAMPLE INPUT
 
3
5 3
8 9 10 23 4
7 9 2 3 13
6 8
8 99 23 1 3 0
9 32 22 45 3 2
3 2
1 1 0
5 8 9
SAMPLE OUTPUT
 
75
1560
56
Explanation

There are 3 TestCases.

In 1st TestCase there are 5 cards and the time required to increase the value of a card by one is 3.

Initial values on Alice’s cards are 

8,9,10,23,4

.

If he converts the the above array into 

14,14,14,23,14.

 Then it’s guranteed that he will win with minimum running time of algorithm.

For this conversion the running time of algorithm for:

    1st element :- 

6∗3=18sec

    2nd element :- 

5∗3=15sec

    3rd element :- 

4∗3=12sec

    4th element :- 

0∗3=0sec

    5th element :- 

10∗3=30sec

Hence the total running time of algorithm for 1st TestCase is 

18+15+12+0+30=75sec

Time Limit:1.0 sec(s) for each input file.
Memory Limit:256 MB
Source Limit:1024 KB

BEST SUBMISSION

SIMILAR PROBLEMS

CONTRIBUTORS

Code:-

#include<stdio.h>
int main()
{
    int t,k;
    long int n;
    scanf(“%d”,&t);
    while(t–)
    {
        scanf(“%ld%d”,&n,&k);
        long long int a[n],bob,max=0,i,sum=0;
        for(i=0;i<n;i++)
         scanf(“%lld”,&a[i]);
        for(i=0;i<n;i++)
        {
scanf(“%lld”,&bob);
            if(max<bob)
             max=bob;
        }
        max++;
        for(i=0;i<n;i++)
        {
            if(a[i]<max)
sum=sum+(max-a[i]);
        }
        printf(“%lldn”,sum*k);
    }
    return 0;
}




Leave a Reply

Your email address will not be published.