Can someone help me with Step-2 C: Very Easy Task↵
↵
Problem Link : https://codeforces.com/edu/course/2/lesson/6/2/practice/contest/283932/problem/C↵
↵
**My Approach:** if the task can be done in T time, then 1(good) else 0 (bad). So, making 1 copy of the original document will take min(x,y) time, and then both copy machines can simultaneously work. ↵
↵
we need to check whether n copies can be made in T time or not, if I am updating T1 = T-min(x,y) and then checking that can I make n-1 copies in T1 time. Then find the first occurrence of 1 using binary search. It is throwing me an error "Wrong Answer on test case 5" ↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define nl "\n";↵
↵
bool check(int n, int x, int y, ll mid)↵
{↵
mid = mid - min(x, y);↵
n = n - 1;↵
ll res = (mid / x) + (mid / y);↵
return res>=n; ↵
}↵
↵
void solve()↵
{↵
int n, x, y;↵
cin >> n >> x >> y;↵
ll l =0;↵
ll r =1e12; ↵
int ans =-1; ↵
while(l<=r)↵
{↵
ll mid = (l+r)/2; ↵
if(check(n,x,y,mid))↵
{↵
ans = mid; ↵
r = mid-1; ↵
}↵
else↵
{↵
l = mid+1; ↵
}↵
}↵
cout<<ans<<nl; ↵
}↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
#ifndef ONLINE_JUDGE↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
#endif↵
↵
cout << fixed << setprecision(20);↵
ll t = 1;↵
// cin >> t;↵
while (t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
**Actual Approach :** we need to check whether n-1 copies can be made in T time or not. Then, by using binary search find the first occurrence of 1 as it will be the least time to make n-1 copies, and then adding min(x,y) as it will be the time to make the copy of original. ↵
↵
<spoiler summary="AC Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define nl "\n";↵
↵
bool check(int n, int x, int y, ll mid)↵
{↵
ll res = (mid / x) + (mid / y);↵
// cout<<res<<nl; ↵
return res>=n-1; ↵
}↵
↵
void solve()↵
{↵
int n, x, y;↵
cin >> n >> x >> y;↵
ll l =0;↵
ll r =1e10; ↵
ll ans =-1; ↵
while(l<=r)↵
{↵
ll mid = (l+r)/2; ↵
// cout<<"mid : "<<mid<<nl; ↵
if(check(n,x,y,mid))↵
{↵
ans = mid; ↵
r = mid-1; ↵
}↵
else↵
{↵
l = mid+1; ↵
}↵
}↵
cout<<ans+ min(x,y)<<nl; ↵
}↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
#ifndef ONLINE_JUDGE↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
#endif↵
↵
cout << fixed << setprecision(20);↵
ll t = 1;↵
// cin >> t;↵
while (t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
I dont know, where am I making mistake, both logics seems similar to me. ↵
↵
↵
Problem Link : https://codeforces.com/edu/course/2/lesson/6/2/practice/contest/283932/problem/C↵
↵
**My Approach:** if the task can be done in T time, then 1(good) else 0 (bad). So, making 1 copy of the original document will take min(x,y) time, and then both copy machines can simultaneously work. ↵
↵
we need to check whether n copies can be made in T time or not, if I am updating T1 = T-min(x,y) and then checking that can I make n-1 copies in T1 time. Then find the first occurrence of 1 using binary search. It is throwing me an error "Wrong Answer on test case 5" ↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define nl "\n";↵
↵
bool check(int n, int x, int y, ll mid)↵
{↵
mid = mid - min(x, y);↵
n = n - 1;↵
ll res = (mid / x) + (mid / y);↵
return res>=n; ↵
}↵
↵
void solve()↵
{↵
int n, x, y;↵
cin >> n >> x >> y;↵
ll l =0;↵
ll r =1e12; ↵
int ans =-1; ↵
while(l<=r)↵
{↵
ll mid = (l+r)/2; ↵
if(check(n,x,y,mid))↵
{↵
ans = mid; ↵
r = mid-1; ↵
}↵
else↵
{↵
l = mid+1; ↵
}↵
}↵
cout<<ans<<nl; ↵
}↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
#ifndef ONLINE_JUDGE↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
#endif↵
↵
cout << fixed << setprecision(20);↵
ll t = 1;↵
// cin >> t;↵
while (t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
**Actual Approach :** we need to check whether n-1 copies can be made in T time or not. Then, by using binary search find the first occurrence of 1 as it will be the least time to make n-1 copies, and then adding min(x,y) as it will be the time to make the copy of original. ↵
↵
<spoiler summary="AC Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define nl "\n";↵
↵
bool check(int n, int x, int y, ll mid)↵
{↵
ll res = (mid / x) + (mid / y);↵
// cout<<res<<nl; ↵
return res>=n-1; ↵
}↵
↵
void solve()↵
{↵
int n, x, y;↵
cin >> n >> x >> y;↵
ll l =0;↵
ll r =1e10; ↵
ll ans =-1; ↵
while(l<=r)↵
{↵
ll mid = (l+r)/2; ↵
// cout<<"mid : "<<mid<<nl; ↵
if(check(n,x,y,mid))↵
{↵
ans = mid; ↵
r = mid-1; ↵
}↵
else↵
{↵
l = mid+1; ↵
}↵
}↵
cout<<ans+ min(x,y)<<nl; ↵
}↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
#ifndef ONLINE_JUDGE↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
#endif↵
↵
cout << fixed << setprecision(20);↵
ll t = 1;↵
// cin >> t;↵
while (t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
I dont know, where am I making mistake, both logics seems similar to me. ↵
↵