#P11077. 「FSLOI Round I」石子

    ID: 10546 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>博弈论洛谷原创O2优化洛谷月赛Ad-hoc

「FSLOI Round I」石子

题目背景

English statement. You must submit your code at the Chinese version of the statement.

小 F 和小 L 正在玩一种古老的博弈游戏的改版。

题目描述

给定 nn 堆石子,第 ii 堆有 aia_i 个石子。设序列 a1,a2,,ana_1,a_2,\cdots,a_n 的平均数为 xx。此外,还会给定一个不大于 xx 的数字 kk。小 F 和小 L 将轮流进行以下操作直至一方胜出,小 F 先手:

  • 选定两堆石子 i,ji,j,满足 ai<x<aja_i < x < a_j。若无法选出这样的两堆石子,则对方获胜。

  • 从第 jj 堆石子中拿出 kk 个石子放到第 ii 堆中。

小 F 和小 L 都将用最优策略进行操作。

若游戏会无限进行下去,输出 Draw。若小 F 将获胜,输出 F。否则,输出 L

小 F 一共会进行 TT 场游戏,你需要告诉他每场游戏的结果。

输入格式

第一行一个整数 TT,表示共有 TT 组数据。

每组数据共两行。

第一行输入两个整数 n,kn,k

第二行输入 nn 个整数 aia_i

输出格式

TT 行。

每行应为 DrawFL 中的一种。

1
5 2
1 5 7 9 13
L
2
6 3
4 7 5 3 1 16
7 2
2 6 4 8 12 4 6

Draw
L

提示

【样例 1 解释】

平均数为 77

小 F 可以选择 i=1,j=5i=1,j=5 进行操作,使得石子数分别为 3,5,7,9,113,5,7,9,11

小 L 可以选择 i=1,j=4i=1,j=4 进行操作,使得石子数分别为 5,5,7,7,115,5,7,7,11

小 F 可以选择 i=2,j=5i=2,j=5 进行操作,使得石子数分别为 5,7,7,7,95,7,7,7,9

小 L 可以选择 i=1,j=5i=1,j=5 进行操作,使得石子数分别为 7,7,7,7,77,7,7,7,7

小 F 无法进行操作。小 L 获胜。可以证明无论小 F 如何操作,小 L 都有必胜策略。

【数据规模与约定】

本题采用捆绑测试。

xx 为序列 aa 的平均值。

对于 100%100 \% 的数据,保证:

  • 1T101 \leq T \leq 10
  • 1n2×1051 \leq n \leq 2\times10^5
  • 0ai1090 \leq a_i \leq 10^9
  • 1kx1 \leq k \leq x
  • xx 为整数
子任务 分值 特殊性质
11 55 AA
22 1010 k=1k = 1
33 1515 n5,T=1n \leq 5, T =1
44 2525 n1000n \leq 1000
55 4545

特殊性质 AAa1=a2=a3==ana_1=a_2=a_3=\cdots=a_n