Doctor Chef | DRCHEF | CodeChef


Chef is multi-talented. He has developed a cure for coronavirus called COVAC-19. Now that everyone in the world is infected, it is time to distribute it throughout the world efficiently to wipe out coronavirus from the Earth. Chef just cooks the cure, you are his distribution manager.
In the world, there are N countries (numbered 1 through N) with populations a1,a2,…,aN. Each cure can be used to cure one infected person once. Due to lockdown rules, you may only deliver cures to one country per day, but you may choose that country arbitrarily and independently on each day. Days are numbered by positive integers. On day 1, Chef has x cures ready. On each subsequent day, Chef can supply twice the number of cures that were delivered (i.e. people that were cured) on the previous day. Chef cannot supply leftovers from the previous or any earlier day, as the cures expire in a day. The number of cures delivered to some country on someday cannot exceed the number of infected people it currently has, either.
However, coronavirus is not giving up so easily. It can infect a cured person that comes in contact with an infected person again ― formally, it means that the number of infected people in a country doubles at the end of each day, i.e. after the cures for this day are used (obviously up to the population of that country).
Find the minimum number of days needed to make the world corona-free.

Input

  • The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
  • The first line of each test case contains two space-separated integers N and x.
  • The second line contains N space-separated integers a1,a2,…,aN.

Output

For each test case, print a single line containing one integer ― the minimum number of days.

Constraints

  • 1≤T≤103
  • 1≤N≤105
  • 1≤ai≤109 for each valid i
  • 1≤x≤109
  • the sum of N over all test cases does not exceed 106

Subtasks

Subtask #1 (20 points): a1=a2=…=aN
Subtask #2 (80 points): original constraints

Solution (C++)

#include
using namespace std;
#define mod 1000000007
#define ll long long int
ll find_lowerBound(vector< ll>vec,ll x)
{
    vector<ll>::iterator it = lower_bound(vec.begin(), vec.end(), x);
    ll lowerb = it - vec.begin();
    return lowerb;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
       ll size, x, sum=0;
       cin>>size >> x;
       vector<>vec(size);
       for(int i=0; i < size; i++)
       {
          cin >>vec[i];
       }

       sort(vec.begin(), vec.end());
       ll low=find_lowerBound(vec,x);

       for(int i=low; i
       {
            if(x<vec[i])
            {
              while(x<vec[i])
              {
                 x = x*2;
                 sum++;
              }
              sum++;
            }
           else
             sum++;
           x = 2*vec[i];
        }
        ll count =low+sum;
        if(low != 0)
        {
            sum = 0;
            low--;
            for(int i=low; i<size; i++)
            {
                if(x < vec[i])
                {
                    while(x<vec[i])
                    {
                        x = 2*x;
                        sum++;
                    }
                    sum++;
                }
                else
                  sum++;
                x = 2*vec[i];
            }
            if(sum+low<count)
                cout<<sum+low<< endl;
            else
                cout<<count<< endl;
        }
        else
            cout<<count<<endl;
    }
  return 0;
}


100 Best Headphone under 600

Comments

Post a Comment

Popular posts from this blog

Boxes through a Tunnel | HackerRank

You are transporting some boxes through a tunnel, where each box is a  parallelepiped , and is characterized by its length, width and height. The height of the tunnel   feet and the width can be assumed to be infinite. A box can be carried through the tunnel only if its height is strictly less than the tunnel's height. Find the volume of each box that can be successfully transported to the other end of the tunnel. Note: Boxes cannot be rotated. Input Format The first line contains a single integer  , denoting the number of boxes.  lines follow with three integers on each separated by single spaces    ,   and   which are length, width and height in feet of the  -th box. Constraints Output Format For every box from the input which has a height lesser than   feet, print its volume in a separate line. Sample Input 0 4 5 5 5 1 2 40 10 5 41 7 2 42 Sample ...
Read more

Array Manipulation | HackerRank

Image
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in your array. For example, the length of your array of zeros  . Your list of queries is as follows: a b k 1 5 3 4 8 7 6 9 1 Add the values of   between the indices   and   inclusive: index -> 1 2 3 4 5 6 7 8 9 10 [ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ] [ 3 , 3 , 3 , 3 , 3 , 0 , 0 , 0 , 0 , 0 ] [ 3 , 3 , 3 , 10 , 10 , 7 , 7 , 7 , 0 , 0 ] [ 3 , 3 , 3 , 10 , 10 , 8 , 8 , 8 , 1 , 0 ] The largest value is   after all operations are performed. Function Description Complete the function  arrayManipulation  in the editor below. It must return an integer, the maximum value in the resulting array. arrayManipulation has the fo...
Read more

String Validators | HackerRank

Python has built-in string validation methods for basic data. It can check if a string is composed of alphabetical characters, alphanumeric characters, digits, etc. str.isalnum() This method checks if all the characters of a string are alphanumeric  (a-z, A-Z and 0-9) . >>> print 'ab123'.isalnum() True >>> print 'ab123#'.isalnum() False str.isalpha() This method checks if all the characters of a string are alphabetical  (a-z and A-Z) . >>> print 'abcD'.isalpha() True >>> print 'abcd1'.isalpha() False str.isdigit() This method checks if all the characters of a string are digits  (0-9) . >>> print '1234'.isdigit() True >>> print '123edsd'.isdigit() False str.islower() This method checks if all the characters of a string are lowercase characters  (a-z) . >>> print 'abcd123#'.islower() True >>> print 'Abcd123#'.islower() False str....
Read more