a321. TOI 2019/03 潛力組：石頭遊戲

題目描述

Alice 和 Bob 輪流從同一堆石頭中取走石頭，Alice 先手。每回合可取走的數量必須是事先指定的 N 個數字之一，且不能超過目前剩餘數量。如果輪到某人時石頭已全部取完，該人輸掉這局。

指定數字中的第一個一定是 1，因此只要還有石頭就能進行下一步。兩人都使用最佳策略。給定相同的可取數量及 M 局不同的初始石頭數，請分別判斷 Alice 是否能獲勝。

輸入格式

第一行為 N，1≤N≤50。第二行為 N 個可取數量 P，1≤P≤2×10^6，其中第一個數字為 1；原題範例允許數字重複。

第三行為局數 M，1≤M≤10^5。接下來 M 行各有一個初始石頭數 Q，1≤Q≤2×10^6。每筆資料共 M+3 行。

分組：10 分滿足 P、Q≤4 且 M=1；30 分滿足 P、Q≤100000；60 分滿足 P、Q≤2000000。

輸出格式

依輸入順序輸出 M 行。Alice 能獲勝時輸出 Win!，否則輸出 Lose，注意大小寫及驚嘆號。

範例 1 中，6 顆石頭時，不論先取多少，對手都能取完；7 顆時可先取 1 顆，把必敗局面留給對手。範例 2 中，5 顆可直接取完；6 顆為必敗局面；8 顆可先取 5 顆，再依對手取的數量取完剩下石頭。

範例 1

輸入：

5
1 2 3 4 5
2
6
7

輸出：

Lose
Win!

範例 2

輸入：

4
1 2 2 5
3
5
6
8

輸出：

Win!
Lose
Win!

來源

TOI 2019/03 練習賽潛力組〈石頭遊戲〉。依官方原題 PDF 自行整理，所有範例均取自原件。

原題連結：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/201903/A3-StoneGame(Q).pdf