Score: $300$ points

问题描述

你的冰箱里有 $N$ 种食材。我们称它们为食材 $1$, $\dots$, 食材 $N$。你拥有 $Q_i$ 克的第 $i$ 种食材。

你可以制作两种类型的菜肴。制作一份 A 类菜肴，你需要每种食材 $i$ $(1 \leq i \leq N)$ 的 $A_i$ 克。制作一份 B 类菜肴，你需要每种食材 $i$ 的 $B_i$ 克。你只能制作整数份的每种类型菜肴。

仅使用冰箱中的食材，你能做出的最大总份数是多少？

约束条件

• $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$。
• 所有输入值都是整数。

输入

输入格式如下：

$N$

$Q_1$ $Q_2$ $\dots$ $Q_N$

$A_1$ $A_2$ $\dots$ $A_N$

$B_1$ $B_2$ $\dots$ $B_N$

输出

假设你最多可以制作 $S$ 份菜肴，请输出整数 $S$。

示例输入 1

2
800 300
100 100
200 10

示例输出 1

5

这个冰箱有 $800$ 克成分 $1$ 和 $300$ 克成分 $2$。

你可以用 $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$。

示例输入 2

2
800 300
100 0
0 10

示例输出 2

38

你可以用 $800$ 克成分 $1$ 制作 $8$ 份 A 菜，以及用 $300$ 克成分 $2$ 制作 $30$ 份 B 菜，总共 $38$ 份。

示例输入 3

2
800 300
801 300
800 301

示例输出 3

0

你不能制作任何菜肴。

示例输入 4

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

示例输出 4

222222

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Your refrigerator has $N$ kinds of ingredients. Let us call them ingredient $1$, $\dots$, ingredient $N$. You have $Q_i$ grams of ingredient $i$.

You can make two types of dishes. To make one serving of dish A, you need $A_i$ grams of each ingredient $i$ $(1 \leq i \leq N)$. To make one serving of dish B, you need $B_i$ grams of each ingredient $i$. You can only make an integer number of servings of each type of dish.

Using only the ingredients in the refrigerator, what is the maximum total number of servings of dishes you can make?

Constraints

• $1 \leq N \leq 10$
• $1 \leq Q_i \leq 10^6$
• $0 \leq A_i \leq 10^6$
• There is an $i$ such that $A_i \geq 1$.
• $0 \leq B_i \leq 10^6$
• There is an $i$ such that $B_i \geq 1$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$

$Q_1$ $Q_2$ $\dots$ $Q_N$

$A_1$ $A_2$ $\dots$ $A_N$

$B_1$ $B_2$ $\dots$ $B_N$

Output

Assuming that you can make a maximum total of $S$ servings of dishes, print the integer $S$.

Sample Input 1

2
800 300
100 100
200 10

Sample Output 1

5

This refrigerator has $800$ grams of ingredient $1$ and $300$ grams of ingredient $2$.

You can make one serving of dish A with $100$ grams of ingredient $1$ and $100$ grams of ingredient $2$, and one serving of dish B with $200$ grams of ingredient $1$ and $10$ grams of ingredient $2$.

To make two servings of dish A and three servings of dish B, you need $100 \times 2 + 200 \times 3 = 800$ grams of ingredient $1$, and $100 \times 2 + 10 \times 3 = 230$ grams of ingredient $2$, neither of which exceeds the amount available in the refrigerator. In this way, you can make a total of five servings of dishes, but there is no way to make six, so the answer is $5$.

Sample Input 2

2
800 300
100 0
0 10

Sample Output 2

38

You can make $8$ servings of dish A with $800$ grams of ingredient $1$, and $30$ servings of dish B with $300$ grams of ingredient $2$, for a total of $38$ servings.

Sample Input 3

2
800 300
801 300
800 301

Sample Output 3

0

You cannot make any dishes.

Sample Input 4

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

Sample Output 4

222222

update @ 2024/3/10 01:29:07