A. Garden

Codeforces

IDCF915A

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Luba thinks about watering her garden. The garden can be represented as a segment of length _k_. Luba has got _n_ buckets, the _i_\-th bucket allows her to water some continuous subsegment of garden of length **exactly** _a__i_ each hour. **Luba can't water any parts of the garden that were already watered, also she can't water the ground outside the garden**. Luba has to choose **one** of the buckets in order to water the garden as fast as possible (as mentioned above, each hour she will water some continuous subsegment of length _a__i_ if she chooses the _i_\-th bucket). Help her to determine the minimum number of hours she has to spend watering the garden. It is guaranteed that Luba can always choose a bucket so it is possible water the garden. See the examples for better understanding. ## Input The first line of input contains two integer numbers _n_ and _k_ (1 ≤ _n_, _k_ ≤ 100) — the number of buckets and the length of the garden, respectively. The second line of input contains _n_ integer numbers _a__i_ (1 ≤ _a__i_ ≤ 100) — the length of the segment that can be watered by the _i_\-th bucket in one hour. It is guaranteed that there is at least one bucket such that it is possible to water the garden in integer number of hours using only this bucket. ## Output Print one integer number — the minimum number of hours required to water the garden. [samples] ## Note In the first test the best option is to choose the bucket that allows to water the segment of length 3. We can't choose the bucket that allows to water the segment of length 5 because then we can't water the whole garden. In the second test we can choose only the bucket that allows us to water the segment of length 1.

Luba 正在考虑给她的花园浇水。花园可以表示为一个长度为 $k$ 的线段。Luba 有 $n$ 个水桶，第 $i$ 个水桶每小时可以浇灌花园中一个长度 *恰好* 为 $a_i$ 的连续子段。*Luba 不能浇灌已经浇过水的部分，也不能浇灌花园以外的区域*。 Luba 必须 *选择其中一个* 水桶来尽可能快地浇灌整个花园（如上所述，如果她选择第 $i$ 个水桶，每小时她将浇灌一个长度为 $a_i$ 的连续子段）。请帮助她确定浇灌花园所需的最少小时数。保证 Luba 总可以选择一个水桶，使得用该水桶整数小时数浇灌整个花园是可行的。请参考示例以获得更清晰的理解。输入的第一行包含两个整数 $n$ 和 $k$（$1 ≤ n, k ≤ 100$）——水桶的数量和花园的长度。第二行包含 $n$ 个整数 $a_i$（$1 ≤ a_i ≤ 100$）——第 $i$ 个水桶每小时可以浇灌的线段长度。保证至少存在一个水桶，使得仅使用该水桶即可用整数小时数浇灌整个花园。请输出一个整数——浇灌花园所需的最少小时数。在第一个测试用例中，最佳选择是使用能浇灌长度为 $3$ 的线段的水桶。我们不能选择能浇灌长度为 $5$ 的线段的水桶，因为那样无法浇灌整个花园。在第二个测试用例中，我们只能选择能浇灌长度为 $1$ 的线段的水桶。 ## Input 输入的第一行包含两个整数 $n$ 和 $k$（$1 ≤ n, k ≤ 100$）——水桶的数量和花园的长度。第二行包含 $n$ 个整数 $a_i$（$1 ≤ a_i ≤ 100$）——第 $i$ 个水桶每小时可以浇灌的线段长度。保证至少存在一个水桶，使得仅使用该水桶即可用整数小时数浇灌整个花园。 ## Output 请输出一个整数——浇灌花园所需的最少小时数。 [samples] ## Note 在第一个测试用例中，最佳选择是使用能浇灌长度为 $3$ 的线段的水桶。我们不能选择能浇灌长度为 $5$ 的线段的水桶，因为那样无法浇灌整个花园。在第二个测试用例中，我们只能选择能浇灌长度为 $1$ 的线段的水桶。

Given: - A garden of length $ k $. - $ n $ buckets, where the $ i $-th bucket can water a continuous segment of exact length $ a_i $ per hour. - Constraints: - Only one bucket may be chosen. - Watered segments must be entirely within the garden. - No overlapping or watering outside the garden. - Goal: Minimize the number of hours to water the entire garden. Formal problem: Let $ a_i \in \mathbb{Z}^+ $ for $ i = 1, 2, \dots, n $, and $ k \in \mathbb{Z}^+ $. Find: $$ \min_{\substack{1 \leq i \leq n \\ a_i \mid k}} \left( \frac{k}{a_i} \right) $$ That is, minimize $ \frac{k}{a_i} $ over all buckets $ i $ such that $ a_i $ divides $ k $ (since non-integer hours are not allowed, and the entire garden must be covered exactly by integer-length non-overlapping segments of size $ a_i $). **Note**: The guarantee that "it is possible to water the garden" ensures that at least one $ a_i $ divides $ k $.

Samples

Input #1

3 6
2 3 5

Output #1

Input #2

6 7
1 2 3 4 5 6

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Garden",
    "description": {
      "content": "Luba thinks about watering her garden. The garden can be represented as a segment of length _k_. Luba has got _n_ buckets, the _i_\\-th bucket allows her to water some continuous subsegment of garden o",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF915A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Luba thinks about watering her garden. The garden can be represented as a segment of length _k_. Luba has got _n_ buckets, the _i_\\-th bucket allows her to water some continuous subsegment of garden o...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Luba 正在考虑给她的花园浇水。花园可以表示为一个长度为 $k$ 的线段。Luba 有 $n$ 个水桶，第 $i$ 个水桶每小时可以浇灌花园中一个长度 *恰好* 为 $a_i$ 的连续子段。*Luba 不能浇灌已经浇过水的部分，也不能浇灌花园以外的区域*。\n\nLuba 必须 *选择其中一个* 水桶来尽可能快地浇灌整个花园（如上所述，如果她选择第 $i$ 个水桶，每小时她将浇灌一个长度为 $a_i...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given:\n- A garden of length $ k $.\n- $ n $ buckets, where the $ i $-th bucket can water a continuous segment of exact length $ a_i $ per hour.\n- Constraints:\n  - Only one bucket may be chosen.\n  - Wat...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments