D. T-shirts Distribution

Codeforces
IDCF727D
Time1000ms
Memory256MB
Difficulty
constructive algorithmsflowsgreedy
English · Original
Chinese · Translation
Formal · Original
The organizers of a programming contest have decided to present t-shirts to participants. There are six different t-shirts sizes in this problem: _S_, _M_, _L_, _XL_, _XXL_, _XXXL_ (sizes are listed in increasing order). The t-shirts are already prepared. For each size from _S_ to _XXXL_ you are given the number of t-shirts of this size. During the registration, the organizers asked each of the _n_ participants about the t-shirt size he wants. If a participant hesitated between two sizes, he could specify two neighboring sizes — this means that any of these two sizes suits him. Write a program that will determine whether it is possible to present a t-shirt to each participant of the competition, or not. Of course, each participant should get a t-shirt of proper size: * the size he wanted, if he specified one size; * any of the two neibouring sizes, if he specified two sizes. If it is possible, the program should find any valid distribution of the t-shirts. ## Input The first line of the input contains six non-negative integers — the number of t-shirts of each size. The numbers are given for the sizes _S_, _M_, _L_, _XL_, _XXL_, _XXXL_, respectively. The total number of t-shirts doesn't exceed 100 000. The second line contains positive integer _n_ (1 ≤ _n_ ≤ 100 000) — the number of participants. The following _n_ lines contain the sizes specified by the participants, one line per participant. The _i_\-th line contains information provided by the _i_\-th participant: single size or two sizes separated by comma (without any spaces). If there are two sizes, the sizes are written in increasing order. It is guaranteed that two sizes separated by comma are neighboring. ## Output If it is not possible to present a t-shirt to each participant, print «_NO_» (without quotes). Otherwise, print _n_ + 1 lines. In the first line print «_YES_» (without quotes). In the following _n_ lines print the t-shirt sizes the orginizers should give to participants, one per line. The order of the participants should be the same as in the input. If there are multiple solutions, print any of them. [samples]
编程竞赛的组织者决定为参赛者发放T恤。本题中有六种不同的T恤尺码:_S_、_M_、_L_、_XL_、_XXL_、_XXXL_(尺码按递增顺序列出)。T恤已经准备完毕,对于从_S_到_XXXL_的每种尺码,都给出了该尺码的T恤数量。 在注册期间,组织者询问了每个#cf_span[n]名参赛者希望获得的T恤尺码。如果某位参赛者在两种尺码之间犹豫,他可以指定两个相邻的尺码——这意味着这两种尺码中的任意一种都适合他。 编写一个程序,判断是否能够为每位参赛者发放一件合适的T恤。当然,每位参赛者应获得与其需求匹配的尺码: 如果可能,程序应找出一种有效的T恤分配方案。 输入的第一行包含六个非负整数——分别表示_S_、_M_、_L_、_XL_、_XXL_、_XXXL_这六种尺码的T恤数量。T恤总数不超过#cf_span[100 000]。 第二行包含一个正整数#cf_span[n](#cf_span[1 ≤ n ≤ 100 000])——参赛者人数。 接下来的#cf_span[n]行,每行包含一名参赛者指定的尺码。第#cf_span[i]行包含第#cf_span[i]名参赛者的信息:一个单独的尺码,或两个由逗号(无空格)分隔的尺码。如果存在两个尺码,则按递增顺序书写。保证由逗号分隔的两个尺码是相邻的。 如果无法为每位参赛者发放T恤,请输出«_NO_»(不含引号)。 否则,请输出#cf_span[n + 1]行。第一行输出«_YES_»(不含引号)。接下来的#cf_span[n]行,每行输出组织者应分配给参赛者的T恤尺码,顺序与输入中参赛者的顺序一致。 如果有多种解法,输出任意一种即可。 ## Input 输入的第一行包含六个非负整数——分别表示_S_、_M_、_L_、_XL_、_XXL_、_XXXL_这六种尺码的T恤数量。T恤总数不超过#cf_span[100 000]。第二行包含一个正整数#cf_span[n](#cf_span[1 ≤ n ≤ 100 000])——参赛者人数。接下来的#cf_span[n]行,每行包含一名参赛者指定的尺码。第#cf_span[i]行包含第#cf_span[i]名参赛者的信息:一个单独的尺码,或两个由逗号(无空格)分隔的尺码。如果存在两个尺码,则按递增顺序书写。保证由逗号分隔的两个尺码是相邻的。 ## Output 如果无法为每位参赛者发放T恤,请输出«_NO_»(不含引号)。否则,请输出#cf_span[n + 1]行。第一行输出«_YES_»(不含引号)。接下来的#cf_span[n]行,每行输出组织者应分配给参赛者的T恤尺码,顺序与输入中参赛者的顺序一致。如果有多种解法,输出任意一种即可。 [samples]
**Definitions:** Let the six t-shirt sizes be ordered as: $ s_0 = \text{S},\ s_1 = \text{M},\ s_2 = \text{L},\ s_3 = \text{XL},\ s_4 = \text{XXL},\ s_5 = \text{XXXL} $ Let $ c = (c_0, c_1, c_2, c_3, c_4, c_5) \in \mathbb{N}^6 $ be the vector of available t-shirt counts for each size. Let $ n \in \mathbb{N}^+ $ be the number of participants. For each participant $ i \in \{1, \dots, n\} $, let $ A_i \subseteq \{0,1,2,3,4,5\} $ be the set of acceptable sizes, where: - $ |A_i| = 1 $ if the participant requested a single size, - $ |A_i| = 2 $ and $ A_i = \{j, j+1\} $ for some $ j \in \{0,1,2,3,4\} $ if the participant requested two neighboring sizes. **Constraints:** We seek an assignment function $ f: \{1, \dots, n\} \to \{0,1,2,3,4,5\} $ such that: 1. $ f(i) \in A_i $ for all $ i \in \{1, \dots, n\} $, 2. $ \left| \{ i \mid f(i) = j \} \right| \leq c_j $ for all $ j \in \{0,1,2,3,4,5\} $. **Objective:** Determine whether such an assignment $ f $ exists. If yes, output one such assignment; otherwise, output "NO".
Samples
Input #1
0 1 0 1 1 0
3
XL
S,M
XL,XXL
Output #1
YES
XL
M
XXL
Input #2
1 1 2 0 1 1
5
S
M
S,M
XXL,XXXL
XL,XXL
Output #2
NO
API Response (JSON)
{
  "problem": {
    "name": "D. T-shirts Distribution",
    "description": {
      "content": "The organizers of a programming contest have decided to present t-shirts to participants. There are six different t-shirts sizes in this problem: _S_, _M_, _L_, _XL_, _XXL_, _XXXL_ (sizes are listed i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF727D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The organizers of a programming contest have decided to present t-shirts to participants. There are six different t-shirts sizes in this problem: _S_, _M_, _L_, _XL_, _XXL_, _XXXL_ (sizes are listed i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "编程竞赛的组织者决定为参赛者发放T恤。本题中有六种不同的T恤尺码:_S_、_M_、_L_、_XL_、_XXL_、_XXXL_(尺码按递增顺序列出)。T恤已经准备完毕,对于从_S_到_XXXL_的每种尺码,都给出了该尺码的T恤数量。\n\n在注册期间,组织者询问了每个#cf_span[n]名参赛者希望获得的T恤尺码。如果某位参赛者在两种尺码之间犹豫,他可以指定两个相邻的尺码——这意味着这两种尺码中的任意...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions:**\n\nLet the six t-shirt sizes be ordered as:  \n$ s_0 = \\text{S},\\ s_1 = \\text{M},\\ s_2 = \\text{L},\\ s_3 = \\text{XL},\\ s_4 = \\text{XXL},\\ s_5 = \\text{XXXL} $\n\nLet $ c = (c_0, c_1, c_2, c_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments