10726. Торты

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

Зная n ингредиентов, необходимых для приготовления одного торта, а также ингредиентов, которые имеются у Вас на кухне, определите количество тортов, которое Вы сможете приготовить.

Вход. Первая строка содержит одно целое число n (1 ≤ n ≤ 10).

Далее следуют n строк, по одной на каждый ингредиент. Каждая из этих строк содержит два положительных целых числа: первое – необходимое количество этого ингредиента на торт, второе – количество этого ингредиента у Вас на кухне.

Количество всех ингредиентов является целым числом от 1 до 10⁴.

Выход. Выведите одно целое число: максимальное количество тортов, которое Вы сможете приготовить из доступных ингредиентов.

Пример входа 1	Пример выхода 1
3 100 500 2 5 70 1000	2
Пример входа 2	Пример выхода 2
3 100 50 2 5 70 1000	0

РЕШЕНИЕ

циклы

Анализ алгоритма

Переберем ингредиенты. Пусть need содержит необходимое количество текущего ингредиента на торт, have содержит количество этого ингредиента на кухне. Тогда очевидно, что можно приготовить не более have / need тортов, содержащих этот ингредиент. Ищем минимальное значение этого частного среди всех ингредиентов. Оно и будет ответом.

Пример

В первом тесте ответ равен min(500 / 100, 5 / 2, 1000 / 70) = min(5, 2, 14) = 2.

Во втором тесте ответ равен min(50 / 100, 5 / 2, 1000 / 70) = min(0, 2, 14) = 0. Первого ингредиента не хватит даже на один торт.

Реализация алгоритма

Читаем количество ингредиентов n.

scanf("%d", &n);

В переменной res подсчитываем количество тортов, которое можно приготовить из имеющихся ингредиентов.

res = 1000000000;

Перебираем ингредиенты. Ищем минимум среди всех частных have / need.

for (i = 0; i < n; i++)

{

scanf("%d %d", &need, &have);

d = have / need;

if (d < res) res = d;

}

Выводим ответ.

printf("%d\n", res);