1 second
256 megabytes
standard input
standard output
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 XXXLyou 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.
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 sizesS, 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.
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.
0 1 0 1 1 0
3
XL
S,M
XL,XXL
YES
XL
M
XXL
1 1 2 0 1 1
5
S
M
S,M
XXL,XXXL
XL,XXL
NO
分析：因为1个人最多选两件型号相邻的T恤，所以直接从小到大的型号贪心即可；
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<ll,int>
#define Lson L, mid, ls[rt]
#define Rson mid+1, R, rs[rt]
#define sys system("pause")
const int maxn=1e5+;
using namespace std;
ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}
inline ll read()
{
ll x=;int f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,k,t,c[];
struct node
{
string a,b;
int ca;
}op[maxn];
string d;
bool flag=true;
string ca[]={"S","M", "L", "XL", "XXL", "XXXL"};
int gao(string a)
{
int i;
rep(i,,)if(a==ca[i])return i+;
}
vi v[];
int main()
{
int i,j;
rep(i,,)scanf("%d",&c[i]);
scanf("%d",&n);
rep(i,,n)
{
cin>>d;
int xx=;
for(j=;d[j];j++)
{
if(d[j]==',')
{
xx=j;
break;
}
}
if(xx)
{
op[i].a=d.substr(,xx);
op[i].b=d.substr(xx+);
v[gao(d.substr(,xx))].pb(i);
}
else
{
if(--c[gao(d)]<)
{
flag=false;
break;
}
op[i].a=d;
op[i].ca=;
}
}
for(i=;i<=;i++)
{
for(int x:v[i])
{
if(c[i]>)
{
c[i]--;
op[x].ca=;
}
else if(c[i+]>)c[i+]--,op[x].ca=;
else
{
flag=false;
break;
}
}
}
if(flag)
{
puts("YES");
rep(i,,n)
{
if(op[i].ca==)cout<<op[i].a<<endl;
else cout<<op[i].b<<endl;
}
}
else puts("NO");
//system("Pause");
return ;
}