Preparing NOJ

KSS的金牌梦1

3000ms 65536K

Description:

KSSnupt集训队里公认最具有金牌实力的选手,熟练掌握多种金牌算法但是由于队友水平太菜和自身情绪不稳定一直没能拿到金牌。KSS为了圆梦,想为自己制定一个训练计划,那么问题来了:

ACM有许多算法之间单方面依赖关系的,比如:想学会A,就必须先学B,由于KSS很聪明,所以它可以学完AB当然也存在两种多种算法相互交融的情况比如想学会A,就必须先学B想学会B,就必须先学A,这种情况KSS不知从何下手了

现在给出KSS打算学习的一些算法之间的依赖关系KSS尽自己最大的努力去学习这些算法。再给出比赛出现的算法,如果KSS能学会超过70%的比赛算法他就能圆梦否则他只能含恨退役。

Input:

多组测试用例

第一行一个整数N(0<=N<=250000)表示有N算法存在依赖关系,保证涉及的算法总数不超过500


接下来N行每行有两个字符串(以空格分割),表示前一个算法依赖后一个算法N+1有一个整数M(0<M<=1000)表示比赛会出现M算法,接下来M每行有一个字符串表示比赛出现的算法。(字符串保证不含空格)

Output:

如果KSS可以圆梦,输出“Excelsior!否则,输出“KSS have a dream!。(不用输出引号)

Sample Input:

4
Aho-Corasickautomaton KMP
Aho-Corasickautomaton trietree
Inclusion-ExclusionPrinciple Mobiusinversion
Mobiusinversion Inclusion-ExclusionPrinciple
5
KMP
trietree
Aho-Corasickautomaton
Splay
Suffixarray

Sample Output:

KSS have a dream!

Note:

对于样例,KSS可以学会KMPtrietreeAho-Corasickautomaton但是不能学会Inclusion-ExclusionPrincipleMobiusinversion所以只能掌握60%比赛算法


本题由旧版NOJ导入,来源:hjp

Info

NOJ

Provider NOJ

Code NOJ2080

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet