Please help with this: A geniune doubt

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	170
2	Um_nik	162
3	atcoder_official	160
3	maomao90	160
5	djm03178	158
5	-is-this-fft-	158
7	adamant	154
7	Dominater069	154
9	awoo	152
9	luogu_official	152

Can someone help me with Step-2 C: Very Easy Task

Problem Link : https://mirror.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"

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;
}

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.

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;
}

I dont know, where am I making mistake, both logics seems similar to me.

Блог пользователя Kanao