C. Apple Shops

Codeforces

IDCF10203C

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Ayoub wants to buy k boxes of apples, and there are n shops where he can buy apples from. The price of one box of apples in the ith shop equals to pi. It is obvious that Ayoub should go to the shop with the minimal price per box. When the government saw everyone buying from the same shop, they made a special rule so that people will buy from different shops. The cost of buying the jth apple box from the ith shop is equal to pi + (j - 1) × x For example, if the price of one box from a specific shop is 5 and x = 3. If you want to buy 3 boxes, you will pay 5 money on the first box and 5 + x on the second box, and 5 + 2 × x on the third box, in total paying 5 + 8 + 11 = 24. Now you should tell Ayoub how many boxes he should buy from every shop so that the total money he will pay is minimized. First line contains 3 integers n k x (1 ≤ n ≤ 105) (1 ≤ k, x ≤ 109) which are the number of shops and the number of box Ayoub wants to buy and the amount of money you should pay more after buying a box from a specific shop. Second line contains n integers, the ith one is pi (1 ≤ pi ≤ 109) which is the price of a box of apples from the ith shop. You should print n integers, the ith one should be the number of box Ayoub should buy from the ith shop. Make sure that the amount of money will be payed will be minimized as possible. If there are more than one answer you can print any of them. In the second sample Ayoub will pay 1 and 4 to the first shop and will pay 2 to the third shop and will pay 3 to the fourth shop, in total he will buy 10 money. ## Input First line contains 3 integers n k x (1 ≤ n ≤ 105) (1 ≤ k, x ≤ 109) which are the number of shops and the number of box Ayoub wants to buy and the amount of money you should pay more after buying a box from a specific shop.Second line contains n integers, the ith one is pi (1 ≤ pi ≤ 109) which is the price of a box of apples from the ith shop. ## Output You should print n integers, the ith one should be the number of box Ayoub should buy from the ith shop.Make sure that the amount of money will be payed will be minimized as possible.If there are more than one answer you can print any of them. [samples] ## Note In the second sample Ayoub will pay 1 and 4 to the first shop and will pay 2 to the third shop and will pay 3 to the fourth shop, in total he will buy 10 money.

**Definitions** Let $ n, k, x \in \mathbb{Z}^+ $: number of shops, total boxes to buy, and incremental cost per additional box from the same shop. Let $ P = (p_1, p_2, \dots, p_n) \in \mathbb{Z}^n $: price per box at each shop. Let $ a_i \in \mathbb{Z}_{\geq 0} $: number of boxes bought from shop $ i $, for $ i = 1, \dots, n $. **Constraints** 1. $ \sum_{i=1}^n a_i = k $ 2. $ a_i \geq 0 $ for all $ i \in \{1, \dots, n\} $ **Objective** Minimize total cost: $$ \sum_{i=1}^n \sum_{j=1}^{a_i} \left( p_i + (j - 1) \cdot x \right) = \sum_{i=1}^n \left( a_i p_i + x \cdot \frac{a_i(a_i - 1)}{2} \right) $$

API Response (JSON)

{
  "problem": {
    "name": "C. Apple Shops",
    "description": {
      "content": "Ayoub wants to buy k boxes of apples, and there are n shops where he can buy apples from. The price of one box of apples in the ith shop equals to pi. It is obvious that Ayoub should go to the shop w",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10203C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ayoub wants to buy k boxes of apples, and there are n shops where he can buy apples from. The price of one box of apples in the ith shop equals to pi.\n\nIt is obvious that Ayoub should go to the shop w...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k, x \\in \\mathbb{Z}^+ $: number of shops, total boxes to buy, and incremental cost per additional box from the same shop.  \nLet $ P = (p_1, p_2, \\dots, p_n) \\in \\mathbb{Z}^n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments