Калькулятор, всерос

Question

Помогите найти ошибку, пожалуйста. Выводится WA, вводные данные неизвестны. //

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

Сначала пользователь вводит целое положительное число n, которое выводится на экран. Затем пользователь может нажимать на три кнопки: A, B и C.

При нажатии на кнопку A число, которое выведено на экран, делится на 2. Если число на экране нечетное, то остаток отбрасывается. Например, результат этой операции для числа 80 равен 40, а для числа 239 равен 119.

При нажатии на кнопку B к числу, которое выведено на экран, прибавляется 1, и результат делится на 2. Остаток от деления отбрасывается. Например, результат операции для числа 80 равен 40, а для числа 239 равен 120.

При нажатии на кнопку C происходит следующее. Если число, которое выведено на экран, положительное, то из него вычитается 1 и результат делится на 2, остаток отбрасывается. Если же перед нажатием на кнопку C на экран было выведено число 0, то оно остается неизменным. Например, результат операции для числа 80 равен 39, а для числа 239 равен 119.

Пользователь ввел число n и собирается нажать на кнопки операций в некотором порядке. В частности, он планирует нажать на кнопку A суммарно a раз, на кнопку B – b раз и на кнопку C – c раз. Его заинтересовал вопрос, какое минимальное число может получиться в результате выполнения описанных операций.

Требуется написать программу, которая по введенному числу n и числам a, b и c, показывающим количество произведенных на калькуляторе операций разного типа, определяет минимальное число, которое может получиться в результате работы калькулятора.

Формат ввода Входной файл содержит четыре целых числа: n, a, b и c (1 ≤ n ≤ 10^18, 0 ≤ a, b, c ≤ 60). Числа заданы на одной строке, соседние числа разделены одним пробелом.

Формат вывода Требуется вывести одно число — минимальное число, которое может получиться у пользователя в результате работы калькулятора.

Пример Ввод
72 2 1 1 Вывод 4

#include <iostream>
using namespace std;
int main(){
    long long n;
    int a, b, c;
    cin>> n;
    cin>> a;
    for(int i = 0; i < a; i++){
        n /= 2;
    }
    cin>> b;
    for(int i = 0; i < b; i++){
        n++;
        n /= 2;
    }
    cin>> c;
    for(int i = 0; i < c; i++){
        if(n > 0)
          n--;
          n /= 2;
        if (n == 0)
        n = 0;
    }
    cout<< n;
    return 0;
}

Answer 1

Ну, например, динамическое программирование.

Пусть d[i][j][k] — минимальное число, которое можно получить из n после нажатия i раз кнопки A, j раз кнопки B и k раз — кнопки C.

Далее все очевидно...

long long d[61][61][61];

int main()
{
    long long a, b, c, n;
    cin >> n >> a >> b >> c;

    d[0][0][0] = n;
    for (int i = 0; i <= a; i++)
    for (int j = 0; j <= b; j++)
    for (int k = 0; k <= c; k++)
    {
        if (i < a)
            d[i+1][j][k] = min(d[i][j][k], d[i][j][k]/2);
        if (j < b)
            d[i][j+1][k] = min(d[i][j][k], (d[i][j][k]+1)/2);
        if (k < c)
            d[i][j][k+1] = min(d[i][j][k], (d[i][j][k]-1)/2);
    }
    cout << d[a][b][c];
}

В последнем случае проверка на 0 не нужна, так как при значении 0

(d[i][j][k]-1)/2

даст 0.

"По-моему, так" (с) Пух

Answer 2

Ваша программа ошибается на некоторых входах. Например, для входа n = 2, a = 1, b = 1, c = 0 она вернёт единицу, хотя можно получить ноль. Вы применяете кнопки в порядке ab. Порядок ba иногда даёт меньший результат. Анализ ниже.

Посмотрим внимательно на функции a(n), b(n), c(n) и их комбинации. Все три функции не убывают. Значит не убывают и любые их комбинации.

Сравним комбинации:

b(a(n)) a(n)     n        b(n)     a(b(n))
k       2k       4k       2k       k
k       2k       4k + 1   2k + 1   k
k + 1   2k + 1   4k + 2   2k + 1   k
k + 1   2k + 1   4k + 3   2k + 2   k + 1

Получается что b(a(n)) >= a(b(n)) для любых n. На языке кнопок это означает что (многоточия обозначают один и те же кнопки в обоих строках):

....ab.... # в этой строке результат не меньше чем в следующей
....ba.... # в этой строке результат не больше чем в предыдущей

Следовательно, если какая-то строка ...ab... даёт минимальный результат, то строка ...ba... даёт результат не больше, а значит тоже минимальный. То есть, при поиске минимальной последовательности мы можем не рассматривать любые последовательности с комбинацией ab внутри.

Аналогично доказывается что есть лучшая строка без cb и без ca. То есть, после кнопки c других кнопок быть не должно. Значит все c собираются в конце строки. Так как комбинация ab тоже "запрещена", получаем единственную комбинацию которая порождает самое маленькое значение (вне зависимости от значения n):

b...ba...ac...c

Решение:

#include <iostream>

int main() {
    unsigned long long n;
    int a, b, c;
    std::cin >> n >> a >> b >> c;

    for (int i = 0; i < b; ++i) {
        n = (n + 1) / 2ULL;
    }
    for (int i = 0; i < a; ++i) {
        n = n / 2ULL;
    }
    for (int i = 0; i < c; ++i) {
        if (n > 0) {
            n = (n - 1) / 2ULL;
        }
    }

    std::cout << n << '\n';
}

БЛОГ НА HUSL

Калькулятор, всерос

Ответы (2 шт):