spoj MAIN8_C - Shake Shake Shaky.

general
,
1

Shaky has N (1<=N<=50000) candy boxes each of them contains a non-zero number of candies (between 1 and 1000000000). Shakey want to distibute these candies among his K (1<=K<=1000000000) IIIT-Delhi students. He want to distibute them in a way such that:

  1. All students get equal number of candies.

  2. All the candies which a student get must be from a single box only.

As he want to make all of them happy so he want to give as many candies as possible. Help Shaky in finding out what is the maximum number of candies which a student can get.

Input
First line contains 1<=T<=20 the number of test cases. Then T test cases follow. First line of each test case contains N and K. Next line contains N integers, ith of which is the number of candies in ith box.

Output
For each test case print the required answer in a seperate line.

Example
Input:
2
3 2
3 1 4
4 1
3 2 3 9

Output:
3
9

Someone please explain how to use binary search here.

2

It’s a good example of modified binary search.

Here is the approach:

1.Sort the array in ascending order.

2.Run the binary search and Let say mid element is x.

3.Now make a check whether that mid element fulfills your demand according to a number of children.

4.If condition satisfies, then move b/w mid and high else move b/w low and mid.

Final value would be your answer,

Here is the code after some modification in binary search://author @ Ayush Aggarwal#include <bits/stdc++.h>using namespace std;typed - Pastebin.com

EDIT: Explanation of sample test case:

Given array: 3 1 4
After sorting: 1 3 4
N = 3 & K = 2;
1st iteration: mid = (0+3)/2 = 1;
a[mid] = 3 = val;
Now make a check whether val satisfies our condition or not?
Here is the function for the same:


 bool func(ll val,ll k,ll n)
{
	if(k==1)
		return true;
	ll sum=0;
	for(ll i=n-1;i>=0;i--)
	{
		sum +=(a[i]/val);
	}
	if(sum >= k)
		return true;
	else
		return false;
}

Here is the code explanation:
As we looping from N-1 to 0,our array becomes 4 3 1, so not to check whether one/more child can get candy out of box or not,sum = sum+a[i]/val;so now

4 -> 4/3 = 1
3 -> 3/3 = 1
1 -> 1/3 = 0
sum = 2 = k,return true;

Happy coding!

3

can anyone explain why I’m getting WA!

4

Change line 24 high=mid
bcoz for each iteration we are checking [0,high) as first:high=arr[n-1]+1
be careful high is excluded

5

3.Now make a check whether that mid element fulfills your demand according to a number of children.

Please explain this.
3 2
3 1 4
lets say n=4, k(no of child)=2.

6

man the test case. n=3,k=2. values of n=3,1,4. explain this

7

for(ll i=n-1;i>=0;i–)
{
sum +=(a[i]/val);
}

explain this too

8

oh, my bad didn’t notice that.

9

ayush please explain me the condition. i cannot fully understand this question

10

try run your sample test case, you will understand that.Sorry can’t give more time to this problem, I have other stuff to do.

11

sum +=(a[i]/val);. does this mean number of students who got chocolates?

12

Yupppppppppp

13

Debug this please. shows WA.

    lo=0;
    hi=1000000000;
    while(lo<=hi)
    {

        mid=(lo+hi)/2;
        if(mid==0)
        {
            if(k>n) ans=0;
            else ans=1;
            break;
        }
        stud=0;
        for(i=0;i<n;i++)
        {
        stud+=a[i]/mid;
        }
        if(stud>=k)
        {
            ans=mid;
            lo=mid+1;
        }
        else hi=mid-1;
    }
    cout<<ans<<endl;
}
return 0;

}

1 Like