A. Anastasia and pebbles

Codeforces

IDCF789A

Time1000ms

Memory256MB

Difficulty—

implementationmath

English · Original

Chinese · Translation

Formal · Original

Anastasia loves going for a walk in Central Uzhlyandian Park. But she became uninterested in simple walking, so she began to collect Uzhlyandian pebbles. At first, she decided to collect all the pebbles she could find in the park. She has only **two pockets**. She can put at most _k_ pebbles in each pocket at the same time. There are _n_ different pebble types in the park, and there are _w__i_ pebbles of the _i_\-th type. Anastasia is very responsible, so she never mixes pebbles of different types in same pocket. However, she can put different kinds of pebbles in different pockets at the same time. Unfortunately, she can't spend all her time collecting pebbles, so she can collect pebbles from the park only once a day. Help her to find the minimum number of days needed to collect all the pebbles of Uzhlyandian Central Park, taking into consideration that Anastasia can't place pebbles of different types in same pocket. ## Input The first line contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 105, 1 ≤ _k_ ≤ 109) — the number of different pebble types and number of pebbles Anastasia can place in one pocket. The second line contains _n_ integers _w_1, _w_2, ..., _w__n_ (1 ≤ _w__i_ ≤ 104) — number of pebbles of each type. ## Output The only line of output contains one integer — the minimum number of days Anastasia needs to collect all the pebbles. [samples] ## Note In the first sample case, Anastasia can collect all pebbles of the first type on the first day, of second type — on the second day, and of third type — on the third day. Optimal sequence of actions in the second sample case: * In the first day Anastasia collects 8 pebbles of the third type. * In the second day she collects 8 pebbles of the fourth type. * In the third day she collects 3 pebbles of the first type and 1 pebble of the fourth type. * In the fourth day she collects 7 pebbles of the fifth type. * In the fifth day she collects 1 pebble of the second type.

Anastasia 喜欢在中央乌日兰迪亚公园散步。但她对单纯的散步失去了兴趣，于是开始收集乌日兰迪亚鹅卵石。起初，她决定收集公园里能找到的所有鹅卵石。她只有 *两个口袋*。每个口袋同时最多能装 #cf_span[k] 枚鹅卵石。公园中有 #cf_span[n] 种不同类型的鹅卵石，第 #cf_span[i] 种类型有 #cf_span[wi] 枚鹅卵石。Anastasia 非常负责，因此她从不将不同类型的鹅卵石混在同一口袋中。然而，她可以在同一时间将不同类型的鹅卵石分别放入两个口袋。不幸的是，她不能把所有时间都花在收集鹅卵石上，因此她每天只能去公园收集一次鹅卵石。请帮助她找出收集中央乌日兰迪亚公园所有鹅卵石所需的最少天数，前提是 Anastasia 不能将不同类型的鹅卵石放在同一个口袋中。第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 105], #cf_span[1 ≤ k ≤ 109]) —— 不同鹅卵石类型的数量以及 Anastasia 在一个口袋中能放置的鹅卵石数量。第二行包含 #cf_span[n] 个整数 #cf_span[w1, w2, ..., wn] (#cf_span[1 ≤ wi ≤ 104]) —— 每种类型的鹅卵石数量。输出仅一行，包含一个整数 —— Anastasia 收集所有鹅卵石所需的最少天数。在第一个样例中，Anastasia 可以在第一天收集第一种类型的全部鹅卵石，第二天收集第二种类型的，第三天收集第三种类型的。第二个样例中的最优操作序列： ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 105], #cf_span[1 ≤ k ≤ 109]) —— 不同鹅卵石类型的数量以及 Anastasia 在一个口袋中能放置的鹅卵石数量。第二行包含 #cf_span[n] 个整数 #cf_span[w1, w2, ..., wn] (#cf_span[1 ≤ wi ≤ 104]) —— 每种类型的鹅卵石数量。 ## Output 输出仅一行，包含一个整数 —— Anastasia 收集所有鹅卵石所需的最少天数。 [samples] ## Note 在第一个样例中，Anastasia 可以在第一天收集第一种类型的全部鹅卵石，第二天收集第二种类型的，第三天收集第三种类型的。第二个样例中的最优操作序列：第一天，Anastasia 收集第三种类型的 #cf_span[8] 枚鹅卵石。第二天，她收集第四种类型的 #cf_span[8] 枚鹅卵石。第三天，她收集第一种类型的 #cf_span[3] 枚鹅卵石和第四种类型的 #cf_span[1] 枚鹅卵石。第四天，她收集第五种类型的 #cf_span[7] 枚鹅卵石。第五天，她收集第二种类型的 #cf_span[1] 枚鹅卵石。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of pebble types. Let $ k \in \mathbb{Z}^+ $ be the maximum number of pebbles per pocket. Let $ W = (w_1, w_2, \dots, w_n) $ be a sequence of positive integers, where $ w_i $ is the number of pebbles of type $ i $. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 1 \leq k \leq 10^9 $ 3. $ 1 \leq w_i \leq 10^4 $ for all $ i \in \{1, \dots, n\} $ **Objective** For each pebble type $ i $, the number of pockets required to collect all $ w_i $ pebbles is $ \left\lceil \frac{w_i}{k} \right\rceil $. Since Anastasia has two pockets per day and cannot mix types in a pocket, the minimum number of days needed is: $$ \left\lceil \frac{1}{2} \sum_{i=1}^{n} \left\lceil \frac{w_i}{k} \right\rceil \right\rceil $$

Samples

Input #1

3 2
2 3 4

Output #1

Input #2

5 4
3 1 8 9 7

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Anastasia and pebbles",
    "description": {
      "content": "Anastasia loves going for a walk in Central Uzhlyandian Park. But she became uninterested in simple walking, so she began to collect Uzhlyandian pebbles. At first, she decided to collect all the pebbl",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF789A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Anastasia loves going for a walk in Central Uzhlyandian Park. But she became uninterested in simple walking, so she began to collect Uzhlyandian pebbles. At first, she decided to collect all the pebbl...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Anastasia 喜欢在中央乌日兰迪亚公园散步。但她对单纯的散步失去了兴趣，于是开始收集乌日兰迪亚鹅卵石。起初，她决定收集公园里能找到的所有鹅卵石。\n\n她只有 *两个口袋*。每个口袋同时最多能装 #cf_span[k] 枚鹅卵石。公园中有 #cf_span[n] 种不同类型的鹅卵石，第 #cf_span[i] 种类型有 #cf_span[wi] 枚鹅卵石。Anastasia 非常负责，因此她从不...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of pebble types.  \nLet $ k \\in \\mathbb{Z}^+ $ be the maximum number of pebbles per pocket.  \nLet $ W = (w_1, w_2, \\dots, w_n) $ be a sequence...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments