ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1607. Taxi

O(1) c++ solution and BEST EXPLANATION
Posted by Mohamed 10 Sep 2022 21:02
i kinda changed the variables
a = the first sum suggested by petr
b = the ---------------------- taxi driver
c = amount added by petr everytime
d = ---------------- taxi driver
we can say that at step n of bargaining:
petr -> a + n*c
taxi -> b - n*d

where looking for a time when petr's suggestion is less than the drivers
which means a + nc <= c - n*d
but there sometime when petr suggest more than what the driver suggest the previous time.
that's why i am comparing between the last petr's suggestion and the previous one of the driver a+c*n > b-d*(n-1). in this case petr says ok to the taxi driver and do not suggest more than that.


void solve() {
    int a, c, b, d;
    cin >> a >> c >> b >> d;
    if (a >= b) {
        cout << a;
        return;
    }
    int n = (b-a)/(c+d);
    if ((b-1)%(c+d)!=0) n++;
    if (a+c*n > b-d*(n-1)) {
        cout << b - d*(n-1) << ln;
    }
    else {
        cout << a + n*c << ln;
    }
}


Edited by author 10.09.2022 21:11
Re: O(1) c++ solution and BEST EXPLANATION
Posted by zhnzhang61 28 Jan 2024 07:35
could you help explain why:     if ((b-1)%(c+d)!=0) n++;
Re: O(1) c++ solution and BEST EXPLANATION
Posted by Timur R 25 Jun 2024 16:29
this is more simply code:

    int a, b, c, d; cin >> a >> b >> c >> d;
    if (a >= c) {
        cout << a;
        return;
    }
    int l = (c - a) / (b + d);
    a += b * l;
    c -= d * l;
    if (a + b <= c) cout << a + b;
    else cout << c;