ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1607. Такси

O(1) c++ solution and BEST EXPLANATION
Послано Mohamed 10 сен 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
Послано zhnzhang61 28 янв 2024 07:35
could you help explain why:     if ((b-1)%(c+d)!=0) n++;
Re: O(1) c++ solution and BEST EXPLANATION
Послано Timur R 25 июн 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;