/ Vijos / 题库 /

硬币游戏

硬币游戏

描述

  Alice和Bob现在在玩的游戏,主角是依次编号为1到n的n枚硬币。每一枚硬币都有两面,我们分别称之为正面和反面。一开始的时候,有些硬币是正面向上的,有些是反面朝上的。
  Alice和Bob将轮流对这些硬币进行翻转操作,并且Alice总是先手。具体来说,每次一位玩家可以选择一枚编号为x的硬币,要求这枚硬币此刻是反面朝上的。对于编号x来说,我们总可以将x写作x=c×2^a×3^b,其中a和b是非负整数,c是不被2整除也不被3整除的非负整数。然后有两种选择。
  第一种,选择整数p和q满足a>=p×q,p>=1且1<=q<=MAXQ,然后同时翻转所有编号为c×2^(a-p×j)×3^b的硬币,其中j=0,1,2,...,q。
  第二种,选择整数p和q满足b>=p×q,p>=1且1<=q<=MAXQ,然后同时翻转所有编号为c×2^a×3^(b-p×j)的硬币,其中j=0,1,2,...,q。
  可以发现这个游戏不可能无限进行下去,当某位玩家无法继续上述操作时,便输掉了游戏。作为先手玩家的Alice,总是希望可以在比赛开始之前就知道自己能否获胜。他知道自己和Bob都是充分聪明的,所以在游戏过程中两人都会最优化自己的策略并尽量保证自己处在不败的情形中。

格式

输入格式

本题有多组测试数据,第一行输入一个整数t,表示总的数据组数。之后给出t组数据。
对于每一组数据来说,第一行输入两个整数n和MAXQ。
第二行输入n个整数,依次描述了每一枚硬币的初始状态,约定用0表示反面朝上,用1表示正面朝上。

输出格式

输出一共有t行对应t组数据。对于每一组数据来说,如果Alice先手必胜,则输出“win”(不包括引号),否则输出“lose”。

样例1

样例输入1

6
16 14
1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 
16 14
0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 
16 11
0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 1 
16 12
1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 
16 4
1 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 
16 20
0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 

样例输出1

win
lose
win
lose
win
win

限制

对于10%的数据,1<=n<=16且1<=MAXQ<=20。
对于40%的数据,1<=n<=40且1<=MAXQ<=20。
对于100%的数据,1<=n<=30000且1<=MAXQ<=20,t<=100。
此外还有30%的数据,1<=n<=30000且MAXQ=1。

来源

SDOI 2016 round2 day1

信息

ID
1993
难度
3
分类
(无)
标签
递交数
25
已通过
16
通过率
64%
上传者

相关

在下列训练计划中:

RP++分类题库