A. Supermarket

Codeforces

IDCF919A

Time2000ms

Memory256MB

Difficulty—

brute forcegreedyimplementation

English · Original

Chinese · Translation

Formal · Original

We often go to supermarkets to buy some fruits or vegetables, and on the tag there prints the price for a kilo. But in some supermarkets, when asked how much the items are, the clerk will say that $a$ _yuan_ for $b$ kilos (You don't need to care about what _"yuan"_ is), the same as $a/b$ _yuan_ for a kilo. Now imagine you'd like to buy $m$ kilos of apples. You've asked $n$ supermarkets and got the prices. Find the minimum cost for those apples. You can assume that there are enough apples in all supermarkets. ## Input The first line contains two positive integers $n$ and $m$ ($1 \leq n \leq 5\,000$, $1 \leq m \leq 100$), denoting that there are $n$ supermarkets and you want to buy $m$ kilos of apples. The following $n$ lines describe the information of the supermarkets. Each line contains two positive integers $a, b$ ($1 \leq a, b \leq 100$), denoting that in this supermarket, you are supposed to pay $a$ _yuan_ for $b$ kilos of apples. ## Output The only line, denoting the minimum cost for $m$ kilos of apples. Please make sure that the absolute or relative error between your answer and the correct answer won't exceed $10^{-6}$. Formally, let your answer be $x$, and the jury's answer be $y$. Your answer is considered correct if $\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$. [samples] ## Note In the first sample, you are supposed to buy $5$ kilos of apples in supermarket $3$. The cost is $5/3$ _yuan_. In the second sample, you are supposed to buy $1$ kilo of apples in supermarket $2$. The cost is $98/99$ _yuan_.

我们经常去超市购买水果或蔬菜，标签上会印出每千克的价格。但在一些超市，当被问及商品价格时，店员会说：买 $b$ 千克需要支付 $a$ _元_（你无需关心 _"元"_ 是什么），这等价于每千克 $a \/ b$ _元_。现在假设你想购买 $m$ 千克的苹果。你询问了 $n$ 家超市并获得了它们的价格。请找出购买这些苹果的最低成本。你可以假设所有超市的苹果供应充足。第一行包含两个正整数 $n$ 和 $m$（$1 lt.eq n lt.eq 5 thin 000$，$1 lt.eq m lt.eq 100$），表示有 $n$ 家超市，你想要购买 $m$ 千克的苹果。接下来的 $n$ 行描述了各超市的信息。每行包含两个正整数 $a, b$（$1 lt.eq a, b lt.eq 100$），表示在该超市，你需要支付 $a$ _元_ 来购买 $b$ 千克的苹果。仅输出一行，表示购买 $m$ 千克苹果的最低成本。请确保你的答案与正确答案的绝对误差或相对误差不超过 $10^(-6)$。形式化地，设你的答案为 $x$，标准答案为 $y$。若满足 $frac(| x -y |, max (1 comma | y |)) lt.eq 10^(-6)$，则你的答案被视为正确。在第一个样例中，你应在第 $3$ 家超市购买 $5$ 千克苹果，成本为 $5 \/ 3$ _元_。在第二个样例中，你应在第 $2$ 家超市购买 $1$ 千克苹果，成本为 $98 \/ 99$ _元_。 ## Input 第一行包含两个正整数 $n$ 和 $m$（$1 lt.eq n lt.eq 5 thin 000$，$1 lt.eq m lt.eq 100$），表示有 $n$ 家超市，你想要购买 $m$ 千克的苹果。接下来的 $n$ 行描述了各超市的信息。每行包含两个正整数 $a, b$（$1 lt.eq a, b lt.eq 100$），表示在该超市，你需要支付 $a$ _元_ 来购买 $b$ 千克的苹果。 ## Output 仅输出一行，表示购买 $m$ 千克苹果的最低成本。请确保你的答案与正确答案的绝对误差或相对误差不超过 $10^(-6)$。形式化地，设你的答案为 $x$，标准答案为 $y$。若满足 $frac(| x -y |, max (1 comma | y |)) lt.eq 10^(-6)$，则你的答案被视为正确。 [samples] ## Note 在第一个样例中，你应在第 $3$ 家超市购买 $5$ 千克苹果，成本为 $5 \/ 3$ _元_。在第二个样例中，你应在第 $2$ 家超市购买 $1$ 千克苹果，成本为 $98 \/ 99$ _元_。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the number of supermarkets and the desired quantity of apples (in kilos), respectively. For each supermarket $ i \in \{1, \dots, n\} $, let $ (a_i, b_i) \in \mathbb{Z}^+ \times \mathbb{Z}^+ $ denote the price $ a_i $ yuan for $ b_i $ kilos of apples. **Constraints** 1. $ 1 \le n \le 5000 $ 2. $ 1 \le m \le 100 $ 3. $ 1 \le a_i, b_i \le 100 $ for all $ i \in \{1, \dots, n\} $ **Objective** Compute the minimum cost to buy $ m $ kilos of apples, where the cost per kilo at supermarket $ i $ is $ \frac{a_i}{b_i} $. The minimum total cost is: $$ \min_{i \in \{1, \dots, n\}} \left( \frac{a_i}{b_i} \cdot m \right) $$

Samples

Input #1

Output #1

1.66666667

Input #2

2 1
99 100
98 99

Output #2

0.98989899

API Response (JSON)

{
  "problem": {
    "name": "A. Supermarket",
    "description": {
      "content": "We often go to supermarkets to buy some fruits or vegetables, and on the tag there prints the price for a kilo. But in some supermarkets, when asked how much the items are, the clerk will say that $a$",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF919A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We often go to supermarkets to buy some fruits or vegetables, and on the tag there prints the price for a kilo. But in some supermarkets, when asked how much the items are, the clerk will say that $a$...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "我们经常去超市购买水果或蔬菜，标签上会印出每千克的价格。但在一些超市，当被问及商品价格时，店员会说：买 $b$ 千克需要支付 $a$ _元_（你无需关心 _\"元\"_ 是什么），这等价于每千克 $a \\/ b$ _元_。\n\n现在假设你想购买 $m$ 千克的苹果。你询问了 $n$ 家超市并获得了它们的价格。请找出购买这些苹果的最低成本。\n\n你可以假设所有超市的苹果供应充足。\n\n第一行包含两个正整数 $...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of supermarkets and the desired quantity of apples (in kilos), respectively.  \nFor each supermarket $ i \\in \\{1, \\dots, n\\} $, let $ (...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments