B. End of Exams

Codeforces

IDCF93B

Time1000ms

Memory256MB

Difficulty—

greedy

English · Original

Chinese · Translation

Formal · Original

Students love to celebrate their holidays. Especially if the holiday is the day of the end of exams! Despite the fact that Igor K., unlike his groupmates, failed to pass a programming test, he decided to invite them to go to a cafe so that each of them could drink a bottle of... fresh cow milk. Having entered the cafe, the _m_ friends found _n_ different kinds of milk on the menu, that's why they ordered _n_ bottles — one bottle of each kind. We know that the volume of milk in each bottle equals _w_. When the bottles were brought in, they decided to pour all the milk evenly among the _m_ cups, so that each got a cup. As a punishment for not passing the test Igor was appointed the person to pour the milk. He protested that he was afraid to mix something up and suggested to distribute the drink so that the milk from each bottle was in no more than two different cups. His friends agreed but they suddenly faced the following problem — and what is actually the way to do it? Help them and write the program that will help to distribute the milk among the cups and drink it as quickly as possible! Note that due to Igor K.'s perfectly accurate eye and unswerving hands, he can pour any fractional amount of milk from any bottle to any cup. ## Input The only input data file contains three integers _n_, _w_ and _m_ (1 ≤ _n_ ≤ 50, 100 ≤ _w_ ≤ 1000, 2 ≤ _m_ ≤ 50), where _n_ stands for the number of ordered bottles, _w_ stands for the volume of each of them and _m_ stands for the number of friends in the company. ## Output Print on the first line "_YES_" if it is possible to pour the milk so that the milk from each bottle was in no more than two different cups. If there's no solution, print "_NO_". If there is a solution, then print _m_ more lines, where the _i_\-th of them describes the content of the _i_\-th student's cup. The line should consist of one or more pairs that would look like "_b_ _v_". Each such pair means that _v_ (_v_ > 0) units of milk were poured into the _i_\-th cup from bottle _b_ (1 ≤ _b_ ≤ _n_). All numbers _b_ on each line should be different. If there are several variants to solve the problem, print any of them. Print the real numbers with no less than 6 digits after the decimal point. [samples]

学生喜欢庆祝他们的假期，尤其是期末考试结束的日子！尽管 Igor K. 与他的同学们不同，未能通过编程测试，他还是决定邀请他们去咖啡馆，让每个人都能喝一瓶……新鲜的牛奶。进入咖啡馆后，这 #cf_span[m] 位朋友发现菜单上有 #cf_span[n] 种不同的牛奶，于是他们点了 #cf_span[n] 瓶——每种一瓶。我们知道每瓶牛奶的体积为 #cf_span[w]。当瓶子被端上来后，他们决定将所有牛奶均匀地倒入 #cf_span[m] 个杯子中，每人一个杯子。作为未能通过测试的惩罚，Igor 被指定为倒牛奶的人。他担心会搞混，提议将饮料分配得使得每瓶牛奶最多只进入两个不同的杯子。他的朋友们同意了，但他们突然面临一个问题——究竟该如何操作？请帮助他们，编写一个程序，帮助分配牛奶，以便尽快喝掉！注意：由于 Igor K. 的视力极其精准且双手稳如磐石，他可以从任意瓶子向任意杯子倒入任意小数体积的牛奶。输入文件仅包含三个整数 #cf_span[n], #cf_span[w] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 50], #cf_span[100 ≤ w ≤ 1000], #cf_span[2 ≤ m ≤ 50]），其中 #cf_span[n] 表示订购的瓶子数，#cf_span[w] 表示每瓶的体积，#cf_span[m] 表示朋友的人数。如果可以将牛奶倒入杯子，使得每瓶牛奶最多出现在两个不同的杯子中，则在第一行输出 "_YES_"；若无解，则输出 "_NO_"。若有解，则再输出 #cf_span[m] 行，其中第 #cf_span[i] 行描述第 #cf_span[i] 位学生的杯子内容。该行应由一个或多个形如 "#cf_span[b] #cf_span[v]" 的数对组成。每个数对表示有 #cf_span[v]（#cf_span[v > 0]）单位的牛奶从第 #cf_span[b] 瓶（#cf_span[1 ≤ b ≤ n]）倒入了第 #cf_span[i] 个杯子。每行中的所有 #cf_span[b] 必须互不相同。若存在多种解法，输出任意一种即可。实数输出时小数点后至少保留 6 位。 ## Input 输入文件仅包含三个整数 #cf_span[n], #cf_span[w] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 50], #cf_span[100 ≤ w ≤ 1000], #cf_span[2 ≤ m ≤ 50]），其中 #cf_span[n] 表示订购的瓶子数，#cf_span[w] 表示每瓶的体积，#cf_span[m] 表示朋友的人数。 ## Output 如果可以将牛奶倒入杯子，使得每瓶牛奶最多出现在两个不同的杯子中，则在第一行输出 "_YES_"；若无解，则输出 "_NO_"。若有解，则再输出 #cf_span[m] 行，其中第 #cf_span[i] 行描述第 #cf_span[i] 位学生的杯子内容。该行应由一个或多个形如 "#cf_span[b] #cf_span[v]" 的数对组成。每个数对表示有 #cf_span[v]（#cf_span[v > 0]）单位的牛奶从第 #cf_span[b] 瓶（#cf_span[1 ≤ b ≤ n]）倒入了第 #cf_span[i] 个杯子。每行中的所有 #cf_span[b] 必须互不相同。若存在多种解法，输出任意一种即可。实数输出时小数点后至少保留 6 位。 [samples]

