C. Tea Party

Codeforces

IDCF808C

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsgreedysortings

English · Original

Chinese · Translation

Formal · Original

Polycarp invited all his friends to the tea party to celebrate the holiday. He has _n_ cups, one for each of his _n_ friends, with volumes _a_1, _a_2, ..., _a__n_. His teapot stores _w_ milliliters of tea (_w_ ≤ _a_1 + _a_2 + ... + _a__n_). Polycarp wants to pour tea in cups in such a way that: * Every cup will contain tea for at least half of its volume * Every cup will contain integer number of milliliters of tea * All the tea from the teapot will be poured into cups * All friends will be _satisfied_. Friend with cup _i_ won't be _satisfied_, if there exists such cup _j_ that cup _i_ contains less tea than cup _j_ but _a__i_ > _a__j_. For each cup output how many milliliters of tea should be poured in it. If it's impossible to pour all the tea and satisfy all conditions then output _\-1_. ## Input The first line contains two integer numbers _n_ and _w_ (1 ≤ _n_ ≤ 100, ). The second line contains _n_ numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 100). ## Output Output how many milliliters of tea every cup should contain. If there are multiple answers, print any of them. If it's impossible to pour all the tea and satisfy all conditions then output _\-1_. [samples] ## Note In the third example you should pour to the first cup at least 5 milliliters, to the second one at least 4, to the third one at least 5. It sums up to 14, which is greater than 10 milliliters available.

Polycarp 邀请了他所有朋友来参加茶会庆祝节日。他有 #cf_span[n] 个杯子，每个朋友一个，容量分别为 #cf_span[a1, a2, ..., an]。他的茶壶装有 #cf_span[w] 毫升的茶（#cf_span[w ≤ a1 + a2 + ... + an]）。Polycarp 希望以如下方式将茶倒入杯子中：如果存在某个杯子 #cf_span[j]，使得杯子 #cf_span[i] 中的茶量少于杯子 #cf_span[j]，但 #cf_span[ai > aj]，则杯子 #cf_span[i] 的主人将不被满足。请为每个杯子输出应倒入的茶量（单位：毫升）。如果无法倒完所有茶且满足所有条件，则输出 _-1_。第一行包含两个整数 #cf_span[n] 和 #cf_span[w]（#cf_span[1 ≤ n ≤ 100]）。第二行包含 #cf_span[n] 个数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 100]）。请输出每个杯子应包含的茶量（单位：毫升）。如果有多种答案，输出任意一种即可。如果无法倒完所有茶且满足所有条件，则输出 _-1_。在第三个例子中，第一个杯子至少需要倒 5 毫升，第二个杯子至少需要倒 4 毫升，第三个杯子至少需要倒 5 毫升。总和为 14，超过了可用的 10 毫升。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[w]（#cf_span[1 ≤ n ≤ 100]）。第二行包含 #cf_span[n] 个数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 100]）。 ## Output 请输出每个杯子应包含的茶量（单位：毫升）。如果有多种答案，输出任意一种即可。如果无法倒完所有茶且满足所有条件，则输出 _-1_。 [samples] ## Note 在第三个例子中，第一个杯子至少需要倒 5 毫升，第二个杯子至少需要倒 4 毫升，第三个杯子至少需要倒 5 毫升。总和为 14，超过了可用的 10 毫升。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of cups. Let $ w \in \mathbb{Z}^+ $ be the total tea volume available. Let $ A = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $ be the capacities of the cups, with $ a_i \geq 1 $. Let $ x = (x_1, x_2, \dots, x_n) \in \mathbb{R}^n $ be the tea volume poured into each cup, with $ 0 \leq x_i \leq a_i $. **Constraints** 1. $ \sum_{i=1}^n x_i = w $ 2. For all $ i, j \in \{1, \dots, n\} $: If $ x_i < x_j $, then $ a_i \leq a_j $ (Equivalently: $ a_i > a_j \Rightarrow x_i \geq x_j $) **Objective** Find any $ x \in \mathbb{R}^n $ satisfying the above constraints, or output $-1$ if no such $ x $ exists.

Samples

Input #1

2 10
8 7

Output #1

6 4

Input #2

4 4
1 1 1 1

Output #2

1 1 1 1

Input #3

3 10
9 8 10

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "C. Tea Party",
    "description": {
      "content": "Polycarp invited all his friends to the tea party to celebrate the holiday. He has _n_ cups, one for each of his _n_ friends, with volumes _a_1, _a_2, ..., _a__n_. His teapot stores _w_ milliliters of",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF808C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp invited all his friends to the tea party to celebrate the holiday. He has _n_ cups, one for each of his _n_ friends, with volumes _a_1, _a_2, ..., _a__n_. His teapot stores _w_ milliliters of...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 邀请了他所有朋友来参加茶会庆祝节日。他有 #cf_span[n] 个杯子，每个朋友一个，容量分别为 #cf_span[a1, a2, ..., an]。他的茶壶装有 #cf_span[w] 毫升的茶（#cf_span[w ≤ a1 + a2 + ... + an]）。Polycarp 希望以如下方式将茶倒入杯子中：\n\n如果存在某个杯子 #cf_span[j]，使得杯子 #cf_s...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of cups.  \nLet $ w \\in \\mathbb{Z}^+ $ be the total tea volume available.  \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $ be the capacit...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments