Задания с CodeForces. Вариант решения есть, но не подходит для всех тестов. Может неправильно понял реализацию решения?

Question

[stioann]

Суть задачи в том, что имеется лифт, который стоит на 0 этаже. Нам нужно попасть на этаж (D) и для этого у нас есть всего две кнопки "+3" и "-2". D на входе больше или равно "-1000" и меньше или равно "1000". На выход программа должна дать минимальное количество нажатий для достижения нужного этажа. Решение реализовано на C++.

Код есть, но не проходит тест до конца. Может я условие неправильно реализовал? Или не правильно понял как решить задачу.

Код:

#include <iostream>
#include <cmath>

int main() {
    int D;
    std::cin >> D;

    D = std::abs(D);

    int count = 0;

    while (D != 0) {
        if (D >= 3) {
            D -= 3;
            count++;
        } else {
            D += 2;
            count++;
        }
    }

    std::cout << count << std::endl;

    return 0;
}

Comments

[WbICHA]

D = std::abs(D);

А не подскажешь что именно делает функция abs?)

[Alexandroppolus]

WbICHA, абсолютное значение, abs(1) === 1, abs(-1) === 1

[WbICHA]

Alexandroppolus, я знаю, это был намёк автору.)

Answer 1

[Alexandroppolus]

тебе надо отдельно рассмотреть D > 0 и D < 0, потому что в первом кейсе сначала едем вверх по 3 этажа и потом чуть вниз по 2, а во втором - сначала вниз по 2 этажа, потом чуть вверх по 3

далее, в первом случае могут быть 3 кейса, по остатку от деления D на 3. Если 0, то "-2" не понадобится, если 1, то можно будет обойтись одним нажатием на "-2", иначе двумя. Для D<0 - аналогично.

и всё можно решить формулами, без цикла, за O(1)

Comments

[stioann]

То есть я изначально неправильно подумал решать через модуль. Но почему-то мозг теперь отказывается это решать без модуля и цикла. Спасибо. Буду думать над решением.

[Wataru]

stioann, Alexandroppolus, можно над случаями особо не думать, а просто перебрать до 0-1 шагов +3, 0-2 шагов -2 вложенными циклами, потом, если оставшийся путь отрицателен и делится на 2, или положителен и делится на 3, брать оставшееся количество ходов. Из всех вариантов выбираем мнинимальный.

[Alexandroppolus]

Wataru, там всё решается в одну строку

count = d < 0 ? (-d) / 2 + ((-d) % 2) * 3 : d / 3 + (d % 3) * 2;

(в плюсах ведь целочисленное деление для интов?)

[Wataru]

Alexandroppolus, Да, целочисленное. Да, это решение. Я лишь предложил более простое в понимании O(1) решение без аккуратного разбора случаев.

[stioann]

Спасибо вам. Пытался понять уже несколько дней. Почему-то не лезло решение в голову.

Answer 2

[Wataru]

Для -3 ваша программа выведет 1, когда как правильный ответ 4 (+3-2-2-2).