CF 102386A - Строительство башни

Каждый этаж башни требует ровно один килограмм железа и один килограмм дерева.

codeforcescompetitive-programming

CF 102386A - \u0421\u0442\u0440\u043e\u0438\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u043e \u0431\u0430\u0448\u043d\u0438

Rating: -
Tags: -
Solve time: 13m 8s
Verified: yes

Solution

Problem Understanding

Каждый этаж башни требует ровно один килограмм железа и один килограмм дерева. Если килограмм железа стоит X рублей, а килограмм дерева стоит Y рублей, то один полностью построенный этаж всегда обходится в X + Y рублей.

Вход содержит бюджет N, цену килограмма железа X и цену килограмма дерева Y. Нужно найти максимальное целое количество этажей, для которого суммарная стоимость материалов не превышает бюджет. Поскольку материалы для одного этажа нельзя заменить или купить частично, задача сводится к нахождению максимального k, такого что k * (X + Y) <= N.

Ограничение N <= 10^9, а также ограничения X <= 10^9 и Y <= 10^9 позволяют использовать арифметические операции за константное время. Перебирать количество этажей уже нельзя считать хорошим решением: при маленьких ценах число возможных этажей может достигать сотен миллионов. Решение должно работать за O(1).

Есть несколько границ, на которых легко ошибиться. Например, при входе 3, 2, 1 один этаж стоит ровно 3, поэтому ответ равен 1. Если написать условие перебора как cost < N, вместо cost <= N, такой случай будет пропущен и получится неверный ответ 0.

Другой случай возникает, когда денег недостаточно даже на один этаж. Для входа 5, 1, 10 один этаж стоит 11, поэтому правильный ответ равен 0. Подход, который отдельно проверяет возможность покупки железа и дерева, может ошибочно решить, что железо уже позволяет начать строительство, хотя этаж требует оба материала.

Наконец, нужно учитывать большие значения цен. При N = 10^9, X = 10^9, Y = 10^9 стоимость одного этажа равна 2 * 10^9, поэтому ответ равен 0. В языках с фиксированными целочисленными типами важно хранить сумму X + Y в достаточно широком типе.

Approaches

Самый прямой способ заключается в последовательном построении этажей. Можно начать с нуля, каждый раз добавлять стоимость одного этажа и увеличивать количество построенных этажей, пока следующая покупка укладывается в бюджет. Такой алгоритм корректен, потому что он проверяет этажи в порядке возрастания и останавливается ровно перед первым недоступным этажом.

Проблема в количестве итераций. В худшем случае X = 1 и Y = 1, а N = 10^9. Тогда один этаж стоит всего 2 рубля, и перебор выполнит примерно 5 * 10^8 итераций. Для задачи, ответ на которую можно получить одной арифметической операцией, это совершенно избыточно.

Ключевая идея состоит в том, что стоимость каждого этажа одинакова. Если один этаж стоит X + Y, то два этажа стоят 2 * (X + Y), три этажа стоят 3 * (X + Y), и так далее. Нам не нужно моделировать строительство каждого этажа, достаточно разделить весь бюджет на стоимость одного этажа и взять целую часть результата.

Иными словами, искомое количество равно N // (X + Y). Целочисленное деление автоматически отбрасывает неполный последний этаж, а именно это нам и требуется.

Approach Time Complexity Space Complexity Verdict
Brute Force O(N / (X + Y)), до O(10^9) O(1) Too slow
Optimal O(1) O(1) Accepted

Algorithm Walkthrough

  1. Считаем бюджет N, стоимость килограмма железа X и стоимость килограмма дерева Y. Эти три числа полностью определяют стоимость любого возможного этажа.
  2. Вычисляем стоимость одного этажа как cost = X + Y. Один этаж всегда требует оба материала, поэтому складывать цены нужно до вычисления ответа.
  3. Делим бюджет на стоимость одного этажа с целочисленным делением: answer = N // cost. Полученное число показывает максимальное количество полных этажей, которые можно оплатить.
  4. Выводим answer. Остаток от деления представляет деньги, которых недостаточно для ещё одного полного этажа, поэтому использовать их для увеличения ответа нельзя.

Why it works

Пусть алгоритм возвращает k = N // (X + Y). По свойству целочисленного деления выполняется k * (X + Y) <= N, значит, k этажей действительно можно оплатить. При этом (k + 1) * (X + Y) > N, потому что k является целой частью частного. Значит, построить k + 1 этажей уже невозможно. Следовательно, k является не просто допустимым, а максимальным количеством этажей.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    X = int(input())
    Y = int(input())

    cost = X + Y
    answer = N // cost

    print(answer)

if __name__ == "__main__":
    solve()

Сначала программа читает три значения из отдельных строк, как задано форматом входа. Переменная N хранит весь доступный бюджет, а X и Y задают цены двух материалов.

