CF786A.Berzerk

普及+/提高

通过率:0%

时间限制:4.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Rick and Morty are playing their own version of Berzerk (which has nothing in common with the famous Berzerk game). This game needs a huge space, so they play it with a computer.

In this game there are n objects numbered from 1 to n arranged in a circle (in clockwise order). Object number 1 is a black hole and the others are planets. There's a monster in one of the planet. Rick and Morty don't know on which one yet, only that he's not initially in the black hole, but Unity will inform them before the game starts. But for now, they want to be prepared for every possible scenario.

Each one of them has a set of numbers between 1 and n - 1 (inclusive). Rick's set is _s_1 with _k_1 elements and Morty's is _s_2 with _k_2 elements. One of them goes first and the player changes alternatively. In each player's turn, he should choose an arbitrary number like x from his set and the monster will move to his x-th next object from its current position (clockwise). If after his move the monster gets to the black hole he wins.

Your task is that for each of monster's initial positions and who plays first determine if the starter wins, loses, or the game will stuck in an infinite loop. In case when player can lose or make game infinity, it more profitable to choose infinity game.

瑞克和莫蒂正在玩他们自己版本的“狂暴”游戏(该版本与著名的“狂暴”游戏毫无关联)。这个游戏需要极大的空间,因此他们用计算机来运行。

游戏中有 $ n $ 个物体,编号从 $ 1 $ 到 $ n $,按顺时针方向围成一个圆圈。编号为 $ 1 $ 的物体是黑洞,其余物体为行星。怪物初始位于某颗行星上。瑞克和莫蒂尚不知道它具体在哪个行星上,只知道它初始时不在黑洞中;不过,在游戏开始前,“统一”(Unity)会告知他们怪物的确切初始位置。但目前,他们希望为每一种可能的情形都做好准备。

每位玩家都拥有一组介于 $ 1 $ 到 $ n-1 $(含端点)之间的整数:瑞克的集合为 $ s_1 $,大小为 $ k_1 $;莫蒂的集合为 $ s_2 $,大小为 $ k_2 $。其中一人先手,之后双方轮流行动。在每位玩家的回合中,他须从自己的集合中任选一个数 $ x $,然后怪物将从当前位置沿顺时针方向移动到其后第 $ x $ 个物体处。若该次移动后怪物恰好到达黑洞(即位置 $ 1 $),则当前玩家获胜。

你的任务是:对怪物的每一种可能初始位置,以及对每一种先手玩家(瑞克或莫蒂),判断先手玩家最终是必胜、必败,还是游戏将陷入无限循环。特别地,当某位玩家既可选择导致自己失败的走法,也可选择导致无限循环的走法时,他更倾向于选择使游戏无限循环的走法。

输入格式

The first line of input contains a single integer n (2 ≤ n ≤ 7000) — number of objects in game.

The second line contains integer _k_1 followed by _k_1 distinct integers _s_1, 1, _s_1, 2, ..., _s_1, _k_1 — Rick's set.

The third line contains integer _k_2 followed by _k_2 distinct integers _s_2, 1, _s_2, 2, ..., _s_2, _k_2 — Morty's set

1 ≤ k__i ≤ n - 1 and 1 ≤ s__i, 1, s__i, 2, ..., s__i, k__i ≤ n - 1 for 1 ≤ i ≤ 2.

输入的第一行包含一个整数 nn(2≤n≤70002 \leq n \leq 7000)—— 游戏中物体的数量。

第二行包含一个整数 k1k_1,后跟 k1k_1 个互不相同的整数 s1,1, s1,2, …, s1,k1s_{1,1},\ s_{1,2},\ \dots,\ s_{1,k_1} —— Rick 的集合。

第三行包含一个整数 k2k_2,后跟 k2k_2 个互不相同的整数 s2,1, s2,2, …, s2,k2s_{2,1},\ s_{2,2},\ \dots,\ s_{2,k_2} —— Morty 的集合。

对 1≤i≤21 \leq i \leq 2,有 1≤ki≤n−11 \leq k_i \leq n - 1,且 1≤si,1, si,2, …, si,ki≤n−11 \leq s_{i,1},\ s_{i,2},\ \dots,\ s_{i,k_i} \leq n - 1。

输出格式

In the first line print n - 1 words separated by spaces where i-th word is "Win" (without quotations) if in the scenario that Rick plays first and monster is initially in object number i + 1 he wins, "Lose" if he loses and "Loop" if the game will never end.

Similarly, in the second line print n - 1 words separated by spaces where i-th word is "Win" (without quotations) if in the scenario that Morty plays first and monster is initially in object number i + 1 he wins, "Lose" if he loses and "Loop" if the game will never end.

第一行输出 n−1n-1 个单词,以空格分隔;其中第 ii 个单词为 "Win"(不含引号),表示在 Rick 先手、怪物初始位于编号为 i+1i+1 的物体上时 Rick 获胜;为 "Lose" 表示 Rick 失败;为 "Loop" 表示游戏永不结束。

第二行同样输出 n−1n-1 个单词,以空格分隔;其中第 ii 个单词为 "Win"(不含引号),表示在 Morty 先手、怪物初始位于编号为 i+1i+1 的物体上时 Morty 获胜;为 "Lose" 表示 Morty 失败;为 "Loop" 表示游戏永不结束。

输入输出样例

  • 输入#1

    5
    2 3 2
    3 1 2 3

    输出#1

    Lose Win Win Loop
    Loop Win Win Win
  • 输入#2

    8
    4 6 2 3 4
    2 3 6

    输出#2

    Win Win Win Win Win Win Win
    Lose Win Lose Lose Win Lose Lose

输入解题思路,AI测评打分。不知道怎么写?

首页