Как решать подобные задачи?

Question

[impelix]

Вы управляете роботом, который находится на стадионе с целочисленной длиной круга. Первоначально
робот находится на линии старт/финиш.
Робот принимает команды “run k”, которая направляет его ровно на k метров против часовой стрелки
относительно его текущей локации и сообщает общее количество пройденных кругов со времени старта
(то есть число пересечений линии старт-финиш после начала забега).
Ваша задача — определить длину круга, используя не более 100 команд.
Первое что приходит на ум - это бинарный поиск, но как прийти к решению и понять что это именно оно, непонятно.

Comments

[Rsa97]

Без ограничения на максимальную длину круга задача не решается

[code_panik]

Rsa97, почему нет? Если круг слишком длинный и безуспешно израсходовать все 100 команд, достаточно сказать, что длина круга больше 100 * k? Тоже ответ, наверняка предусмотренный условием.

[impelix]

Rsa97, 10^9 ограничение

Answer 1

[Wataru]

Во всех таких задачах на запросы почти всегда надо приспособить бинарный поиск.

Так и тут. Перебирайте длину круга бинарным поиском. И запоминайте, сколько метров вы уже прошли и сколько полных кругов получили в ответ.

Вот у вас есть гипотеза m=(l+r)/2 - вы хотите проверить, а как она соотносится с длинной круга. Допустим, вы уже прошли x метров и прошли k полных кругов. Уже только из этой информации можно оценить, какая длина круга может быть. Во-первых, убедитесь, сравните floor(x/m) и k. Если floor(x/m) > k вы уже знаете, что длина круга больше m, ведь для круга длины m и более коротких значений вы бы насчитали floor(x/m) или больше оборотов. Если floor(x/m) < k, то уже очевидно, что длина круга меньше m. Если же floor(x/m) = k, то спросите run m-x%m - сколько осталось пройти до финиша, если бы длина круга была равна m. Если вы получили в ответ 1, то значит круг не длинее m. В протвином случае круг строго длиннее m.

Comments

[impelix]

Грубо говоря что то похожее.

int main(){
    int l = 1, r = 1000000000;
    int m = (l + r) /2;
    int x = 50000000000;
    int k;
    int sum = 100;
    int pred;
    cout << "run " << x;
    cin >> k;
    while(l != r) {
        if (floor(x / m) > k) {
            cout << "run " << x += x/2;
            fflush(stdout);
            l = m;
            m = (l + r) / 2;
            sum += x;
            pred = k;
            cin >> k
        } else if (floor(x / m) < k) {
            cout << "run " << x -= x/2;
            fflush(stdout);
            pred = k;
            r = m;
            m = (l + r) / 2;
            sum += x;
            cin >> k;
        } else if (floor(x / m) == k) {
            cout << "run " << m - x % m;
            fflush(stdout);
            cin >> k;
            if (k - pred == 1) {
                r = m;
                m = (l + r) /2;
                x += x/2
            }
            else{
                l = m + 1;
                m = (l + r) /2;
                x -= x/2
            }
        }
    }
}

[impelix]

знаю что += и -= нельзя, это пример просто

[impelix]

единственный момент не понятен, как считать шаг x

[Wataru]

impelix, Ну, в самом начале можно сделать любой шаг. А в x надо считать сумму всех выведенных run. Грубо говоря cout << "run " << m - x%m << "\n"; x += m - x%m;

Так же, в случае, когда floor(x/m) != k можно сдвинуть границу не выводя никаких команд.

Еще надо очень аккуратно со смыслом l и r. Это границы которые искомая величина может принять? тогда в случае, если вы знаете, что m < ответа, надо присваивать l = m+1;. Если вы поняли, что ответ может быть и m, то надо присваивать без 1.

Еще аккуратно посмотрите случай l==r-1: а не зависнет ли программа? Она потом спросит про l, но может ли прийти к выводу, что ответ >= m и не сдвинуть границы?

Edit: и да, в k надо накапливать сумму всех ответов от системы, а не последний ответ. Суммарное количество оборотов.

Answer 2

[romazhan]

1. Установи нижнюю границу длины круга равной 1 и верхнюю границу равной некоторому большому числу, например, 10^9. Можно выбрать любое подходящее значение в качестве верхней границы.
2. Начни бинарный поиск, используя установленные границы. На каждой итерации вычисли среднее значение между нижней и верхней границами длины круга и выполни команду "run k" для этого значения.
3. После каждой команды "run k" проверь, сколько кругов было пройдено с момента старта. Если количество кругов увеличилось, значит, длина круга была занижена, и ты можешь обновить нижнюю границу длины круга до среднего значения.
4. Если количество кругов не изменилось, значит, длина круга была завышена, и ты можешь обновить верхнюю границу длины круга до среднего значения.
5. Повторяй шаги 2-4 до тех пор, пока не будет достигнуто максимальное количество команд (100 в данном случае).

Comments

[Wataru]

Тут только проблема в том, что последующие команды run k вы выполняете не с начала круга, а уже с накопленным пробегом. Так что можно перескочить за фишиш даже сделав шаг короче длины круга.

[romazhan]

Wataru, лол, тогда хз, сложно. На ум приходит лимит функции или методы числовой оптимизации, но в задаче не задано время, так что хз, думаю.

[Wataru]

polak228, Да не, можно приспособить и бинарный поиск. Надо только помнить сколько вы метров уже суммарно прошли и сколько целых оборотов сделали.