Затем вычисляется cost = X + Y. Здесь нет необходимости отдельно рассчитывать количество доступного железа и количество доступного дерева, поскольку каждый этаж требует одинаковое количество обоих материалов, ровно по одному килограмму.

Строка answer = N // cost непосредственно реализует основную формулу. Обычное / в Python создало бы число с плавающей точкой, а // сразу возвращает нужное целое количество полностью оплаченных этажей.

Граница включается автоматически. Если бюджет делится на стоимость этажа без остатка, например N = 3 и cost = 3, результатом будет 1, а не 0. Python также не имеет проблемы с переполнением целых чисел для заданных ограничений.

Worked Examples

Sample 1

Для входа N = 3, X = 2, Y = 1 один этаж стоит 3 рубля.

N X Y cost = X + Y answer = N // cost
3 2 1 3 1

Бюджета ровно хватает на один этаж. Второй этаж потребовал бы уже 6 рублей, поэтому ответ 1 максимален. Этот пример также проверяет границу, когда бюджет полностью совпадает со стоимостью некоторого количества этажей.

Sample 2

Для входа N = 5, X = 1, Y = 10 один этаж стоит 11 рублей.

N X Y cost = X + Y answer = N // cost
5 1 10 11 0

Даже один этаж оплатить нельзя. Целочисленное деление возвращает 0, что корректно отражает отсутствие доступных полных этажей. Этот пример проверяет ситуацию, когда бюджет меньше стоимости одного этажа.

Complexity Analysis

Measure Complexity Explanation
Time O(1) Выполняется фиксированное число арифметических операций
Space O(1) Используется только несколько целочисленных переменных

При максимальных значениях входа алгоритм по-прежнему выполняет ровно одну операцию деления после вычисления стоимости этажа. Он не зависит от размера ответа, поэтому даже потенциальные сотни миллионов этажей не увеличивают время работы или расход памяти.

Test Cases

# helper: run solution on input string, return output string
import sys
import io

def solve():
    input = sys.stdin.readline

    N = int(input())
    X = int(input())
    Y = int(input())

    print(N // (X + Y))

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    try:
        solve()
        return sys.stdout.getvalue().strip()
    finally:
        sys.stdin = old_stdin
        sys.stdout = old_stdout

# provided samples
assert run("3\n2\n1\n") == "1", "sample 1"
assert run("5\n1\n10\n") == "0", "sample 2"

# minimum-size input
assert run("1\n1\n1\n") == "0", "minimum budget cannot buy one floor"

# maximum-size values
assert run("1000000000\n1000000000\n1000000000\n") == "0", \
    "one floor costs more than the entire budget"

# all values equal
assert run("100\n10\n10\n") == "5", \
    "each floor costs 20"

# exact divisibility
assert run("20\n3\n2\n") == "4", \
    "exactly four floors fit into the budget"

# one ruble short of another floor
assert run("19\n3\n2\n") == "3", \
    "four floors would cost 20"
Test input Expected output What it validates
1 / 1 / 1 0 Минимальный бюджет и отсутствие возможности построить этаж
1000000000 / 1000000000 / 1000000000 0 Максимальные значения и большая сумма цен
100 / 10 / 10 5 Одинаковые цены и обычное целочисленное деление
20 / 3 / 2 4 Точное попадание в бюджет без остатка
19 / 3 / 2 3 Проверка границы, когда одного рубля не хватает на следующий этаж

Edge Cases

При минимальном бюджете N = 1, X = 1, Y = 1 стоимость этажа равна 2. Алгоритм вычисляет 1 // 2 = 0, поэтому возвращает 0. Ошибочный перебор, который сначала увеличивает число этажей, а уже потом проверяет бюджет, может случайно получить отрицательный остаток или завысить ответ на единицу.

При точном совпадении бюджета со стоимостью этажа вход 3, 2, 1 даёт стоимость 3 и ответ 3 // 3 = 1. Здесь особенно легко ошибиться, если проверять строгое неравенство cost < N вместо правильного cost <= N.

Когда денег недостаточно на один этаж, например 5, 1, 10, стоимость равна 11, поэтому 5 // 11 = 0. Наличие достаточного количества денег хотя бы на один из материалов ничего не меняет, поскольку этаж требует одновременно и железо, и дерево.

При больших значениях N = 10^9, X = 10^9, Y = 10^9 стоимость этажа составляет 2 * 10^9. Деление даёт 0. Python корректно хранит такую сумму как целое число, поэтому дополнительная защита от переполнения не нужна.

Наконец, вход 19, 3, 2 проверяет ситуацию непосредственно перед границей. Один этаж стоит 5, три этажа стоят 15, а четыре уже требуют 20. Формула 19 // 5 = 3 сразу выбирает правильный ответ и не допускает ошибки на единицу.