C. Bamboo Partition

Codeforces

IDCF830C

Time2000ms

Memory512MB

Difficulty—

brute forcedata structuresimplementationmathnumber theorysortingstwo pointers

English · Original

Chinese · Translation

Formal · Original

Vladimir wants to modernize partitions in his office. To make the office more comfortable he decided to remove a partition and plant several bamboos in a row. He thinks it would be nice if there are _n_ bamboos in a row, and the _i_\-th from the left is _a__i_ meters high. Vladimir has just planted _n_ bamboos in a row, each of which has height 0 meters right now, but they grow 1 meter each day. In order to make the partition nice Vladimir can cut each bamboo once at any height (no greater that the height of the bamboo), and then the bamboo will stop growing. Vladimir wants to check the bamboos each _d_ days (i.e. _d_ days after he planted, then after 2_d_ days and so on), and cut the bamboos that reached the required height. Vladimir wants the total length of bamboo parts he will cut off to be no greater than _k_ meters. What is the maximum value _d_ he can choose so that he can achieve what he wants without cutting off more than _k_ meters of bamboo? ## Input The first line contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 100, 1 ≤ _k_ ≤ 1011) — the number of bamboos and the maximum total length of cut parts, in meters. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the required heights of bamboos, in meters. ## Output Print a single integer — the maximum value of _d_ such that Vladimir can reach his goal. [samples] ## Note In the first example Vladimir can check bamboos each 3 days. Then he will cut the first and the second bamboos after 3 days, and the third bamboo after 6 days. The total length of cut parts is 2 + 0 + 1 = 3 meters.

Vladimir 想要现代化他办公室的隔断。为了使办公室更舒适，他决定移除一个隔断，并在一行中种植若干竹子。他认为，如果一行中有 #cf_span[n] 根竹子，且从左数第 #cf_span[i] 根高度为 #cf_span[ai] 米，那会很好。 Vladimir 刚刚在一行中种植了 #cf_span[n] 根竹子，每根当前高度均为 #cf_span[0] 米，但它们每天长高 #cf_span[1] 米。为了使隔断美观，Vladimir 可以在任意时刻（不超过竹子当前高度）对每根竹子进行一次砍伐，之后该竹子将停止生长。 Vladimir 想每隔 #cf_span[d] 天检查一次竹子（即种植后第 #cf_span[d] 天、第 #cf_span[2d] 天，依此类推），并砍伐那些达到所需高度的竹子。Vladimir 希望他砍下的竹子部分的总长度不超过 #cf_span[k] 米。请问，他能选择的最大 #cf_span[d] 值是多少，使得他能在不砍下超过 #cf_span[k] 米竹子的前提下实现目标？第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100]，#cf_span[1 ≤ k ≤ 1011]）——竹子的数量和允许砍下的最大总长度（单位：米）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）——每根竹子所需的最终高度（单位：米）。请输出一个整数——满足 Vladimir 目标的最大 #cf_span[d] 值。在第一个例子中，Vladimir 可以每隔 #cf_span[3] 天检查一次竹子。他将在第 #cf_span[3] 天砍下第一根和第二根竹子，在第 #cf_span[6] 天砍下第三根竹子。被砍下的部分总长度为 #cf_span[2 + 0 + 1 = 3] 米。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100]，#cf_span[1 ≤ k ≤ 1011]）——竹子的数量和允许砍下的最大总长度（单位：米）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）——每根竹子所需的最终高度（单位：米）。 ## Output 请输出一个整数——满足 Vladimir 目标的最大 #cf_span[d] 值。 [samples] ## Note 在第一个例子中，Vladimir 可以每隔 #cf_span[3] 天检查一次竹子。他将在第 #cf_span[3] 天砍下第一根和第二根竹子，在第 #cf_span[6] 天砍下第三根竹子。被砍下的部分总长度为 #cf_span[2 + 0 + 1 = 3] 米。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of bamboos. Let $ k \in \mathbb{Z}^+ $ be the maximum allowable total cut-off length. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of required heights, where $ a_i \in \mathbb{Z}^+ $. Let $ d \in \mathbb{Z}^+ $ be the check-and-cut interval (in days). Each bamboo grows at 1 meter per day. At time $ t = m \cdot d $ (for $ m \in \mathbb{Z}^+ $), the height of bamboo $ i $ is $ m \cdot d $. Vladimir cuts bamboo $ i $ at the smallest multiple of $ d $ such that $ m_i \cdot d \geq a_i $, i.e., $$ m_i = \left\lceil \frac{a_i}{d} \right\rceil, \quad \text{cutting time} = m_i \cdot d. $$ The cut-off length for bamboo $ i $ is: $$ c_i = m_i \cdot d - a_i = d \cdot \left\lceil \frac{a_i}{d} \right\rceil - a_i. $$ **Constraints** 1. $ 1 \leq n \leq 100 $ 2. $ 1 \leq k \leq 10^{11} $ 3. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ 4. Total cut-off length: $ \sum_{i=1}^n \left( d \cdot \left\lceil \frac{a_i}{d} \right\rceil - a_i \right) \leq k $ **Objective** Find the maximum $ d \in \mathbb{Z}^+ $ such that: $$ \sum_{i=1}^n \left( d \cdot \left\lceil \frac{a_i}{d} \right\rceil - a_i \right) \leq k $$

Samples

Input #1

3 4
1 3 5

Output #1

Input #2

3 40
10 30 50

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Bamboo Partition",
    "description": {
      "content": "Vladimir wants to modernize partitions in his office. To make the office more comfortable he decided to remove a partition and plant several bamboos in a row. He thinks it would be nice if there are _",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF830C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vladimir wants to modernize partitions in his office. To make the office more comfortable he decided to remove a partition and plant several bamboos in a row. He thinks it would be nice if there are _...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Vladimir 想要现代化他办公室的隔断。为了使办公室更舒适，他决定移除一个隔断，并在一行中种植若干竹子。他认为，如果一行中有 #cf_span[n] 根竹子，且从左数第 #cf_span[i] 根高度为 #cf_span[ai] 米，那会很好。\n\nVladimir 刚刚在一行中种植了 #cf_span[n] 根竹子，每根当前高度均为 #cf_span[0] 米，但它们每天长高 #cf_span...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of bamboos.  \nLet $ k \\in \\mathbb{Z}^+ $ be the maximum allowable total cut-off length.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments