Burning Midnight Oil

. Burning Midnight Oil

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

One day a highly important task was commissioned to Vasya — writing a program in a night. The program consists of n lines of code. Vasya is already exhausted, so he works like that: first he writes v lines of code, drinks a cup of tea, then he writes as much as  lines, drinks another cup of tea, then he writes  lines and so on: , , , ...

The expression  is regarded as the integral part from dividing number a by number b.

The moment the current value  equals 0, Vasya immediately falls asleep and he wakes up only in the morning, when the program should already be finished.

Vasya is wondering, what minimum allowable value v can take to let him write not less than n lines of code before he falls asleep.

Input

The input consists of two integers n and k, separated by spaces — the size of the program in lines and the productivity reduction coefficient, 1 ≤ n ≤ 109, 2 ≤ k ≤ 10.

Output

Print the only integer — the minimum value of v that lets Vasya write the program in one night.

Sample test(s)

input

7 2

output

4

input

59 9

output

54

Note

In the first sample the answer is v = 4. Vasya writes the code in the following portions: first 4 lines, then 2, then 1, and then Vasya falls asleep. Thus, he manages to write 4 + 2 + 1 = 7 lines in a night and complete the task.

In the second sample the answer is v = 54. Vasya writes the code in the following portions: 54, 6. The total sum is 54 + 6 = 60, that's even more than n = 59.

#include<iostream>

#include<bits/stdc++.h>

typedef long long int lli;

using namespace std;

lli  n,k;

lli find(lli start,lli end)

 {

lli ans=INT_MAX;

   //cout<<"start "<<start<<"end "<<end<<endl;

   

     while(start<end)

      {

      lli mid=(start+end)/2;

      //cout<<"mid"<<mid<<endl;

       //cout<<"start "<<start<<"end "<<end<<endl;

      int i=0;

      lli pre=0;

       lli temp=mid;

         while(temp/pow(k,i)>0)

          {

          pre+=temp/pow(k,i);

          

          i++;

          }

      //   cout<<"pre "<<pre<<endl;

          if(pre <n)

           {

           

            start=mid+1;

           }

           else

            {

            if(mid<ans) ans=mid;

             end=mid;

            }

      }

      return ans;

 }

int main()

 {

 

  cin>>n>>k;

  if(n==1  || n<=k) cout<<"1"<<endl;

  else

  {

  lli ans=find(1,n);

    cout<<ans<<endl;

  }

   

    return 0;

 }

PIE - Pie

PIE - Pie

no tags 

My birthday is coming up and traditionally I'm serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and each of them gets a piece of pie. This should be one piece of one pie, not several small pieces since that looks messy. This piece can be one whole pie though.

My friends are very annoying and if one of them gets a bigger piece than the others, they start complaining. Therefore all of them should get equally sized (but not necessarily equally shaped) pieces, even if this leads to some pie getting spoiled (which is better than spoiling the party). Of course, I want a piece of pie for myself too, and that piece should also be of the same size.

What is the largest possible piece size all of us can get? All the pies are cylindrical in shape and they all have the same height 1, but the radii of the pies can be different.

Input

One line with a positive integer: the number of test cases. Then for each test case:

• One line with two integers N and F with 1 ≤ N, F ≤ 10000: the number of pies and the number of friends.
• One line with N integers ri with 1 ≤ ri ≤ 10000: the radii of the pies.

Output

For each test case, output one line with the largest possible volume V such that me and my friends can all get a pie piece of size V. The answer should be given as a floating point number with an absolute error of at most 10-3.

Example

Input:
3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2

Output:
25.1327
3.1416
50.2655

nmn
#include<iostream>
using namespace std;
#include<algorithm>
#include<stdio.h>
#define precision 0.0001
#define pi 3.14159265358979323846264338327950

int main()
 {
  int t;
  cin>>t;
  while(t--)
   {
    //cout<<"t "<<t<<endl;
    int pi_count,frnd;
    cin>>pi_count>>frnd;
    frnd+=1;
    int arr[pi_count+100];
    for(int i=0;i<pi_count;i++)
     {
      cin>>arr[i];
     }
     sort(arr,arr+pi_count);
     //cout<<"sort \n";
   
     double lo=(pi*arr[pi_count-1]*arr[pi_count-1])/frnd;
     double temp =lo;
     double kk=lo;
     //cout<<"temp ini "<<temp<<endl;
     double hi=(pi*arr[pi_count-1]*arr[pi_count-1]);
     //cout<<"hi "<<hi<<endl;
     //cout<<"game start \n";
     while(hi-lo>precision )
      {
      int count =0;
      double mid=(lo+hi)/2;
      //cout<<"mid "<<mid<<endl;
       for(int i=0;i<pi_count;i++)
        {
        count+=(pi*arr[i]*arr[i])/mid;
        }
       
        if(count<frnd)
         {
          hi=mid;
         }
         else
         {
           if(mid-temp>0.0001)
{
temp=mid;

}
lo=mid+0.0001;
         }
      }
   
   // cout<<temp<<endl;
    printf("%.4f\n",temp);
   }
   return 0;
 }

MAIN8_C - Shake Shake Shaky

MAIN8_C - Shake Shake Shaky

no tags 

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:

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

mmm

#include<iostream>
#include<algorithm>
//#include<bits/stdc++.h>
long long int arr[1000000];
using namespace std;
 int main()
 {
  long long int t;
  cin>>t;
  while(t--)
  {
  long long int box,stud;
  cin>>box>>stud;
 
    for(long long int i=0;i<box;i++)
     cin>>arr[i];
   sort(arr,arr+box);
   long long int lo=arr[box-1]/stud;
   long long int ans=lo;
 
   long long int hi = arr[box-1];
   if(lo==0 && hi==1)
    {
    cout<<"1"<<endl;
    continue;
   
    }
  // cout<<"initial lo "<<lo<<"  hi  "<<hi<<endl;
   while(lo<=hi)
    {
     long long int mid=(lo+hi)/2;
   //  cout<<"mid "<<mid<<endl;
     long long int stud_covered=0;
      for(long long int i=0;i<box;i++)
       {
        if(mid!=0)
        stud_covered+=arr[i]/mid;
       }
       if(stud_covered>=stud)
        {
        lo=mid+1;
        if(mid>ans) ans=mid;
        }
        else
        {
        hi=mid-1;
        }
    }
cout<<ans<<endl;  
  }
 
  return 0;
 }

EKO - Eko

EKO - Eko

no tags 

Lumberjack Mirko needs to chop down M metres of wood. It is an easy job for him since he has a nifty 

new woodcutting machine that can take down forests like wildfire. However, Mirko is only allowed to 

cut a single row of trees.

Mirko‟s machine works as follows: Mirko sets a height parameter H (in metres), and the machine raises 

a giant sawblade to that height and cuts off all tree parts higher than H (of course, trees not higher than 

H meters remain intact). Mirko then takes the parts that were cut off. For example, if the tree row 

contains trees with heights of 20, 15, 10, and 17 metres, and Mirko raises his sawblade to 15 metres, the 

remaining tree heights after cutting will be 15, 15, 10, and 15 metres, respectively, while Mirko will take 

5 metres off the first tree and 2 metres off the fourth tree (7 metres of wood in total).

Mirko is ecologically minded, so he doesn‟t want to cut off more wood than necessary. That‟s why he 

wants to set his sawblade as high as possible. Help Mirko find the maximum integer height of the 

sawblade that still allows him to cut off at least M metres of wood.

Lumberjack Mirko needs to chop down M metres of wood. It is an easy job for him since he has a nifty 

new woodcutting machine that can take down forests like wildfire. However, Mirko is only allowed to 

cut a single row of trees.

Mirko‟s machine works as follows: Mirko sets a height parameter H (in metres), and the machine raises 

