here is python3 solution:
t=int(input())
for _ in range(t):
n,x=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
i=0
while i<n and a[i]<x:
i+=1
day=i
if i<n and a[i]!=x and i>0 and a[i-1]*2>=x:
day-=1
i-=1
x=a[i]
while i<n:
#print(x,a[i],day)
if a[i]==x:
i+=1
if(i<n):
x=min(2*x,a[i])
day+=1
print(day)@sudipandatta
If possible Please share the test case where my logic is failing
https://www.codechef.com/viewsolution/35595598
because log2 of 0 does not exist. you are dividing input with x and if x>input then (input/x)=0 and log2 of zero will give you floating point error .
Can someone tell me the test case which is causing my solution to fail. I canāt seem to figure it out.
Solution
int n,x;
cin>>n>>x;
int arr[n];
fora(i,n) cin>>arr[i];
sort(arr,arr+n);
int tot=0;
int ptr=0;
int days=0;
while(ptr<n&&arr[ptr]<=x&&2*arr[ptr]<x) ptr++;
while(x<arr[n-1]) {
bool fl=0,fl1=0;
if(arr[ptr]<=x) {
fl1=1;
if(2*arr[ptr]>x) {
x=2*arr[ptr];
fl=1;
tot++;
days++;
ptr++;
}
}
if(!fl) {
x*=2;
days++;
// ptr++;
}
// cout<<x<<"\n";
}
// cout<<days<<" "<<tot<<"\n";
cout<<days+(n-tot)<<"\n";
Can anybody tell me what is wrong with my code, Thanks in advance
Oh got it thank you!
log2() is not giving accurate result for all values, so thats the problem
Such a lame question. So many guys passed it with hit and trial without any proof of correctness.
Such questions should be discouraged. CodeChef needs to work on its questions, should be encouraged to have questions which have amazing solution, not these hit and trial type questions.
Thanks for the suggestion man. Really helped a lot.
Can anyone please look into my code. My answer is correct for 7/10 test cases but giving wrong for just 3 cases. Pls can anyone find out the mistake?? libk of the code in case u need it: https://onlinegdb.com/Skc2qG5kw
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int t=0;
cin>>t;
while(t--)
{
ll n=0; ll vac=0;
cin>>n>>vac;
ll a[n]={0};
for(ll i=0;i<n;i++)
{
cin>>a[i];
}
//sorting array
sort(a,a+n);
//case: when vaccine is greater than country having highest no. of infected population
if(vac>=a[n-1])
{
cout<<n<<endl;
continue;
}
// all the other cases
else
{
ll pos=0; // for finding the correct position from where we have to count no. of days
ll days=0;
for(ll i=0;i<n;i++)
{
if(a[i]>=vac)
{
pos=i;// for eg. lets i=4, when the condition is satisified
break;// that means country at a[0],a[1],a[2],a[3] can be
//cured in 4 days after rest of the countries are cured.
}
}
days=pos; //so we assign same to the days from above loop result.
while(pos<n)
{
days++;// since days=0, so day 1,2,3,.....
if(a[pos]<=vac)
{
vac=a[pos];
pos++;
}
vac=vac*2;
}
cout<<days<<endl;
}
}
return 0;
}
If anyone is having difficulty ,here is a detail explanation ( not a video tutorial) for this problem In this link
I think you missed one condition,
suppose input is:
3 10
3 7 21
no of days by ur method will be 5 but they are actually 4
see if we cure 7 on first day our vaccines will be 14 which is greater than 10
thankyou so much bro ! i fried my brain for more than 4 hours still couldnt find this loophole . thankyou so mch !!
#include <bits/stdc++.h>
using namespace std;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define int long long
void solve()
{
int N, x, a;
cin >> N >> x;
multiset<int> arr;
for (size_t i = 0; i < N; i++)
{
cin >> a;
arr.insert(a);
}
int noOfDays = 0, temp = 0, smallerCountries = 0;
for (auto it = arr.begin(); it != arr.end(); ++it)
{
if (*it < x)
smallerCountries += 1;
}
auto it = arr.begin();
advance(it, smallerCountries);
while (it != arr.end())
{
while (x < *it)
{
x *= 2;
noOfDays += 1;
}
temp = x - *it;
if(temp)
x = *it;
noOfDays += 1;
x *= 2;
advance(it, 1);
}
noOfDays += smallerCountries;
cout << noOfDays << "\n";
}
int32_t main()
{
IOS;
int t;
cin >> t;
while (t--)
solve();
}
I got 3 test case failed on the above solution. Can anybody help?
instead of this, do
x = max(X , 2 * (*it)); // keep X ( the one from input ) unchanged.
noOfDays ++;
can someone tell what those three testcases 6,7,9 could possibly look like, link to my solution here
Thanks for the shortened code but the resultās still the same. Am I missing something?
I did something very similar in the beginning and got all test cases correct but then next day went for a recheck and a test case was wrong and then I started overthinking on it ā¦That is Sadā¦
Sorry i couldnāt understand there is some error with smallCountries values,
i ammended your code and got AC.
https://www.codechef.com/viewsolution/35618932
i did it little the way i actually did in contest.