2209 . DZ的因數遊戲

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

59.0% (46/78)

Submission's AC Ratio

18.6% (122/657)

Tags

CKcon 2021-CKcon

Description

Danb與Zisk是資訊奧林匹亞的國手，除了在程式競賽上決勝負之外，平常的他們也會玩各種遊戲以互相較勁。

今天Danb與Zisk在玩一個與因數有關的遊戲。遊戲一開始他們在白板上寫下兩個正整數x,y，接著雙方會輪流進行操作。每次操作會選目前比較大的數字c，接著他們會擦掉c，並寫下任何一個小於c的因數（即寫下的數字d必須整除c且d<c）。Danb為先手，而當某位玩家無法再進行操作時，那位玩家就輸了。

因為Danb和Zisk都絕頂聰明，因此他們一定會用最佳策略玩此遊戲。但即使如此，最終仍然有人會勝出，而你想知道誰會是勝出的人。

Input Format

第一行輸入一個正整數t，代表Danb跟 Zisk 玩了多少場遊戲。
接下來每行有兩個正整數x,y，代表一場遊戲一開始寫下的數字。

對於所有測資，t≤10，x,y≤108，且單筆測資裡面所有x,y的總和不會超過2×108。

Output Format

輸出t行，第i行表示對於第i場遊戲，如果Danb有必勝策略輸出"Danb"，如果Zisk有必勝策略輸出"Zisk"（不含引號）。

Sample Input 1

2
3 4
1 1

Sample Output 1

Danb
Zisk

Hints

以範測為例，第一場對局中，Danb可以把4改成2，而Zisk只能把3改成1，於是Danb把2改成1，Zisk無法行動，Danb勝。而第二場對局中，Danb一開始就無法行動，因此Zisk勝。

Problem Source

110學年度建國中學校內資訊能力競賽初試pD

Subtasks

No. Testdata Range Constraints Score
1 0~9 x=1 5
2 0~19 x 整除 y 8
3 20~29 x是質數 17
4 30~34, 65~67 x,y≤1000 21
5 30~44, 65~67 x,y≤106 23
6 0~67 無其他限制 26

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 131072 65536 1 2 6
1 1500 131072 65536 1 2 6
2 1500 131072 65536 1 2 6
3 1500 131072 65536 1 2 6
4 1500 131072 65536 1 2 6
5 1500 131072 65536 1 2 6
6 1500 131072 65536 1 2 6
7 1500 131072 65536 1 2 6
8 1500 131072 65536 1 2 6
9 1500 131072 65536 1 2 6
10 1500 131072 65536 2 6
11 1500 131072 65536 2 6
12 1500 131072 65536 2 6
13 1500 131072 65536 2 6
14 1500 131072 65536 2 6
15 1500 131072 65536 2 6
16 1500 131072 65536 2 6
17 1500 131072 65536 2 6
18 1500 131072 65536 2 6
19 1500 131072 65536 2 6
20 1500 131072 65536 3 6
21 1500 131072 65536 3 6
22 1500 131072 65536 3 6
23 1500 131072 65536 3 6
24 1500 131072 65536 3 6
25 1500 131072 65536 3 6
26 1500 131072 65536 3 6
27 1500 131072 65536 3 6
28 1500 131072 65536 3 6
29 1500 131072 65536 3 6
30 1500 131072 65536 4 5 6
31 1500 131072 65536 4 5 6
32 1500 131072 65536 4 5 6
33 1500 131072 65536 4 5 6
34 1500 131072 65536 4 5 6
35 1500 131072 65536 5 6
36 1500 131072 65536 5 6
37 1500 131072 65536 5 6
38 1500 131072 65536 5 6
39 1500 131072 65536 5 6
40 1500 131072 65536 5 6
41 1500 131072 65536 5 6
42 1500 131072 65536 5 6
43 1500 131072 65536 5 6
44 1500 131072 65536 5 6
45 1500 131072 65536 6
46 1500 131072 65536 6
47 1500 131072 65536 6
48 1500 131072 65536 6
49 1500 131072 65536 6
50 1500 131072 65536 6
51 1500 131072 65536 6
52 1500 131072 65536 6
53 1500 131072 65536 6
54 1500 131072 65536 6
55 1500 131072 65536 6
56 1500 131072 65536 6
57 1500 131072 65536 6
58 1500 131072 65536 6
59 1500 131072 65536 6
60 1500 131072 65536 6
61 1500 131072 65536 6
62 1500 131072 65536 6
63 1500 131072 65536 6
64 1500 131072 65536 6
65 1500 131072 65536 4 5 6
66 1500 131072 65536 4 5 6
67 1500 131072 65536 4 5 6
Submit
Back to Top