a giant sawblade to that height and cuts off all tree parts higher than H (of course, trees not higher than 

H meters remain intact). Mirko then takes the parts that were cut off. For example, if the tree row 

contains trees with heights of 20, 15, 10, and 17 metres, and Mirko raises his sawblade to 15 metres, the 

remaining tree heights after cutting will be 15, 15, 10, and 15 metres, respectively, while Mirko will take 

5 metres off the first tree and 2 metres off the fourth tree (7 metres of wood in total).

Mirko is ecologically minded, so he doesn‟t want to cut off more wood than necessary. That‟s why he 

wants to set his sawblade as high as possible. Help Mirko find the maximum integer height of the 

sawblade that still allows him to cut off at least M metres of wood.

Input

The first line of input contains two space-separated positive integers, N (the number of trees, 1 ≤ N ≤ 

1 000 000) and M (Mirko‟s required wood amount, 1 ≤ M ≤ 2 000 000 000).

The second line of input contains N space-separated positive integers less than 1 000 000 000, the 

heights of each tree (in metres). The sum of all heights will exceed M, thus Mirko will always be able to 

obtain the required amount of wood.

Output

The first and only line of output must contain the required height setting.

Example

Input:

4 7

20 15 10 17

Output:

15

Input:

5 20

4 42 40 26 46

Output:

36

xmasma

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
long long int read_int(){
char r;
bool start=false,neg=false;
long long int ret=0;
while(true){
r=getchar();
if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
continue;
}
if((r-'0'<0 || r-'0'>9) && r!='-' && start){
break;
}
if(start)ret*=10;
start=true;
if(r=='-')neg=true;
else ret+=r-'0';
}
if(!neg)
return ret;
else
return -ret;
}
 int  main()
 {
 long long int  tr,m;
  // cin>>tr>>m;
  tr=read_int();
  m=read_int();
   long long int  arr[tr+10],max_gain=0;
    for(long long int  i=0;i<tr;i++)
     {
      //cin>>arr[i];
      arr[i]=read_int();
     }
     sort(arr,arr+tr);
     long long int  lo=arr[0];
     long long int  mid;
     long long int  hi=arr[tr-1];
     while(lo<hi)
      {
      mid=(lo+hi)/2;
      long long int  sum=0;
      for(long long int  i=0;i<tr;i++)
      {
      if(arr[i]>mid)
      sum+=(arr[i]-mid);
      }
     
      if(sum==m)
      {
      cout<<mid<<endl;
      return 0;
      }
     
        else if(sum<m)
        {
         hi=mid;
        }
        else
        {
        if(max_gain<mid) max_gain=mid;
        lo=mid+1;
       
        }
     
     
      }
      cout<<max_gain<<endl;
  return 0;
 }

Fair workload

FairWorkload  
Used as: Division Two - Level Three:

Value	1000
Submission Rate	19 / 299 (6.35%)
Success Rate	11 / 19 (57.89%)
High Score	. for 914.74 points (8 mins 50 secs)
Average Score	721.75 (for 11 correct submissions)

Used as: Division One - Level Two:

Value	500
Submission Rate	147 / 184 (79.89%)
Success Rate	132 / 147 (89.80%)
High Score	antimatter for 487.35 points (4 mins 36 secs)
Average Score	348.60 (for 132 correct submissions)

This is a very nice question, which can be solved in a couple ways. But first and foremost lets try to understand what the problem is asking us to do.
We are given a number of filing cabinets where each cabinet contains some number of folders. We are also given the number of available workers. What we would like to do is to partition the cabinets amongst the N workers in a such a way that
    (1) each worker works with adjacent cabinets
    (2) number of folders that each worker has to work on (cabinets can not be shared) is spread as evenly as possible.
We are to return the largest partition in our most evenly spread arrangement.

As an example: if we are given 9 cabinets:

        10 20 30 40 50 60 70 80 90

and we have 3 workers, the best solution would be:

        10 20 30 40 50 | 60 70 | 80 90

