T-Shirt Gumbo
Time Limit: 1000MS |
|
Memory Limit: 65536K |
Total Submissions: 1437 |
|
Accepted: 635 |
Description
Boudreaux and Thibodeaux are student volunteers for this year's ACM South Central Region's programming contest. One of their duties is to distribute the contest T-shirts to arriving teams. The T-shirts had to be ordered in advance using an educated guess as to how many shirts of each size should be needed. Now it falls to Boudreaux and Thibodeaux to determine if they can hand out T-shirts to all the contestants in a way that makes everyone happy.
Input
Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.
A single data set has 4 components:
- Start line - A single line:
START X
where (1 <= X <= 20) is the number of contestants demanding shirts.
- Tolerance line - A single line containing X space-separated pairs of letters indicating the size tolerances of each contestant. Valid size letters are S - small, M - medium, L - large, X - extra large, T - extra extra large. Each letter pair will indicate the range of sizes that will satisfy a particular contestant. The pair will begin with the smallest size the contestant will accept and end with the largest. For example:
MX
would indicate a contestant that would accept a medium, large, or extra large T-shirt. If a contestant is very picky, both letters in the pair may be the same.
- Inventory line - A single line:
S M L X T
indicating the number of each size shirt in Boudreaux and Thibodeaux's inventory. These values will be between 0 and 20 inclusive.
- End line - A single line:
END
After the last data set, there will be a single line:
ENDOFINPUT
Output
For each data set, there will be exactly one line of output. This line will reflect the attitude of the contestants after the T-shirts are distributed. If all the contestants were satisfied, output:
T-shirts rock!
Otherwise, output:
I'd rather not wear a shirt anyway...
Sample Input
START 1
ST
0 0 1 0 0
END
START 2
SS TT
0 0 1 0 0
END
START 4
SM ML LX XT
0 1 1 1 0
END
ENDOFINPUT
Sample Output
T-shirts rock!
I'd rather not wear a shirt anyway...
I'd rather not wear a shirt anyway...
Source
题目不难,关键在于建图
Source Code
Problem: 2584
|
|
User: bingshen
|
Memory: 144K |
|
Time: 0MS |
Language: C++ |
|
Result: Accepted
|
-
Source Code
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
bool map[105][105];
bool used[105];
int link[105];
int a[10];
char size[105][2];
int sz[105][2];
int n,m;
void init()
{
memset(map,0,sizeof(map));
memset(link,-1,sizeof(link));
m=0;
}
bool dfs(int v)
{
int i;
for(i=0;i<n;i++)
{
if(!used[i]&&map[v][i])
{
used[i]=true;
if(link[i]==-1||dfs(link[i]))
{
link[i]=v;
return true;
}
}
}
return false;
}
int main()
{
int i,j,k;
char control[20],str[10];
while(scanf("%s",control)!=EOF)
{
if(strcmp(control,"ENDOFINPUT")==0)
break;
init();
if(strcmp(control,"START")==0)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",size[i]);
if(size[i][0]=='S')
sz[i][0]=1;
if(size[i][0]=='M')
sz[i][0]=2;
if(size[i][0]=='L')
sz[i][0]=3;
if(size[i][0]=='X')
sz[i][0]=4;
if(size[i][0]=='T')
sz[i][0]=5;
if(size[i][1]=='S')
sz[i][1]=1;
if(size[i][1]=='M')
sz[i][1]=2;
if(size[i][1]=='L')
sz[i][1]=3;
if(size[i][1]=='X')
sz[i][1]=4;
if(size[i][1]=='T')
sz[i][1]=5;
}
for(i=1;i<=5;i++)
scanf("%d",&a[i]);
for(i=1;i<=5;i++)
{
for(j=0;j<a[i];j++)
{
for(k=0;k<n;k++)
{
if(sz[k][0]<=i&&i<=sz[k][1])
{
map[m][k]=true;
}
}
m++;
}
}
int ans=0;
for(i=0;i<m;i++)
{
memset(used,0,sizeof(used));
if(dfs(i))
ans++;
}
if(ans==n)
printf("T-shirts rock!/n");
else
printf("I'd rather not wear a shirt anyway.../n");
scanf("%s",str);
}
}
return 0;
}
分享到:
相关推荐
poj openjudge 1111题最大正向匹配 提交ac
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ中级-基本算法 解题报告+AC代码
初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) ... (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) ......
分类很好,我自己也在做,我不是为了赚积分,只是为了分享给大家,2个积分,很便宜~
关于C++ 算法 北大网站POJ 八数码问题
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ第1005题答案(C语言)
poj1087贪心算法实验报告 poj1087贪心算法实验报告
用贪心算法解决POJ 1065的木棍处理问题
这里面有介绍ACM中的算法,包括算法分类,以及对应在POJ上面的训练题目