Please help with this: A geniune doubt

#	User	Rating
1	Benq	3783
2	jiangly	3772
3	tourist	3706
4	maroonrk	3609
5	Um_nik	3591
6	fantasy	3526
7	ko_osaga	3500
8	inaFSTream	3477
9	cnnfls_csy	3427
10	zh0ukangyang	3423

#	User	Contrib.
1	Um_nik	185
2	awoo	182
3	nor	172
4	-is-this-fft-	170
5	adamant	169
6	maroonrk	165
7	antontrygubO_o	160
8	SecondThread	158
9	dario2994	151
9	kostka	151

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"

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.

Comments (2)

Write comment?

fried_brain

2 months ago, # |

← Rev. 3 →

Your logic is correct, the implementation is a bit off.

In the check function, there might be a case when "mid" becomes negative, in that case if abs(mid) is less than "x" and "y", "res" would be "0", losing the negativeness. C++ treats $$$-a/b$$$ as 0, when $$$a < b$$$, the negativity is not preserved. To ensure that just make sure mid is non-negative. AC Code

→ Reply

Kanao

2 months ago, # ^ |

hey, thanks alot!

I will check this out, thanks for helping i was struggling with this since a very long time.

Kanao's blog