Leftover Recipes

题目描述

你的冰箱里有 $N$ 种食材。我们称它们为食材 $1$，$\dots$，食材 $N$。你有 $Q_i$ 克的食材 $i$。 你可以做两种菜。制作一道菜 A 的一份，需要每种食材 $i$ 的 $A_i$ 克 $(1 \leq i \leq N)$。制作一道菜 B 的一份，需要每种食材 $i$ 的 $B_i$ 克。每种菜你只能做整数份。 仅使用冰箱里的食材，最多可以做多少份菜的总和？

输入格式

输入从标准输入给出，格式如下： $N$ $Q_1$ $Q_2$ $\dots$ $Q_N$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$

输出格式

假设你最多可以做 $S$ 份菜的总和，输出整数 $S$。

2
800 300
100 100
200 10

5

2
800 300
100 0
0 10

38

2
800 300
801 300
800 301

0

10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

222222

提示

$1 \leq N \leq 10$ $1 \leq Q_i \leq 10^6$ $0 \leq A_i \leq 10^6$ 存在某个 $i$ 满足 $A_i \geq 1$。 $0 \leq B_i \leq 10^6$ 存在某个 $i$ 满足 $B_i \geq 1$。 所有输入值均为整数。这个冰箱有食材 $1$ 共 $800$ 克，食材 $2$ 共 $300$ 克。 你可以用 $100$ 克食材 $1$ 和 $100$ 克食材 $2$ 做一道菜 A，用 $200$ 克食材 $1$ 和 $10$ 克食材 $2$ 做一道菜 B。 要做两份菜 A 和三份菜 B，需要 $100 \times 2 + 200 \times 3 = 800$ 克食材 $1$，和 $100 \times 2 + 10 \times 3 = 230$ 克食材 $2$，这两者都不超过冰箱中可用的量。这样可以做总共五份菜，但无法做到六份，所以答案是 $5$。
你可以用 $800$ 克食材 $1$ 做 $8$ 份菜 A，用 $300$ 克食材 $2$ 做 $30$ 份菜 B，总共 $38$ 份。
你无法做任何菜。

标签: AtCoder|abc338C

来源

AtCoder|abc338C