**Definitions** Let $ n, w, m \in \mathbb{Z} $ be given, where: - $ n $: number of bottles, - $ w $: volume of milk in each bottle, - $ m $: number of cups (students). Let $ B = \{1, 2, \dots, n\} $ be the set of bottles, each with volume $ w $. Let $ C = \{1, 2, \dots, m\} $ be the set of cups. **Constraints** 1. $ 1 \leq n \leq 50 $ 2. $ 100 \leq w \leq 1000 $ 3. $ 2 \leq m \leq 50 $ 4. Total milk volume: $ T = n \cdot w $ 5. Each cup must receive total volume $ \frac{n \cdot w}{m} $ 6. Each bottle’s milk must be distributed to **at most two** distinct cups. **Objective** Determine whether there exists a distribution $ D: B \times C \to \mathbb{R}_{\geq 0} $ such that: - $ \sum_{c \in C} D(b, c) = w $ for all $ b \in B $ (each bottle fully poured), - $ \sum_{b \in B} D(b, c) = \frac{n \cdot w}{m} $ for all $ c \in C $ (each cup receives equal share), - For each $ b \in B $, $ |\{ c \in C \mid D(b, c) > 0 \}| \leq 2 $ (each bottle contributes to at most two cups). If such a distribution exists, output: - First line: `"YES"` - For each cup $ c \in C $: list pairs $ (b, v) $ where $ v = D(b, c) > 0 $, with $ b \in B $, and all $ b $ on a line distinct. - Use at least 6 decimal digits for $ v $. If no such distribution exists, output: `"NO"`.

Samples

Input #1

2 500 3

Output #1

YES
1 333.333333
2 333.333333
2 166.666667 1 166.666667

Input #2

4 100 5

Output #2

YES
3 20.000000 4 60.000000
1 80.000000
4 40.000000 2 40.000000
3 80.000000
2 60.000000 1 20.000000

Input #3

4 100 7

Output #3

NO

Input #4

5 500 2

Output #4

YES
4 250.000000 5 500.000000 2 500.000000
3 500.000000 1 500.000000 4 250.000000

API Response (JSON)

{
  "problem": {
    "name": "B. End of Exams",
    "description": {
      "content": "Students love to celebrate their holidays. Especially if the holiday is the day of the end of exams! Despite the fact that Igor K., unlike his groupmates, failed to pass a programming test, he decide",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF93B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Students love to celebrate their holidays. Especially if the holiday is the day of the end of exams!\n\nDespite the fact that Igor K., unlike his groupmates, failed to pass a programming test, he decide...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "学生喜欢庆祝他们的假期，尤其是期末考试结束的日子！\n\n尽管 Igor K. 与他的同学们不同，未能通过编程测试，他还是决定邀请他们去咖啡馆，让每个人都能喝一瓶……新鲜的牛奶。进入咖啡馆后，这 #cf_span[m] 位朋友发现菜单上有 #cf_span[n] 种不同的牛奶，于是他们点了 #cf_span[n] 瓶——每种一瓶。我们知道每瓶牛奶的体积为 #cf_span[w]。\n\n当瓶子被端上来后，...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, w, m \\in \\mathbb{Z} $ be given, where:  \n- $ n $: number of bottles,  \n- $ w $: volume of milk in each bottle,  \n- $ m $: number of cups (students).  \n\nLet $ B = \\{1, 2, \\do...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments