100742: [AtCoder]ABC074 C - Sugar Water

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $300$ points

Problem Statement

Snuke is making sugar water in a beaker. Initially, the beaker is empty. Snuke can perform the following four types of operations any number of times. He may choose not to perform some types of operations.

  • Operation 1: Pour $100A$ grams of water into the beaker.
  • Operation 2: Pour $100B$ grams of water into the beaker.
  • Operation 3: Put $C$ grams of sugar into the beaker.
  • Operation 4: Put $D$ grams of sugar into the beaker.

In our experimental environment, $E$ grams of sugar can dissolve into $100$ grams of water.

Snuke will make sugar water with the highest possible density.

The beaker can contain at most $F$ grams of substances (water and sugar combined), and there must not be any undissolved sugar in the beaker. Find the mass of the sugar water Snuke will make, and the mass of sugar dissolved in it. If there is more than one candidate, any of them will be accepted.

We remind you that the sugar water that contains $a$ grams of water and $b$ grams of sugar is $\frac{100b}{a + b}$ percent. Also, in this problem, pure water that does not contain any sugar is regarded as $0$ percent density sugar water.

Constraints

  • $1 \leq A < B \leq 30$
  • $1 \leq C < D \leq 30$
  • $1 \leq E \leq 100$
  • $100A \leq F \leq 3$ $000$
  • $A$, $B$, $C$, $D$, $E$ and $F$ are all integers.

Inputs

Input is given from Standard Input in the following format:

$A$ $B$ $C$ $D$ $E$ $F$

Outputs

Print two integers separated by a space. The first integer should be the mass of the desired sugar water, and the second should be the mass of the sugar dissolved in it.

Sample Input 1

1 2 10 20 15 200

Sample Output 1

110 10

In this environment, $15$ grams of sugar can dissolve into $100$ grams of water, and the beaker can contain at most $200$ grams of substances.

We can make $110$ grams of sugar water by performing Operation 1 once and Operation 3 once. It is not possible to make sugar water with higher density. For example, the following sequences of operations are infeasible:

  • If we perform Operation 1 once and Operation 4 once, there will be undissolved sugar in the beaker.
  • If we perform Operation 2 once and Operation 3 three times, the mass of substances in the beaker will exceed $200$ grams.

Sample Input 2

1 2 1 2 100 1000

Sample Output 2

200 100

There are other acceptable outputs, such as:

400 200

However, the output below is not acceptable:

300 150

This is because, in order to make $300$ grams of sugar water containing $150$ grams of sugar, we need to pour exactly $150$ grams of water into the beaker, which is impossible.

Sample Input 3

17 19 22 26 55 2802

Sample Output 3

2634 934

Input

题意翻译

废柴君正在烧杯中配置糖水。最初，烧杯是空的。废柴君可以多次执行以下四种类型的操作,每种操作不是必须的。 - 操作1：将 $100 \times A$ 克水倒入烧杯中。 - 操作2：将 $100 \times B$ 克水倒入烧杯中。 - 操作3：将 $C$ 克糖放入烧杯中。 - 操作4：将 $D$ 克糖放入烧杯中。 在我们的实验环境中，至多 $E$ 克糖可溶解于 $100$ 克水。 $a$ 克水，$b$ 克糖的糖水记作百分之 $ \dfrac{100b}{a+b}$。 废柴君想用现有材料配置具有百分率最高的糖水。 烧杯最多可容纳 $F$ 克糖水，并且烧杯中不能有任何不溶解的糖。 输入 一行按顺序给出 $A \sim F$ 输出 输出废柴君将配置的糖水的质量，以及溶解在其中的糖的质量。如果有多种答案，任意输出一个即可。 $1 \leqslant A < B \leqslant 30$ $1 \leqslant C < D \leqslant 30$ $1 \leqslant E \leqslant 100$ $100A \leqslant F \leqslant 3000$ 输入数据均为整数。 样例 1 解释 此时，$15$ 克糖可溶解于 $100$ 克水，烧杯最多可容纳 $200$ 克糖水。 我们可以配置 $110$ 克糖水，即执行操作 $1$ 和操作 $3$。但我们无法制造更优的糖水。例如，以下操作顺序就是不可行的： 如果我们进行一次操作 $1$ 和一次操作 $4$，则烧杯中将会有未溶解的糖。 如果我们执行操作 $2$ 一次和操作 $3$ 三次，烧杯中的糖水质量将超过 $200$ 克。 样例2解释 $200 ~ 100$ $400 ~ 200$ 也是正确的。 $300 ~ 150$ 是错误的。 这是因为，为了配置 $300$ 克 $50\%$ 的糖水我们得准确倒入 $150$ 克糖，这当然是不可能的。 Translated by @yyhhenry

Source/Category

加入题单

算法标签：