And the largest partition in this case is 170 (80+90)

Constraints:
    The number of cabinets we will work with is [2..15]
    The max number of workers we will have is [2..15]

This is a nutshell is a problem of generating all N (number of workers) subsets of the cabinets such that the following is always true:

        (1) A subset must contain only adjacent cabinets
        (2) Cabinets can not repeat
        (3) Cabinets can not be omitted: The total number of cabinets in all subsets gives
        us the total set back
        (4) Subsets cannot be empty

Here are a couple approaches to this problem:

(1) First we can generate all the possible valid subsets as follows:
We set a globalMax to be the total number of folders.
We start with the full set of cabinets and we divide this set into two subsets LeftSet and RightSet.
We then take the RightSet and again divide it by into two sets.
We repeat this process until we have generated the same number of sets as we have workers.
For each subset that we generate in this manner we calcuate the LocalMax.
We then compare this LocalMax to the GlobalMax and if GlobalMax is greater than the LocalMax then we set the new GlobalMax to be the value of the LocalMax.
Basically we have found at this point a solution that distributes the folders better.
Once we go through all these sets we return the current GlobalMax.

This can be done in a recursive manner as follows (after lanenal's solution from room 2)

   int globalMax;
   public int getMostWork(int[] f, int w)
   {
      for(int i=0; i<f.length; i++) globalMax += f[i];
      genSubsets(f, -1, w, 0);
      return globalMax;
   }
   void genSubsets(int[] f, int from, int w, int localMax)
   {
      int sum = 0;
      // Final subset
      if(w==1)
      {
        // get the folders for this subset
      for( int i=from+1; i<=f.length-w; i++) sum += f[i];
         // is this the most folders for the current subsets?
         // If yes then update the localMax
         if(localMax<sum) localMax = sum;
         // Is our localMax less than (better) the globalMax
         if(localMax < globalMax) globalMax = localMax;
         return;
      }

      for( int i=from+1; i<=f.length-w; i++)
      {
         // the LeftSubset folders sum
      sum += f[i];
      // Generate the RightSubset by dividing the current
      // subset in two with the pivot at i.
      // Propagate localMax to the RightSubset
      genSubsets(f, i, w-1, sum>localMax?sum:localMax);
      }
   }

(2) Application of Binary Search. For a non-recursive example of this approach please look at Ukraine's code in room 1.

(3) We can also use Dynamic Programming. I will leave this as an exercise to the reader.


----------------------------------------------code------------------------------------------------------------------------------
#include<stdio.h>
#include<bits/stdc++.h>
typedef int lli;
using namespace std;

int getMostWork(vector <int> v, int m)
{

int l=0,r=0;
int size=v.size();
for(int i=0;i<size;i++)
{
r+=v[i];
}

for(int i=0;i<size;i++)
{
l=max(l,v[i]);
}
 
int ret=r;
int ff=0;
while(l<=r)
 {
  if(l==r) ff=1;
   int mid=(l+r)/2;
   int cov=1;
   int sum=0;
   for(int i=0;i<size;i++)
    {
    if(sum+v[i]>mid)
     {
      cov++;
      sum=v[i];
 }
 else
 {
   sum+=v[i];
 }
     
}
 
//  cout<<" l "<<l<<" "<<r<<"  count "<<cov<<" mid "<<mid<<endl;
if(cov<=m)
 {
  //if(cov==m)
   ret=min(ret,mid);
   r=mid;
 }
 else
 {
  l=mid+1;
 }
 if(ff==1) break;
 }
 return ret;

}



int arr[1000000];
int main()
{
int t;
cin>>t;
while(t--)
 {
  int n,m;
  cin>>n>>m;
  vector<int> v;
  for(int i=0;i<n;i++)
    {
   int a;
    cin>>a;
    v.push_back(a);
  }
  
  int ans=getMostWork(v,m);
   cout<<ans<<endl;
 }


}