← 返回题目列表

Codeforces · 1968/D

D. 排列游戏

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

Bodya 和 Sasha 找到了一个排列 $$$p_1,\dots,p_n$$$ 和一个数组 $$$a_1,\dots,a_n$$$。他们决定玩一个著名的“排列游戏”。

长度 $$$n$$$ 的排列是一个数组,由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数以任意顺序组成。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

他们都选择了排列中的起始位置。

游戏持续 $$$k$$$ 回合。玩家同时做出动作。每个回合中,每个玩家都会发生两件事:

- 如果玩家当前位置为$$$x$$$,则他的分数增加$$$a_x$$$。
- 然后玩家要么停留在当前位置$$$x$$$,要么从$$$x$$$移动到$$$p_x$$$。

知道 Bodya 的起始位置 $$$P_B$$$ 和 Sasha 的起始位置 $$$P_S$$$,如果两个玩家都试图获胜,则确定谁赢得比赛。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含整数 $$$n$$$, $$$k$$$, $$$P_B$$$, $$$P_S$$$ ($$$1\le P_B,P_S\le n\le 2\cdot 10^5$$$, $$$1\le k\le 10^9$$$) — 排列的长度,持续时间分别是比赛的起始位置。

下一行包含 $$$n$$$ 整数 $$$p_1,\dots,p_n$$$ ($$$1 \le p_i \le n$$$) — 排列 $$$p$$$ 的元素。

下一行包含 $$$n$$$ 整数 $$$a_1,\dots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 值之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例输出:

- 如果 Bodya 赢得比赛,则“Bodya”。
- 如果 Sasha 赢得比赛,则“Sasha”。
- 如果玩家得分相同,则“平局”。

示例

输入 #1

10
4 2 3 2
4 1 2 3
7 2 5 6
10 8 2 10
3 1 4 5 2 7 8 10 6 9
5 10 5 1 3 7 10 15 4 3
2 1000000000 1 2
1 2
4 4
8 10 4 1
5 1 4 3 2 8 6 7
1 1 2 1 2 100 101 102
5 1 2 5
1 2 4 5 3
4 6 9 4 2
4 2 3 1
4 1 3 2
6 8 5 3
6 9 5 4
6 1 3 5 2 4
6 9 8 9 5 10
4 8 4 2
2 3 4 1
5 2 8 7
4 2 3 1
4 1 3 2
6 8 5 3
2 1000000000 1 2
1 2
1000000000 2

输出 #1

Bodya
Sasha
Draw
Draw
Bodya
Sasha
Sasha
Sasha
Sasha
Bodya

注意

下面您可以找到第一个测试用例的说明,其中游戏由 $$$k=2$$$ 回合组成。

TurnBodya的位置Bodya的得分Bodya的移动Sasha的位置Sasha的得分Sasha的移动第一$$$3$$$$$$0 + a_3 = 0 + 5 = 5$$$保持在同一位置$$$2$$$$$$0 + a_2 = 0 + 2 = 2$$$移动到$$$p_2=1$$$第二个$$$3$$$$$$5 + a_3 = 5 + 5 = 10$$$保持在同一位置$$$1$$$$$$2 + a_1 = 2 + 7 = 9$$$保持在同一位置最终结果$$$3$$$$$10$$$$$$1$$$$$$9$$$

正如我们所看到的,Bodya 的得分更高,因此他赢得了比赛。可见这场比赛博蒂亚总能赢。