← 返回题目列表

Codeforces · 48/E

E. 愚者伊万 VS 龙戈里尼奇

中文机器翻译题面 查看原题

很久很久以前,在一个遥远的王国……好吧,让我们从愚人伊凡遇到龙戈里尼奇的地方开始。伊凡拿出魔剑,战斗开始了。首先,Gorynych 有 h 头和 t 尾。伊万的每一次剑击都可以砍掉几个头(从1到n,但不超过戈里内奇目前拥有的),或几个尾巴(从1到m,但不超过戈里内奇目前拥有的)。与此同时,尽管看起来很可怕,戈里尼奇龙也能长出新的头和尾巴。而生长的头和尾的数量是由当前打击砍掉的头或尾的数量唯一决定的。当正面和反面的总数超过R时,巨龙戈里尼奇会发出最后一击并消灭愚者伊凡。所以伊凡的目标是尽快砍掉所有龙头和龙尾并取得胜利。事件还可以以第三种方式发展:双方都无法战胜对方,他们将永远继续战斗。

故事是这样的;说起来容易,做起来难。你的任务是编写一个程序来决定战斗的结果。考虑到伊万连续出击。每次打击后,戈里尼奇都会根据被砍掉的数量长出一些新的头和尾。如果龙戈里尼奇在受到打击后失去了所有的头和尾巴并且无法长出新的,那么他就被击败了。伊万以最佳方式战斗(傻瓜很幸运),即

- 如果伊万能够获胜,则他以最少的打击次数获胜;
- 如果无法击败戈里内奇,但可以无限长时间地抵抗他,那么这就是伊凡选择的策略;
- 如果戈里尼奇无论如何都会获胜,伊万的目标是尽可能长时间地抵抗他。

输入

第一行包含三个整数h、t和R(0≤h,t,R≤200,0<h+t≤R),分别代表Gorynych的正面和反面的初始数量以及Gorynych龙尚未攻击的最大正面和反面总数。下一行包含整数 n (1 ≤ n ≤ 200)。接下来的 n 包含一对非负数“hi ti”,它们相应地表示正面的数量和反面的数量,如果 Gorynych 切了 i 个正面 (1 ≤ i ≤ n),则该数量将会增长。下一行包含一个整数 m (1 ≤ m ≤ 200),然后是——以与上述相同的格式描述戈里尼奇的尾巴被切断时的行为。输入文件中的所有数字不超过 200。

输出

如果 Ivan 获胜,则在第一行打印“Ivan”(不带引号);如果 Gorynych the Dragon 获胜,则在第一行打印“Zmey”(俄语中的龙的意思)。在第二行中打印一个整数,表示伊万的打击次数。如果战斗将永远持续下去,请在第一行打印“Draw”。

示例

输入 #1

2 2 4
2
1 0
0 1
3
0 1
0 1
0 0

输出 #1

Ivan
2

输入 #2

2 2 4
1
0 1
1
1 0

输出 #2

Draw

输入 #3

2 2 5
1
1 1
1
3 0

输出 #3

Zmey
2