#P11737. [集训队互测 2015] 最优决策(暂无 Special Judge)

[集训队互测 2015] 最优决策(暂无 Special Judge)

题目描述

决策和计策是神犇。

又到了吔饭的时间,可是决策和计策没有时间去吔饭,于是他们决定选出一个人去带饭。

计策提议使用石头剪刀布决出胜负,但是决策觉得这样太没有技术含量,不能做出很有趣的决策,他提出了用这样一种小游戏决定胜负:

  1. 双方各有一个能量槽,可以存储至多 nn 点能量。
  2. 双方都有大技能,当能量槽满了的时候可以释放大技能,并消耗所有能量。
  3. 除了大技能之外有 mm 种小技能,编号为 1,,m1, \dots, m,分为三类:
    1. 消耗型,消耗 xx 个能量,只有能量不小于 xx 时才能使用。
    2. 免费型,不消耗能量,任何时候都可以使用。
    3. 补给型,使用后能获得 xx 个能量,但是使用后总能量如果超过 nn 点那么多余部分会被浪费掉。任何时候都可以使用。
  4. 技能之间有一些相克的关系。大技能克所有小技能。游戏规定了小技能间有若干个相克关系,每个关系形如:ii 号小技能克 jj 号小技能。其它技能之间没有相克关系。
  5. 每回合每个人必须选择一种可使用的技能,然后同时亮出。假如一方出的技能克对方出的技能,那么游戏结束该方获胜。否则双方更新自己的能量槽然后继续游戏。当然,如果同时出大技能那么双方都会清空能量槽然后继续游戏。
  6. 如果游戏永远都不会结束那么算作双方各赢 0.50.5 场。

决策发现自己可以用 AI 跟计策打一局,这样就不用每次自己去花力气打了。

决策还发现每个游戏局面的最优策略只跟双方的能量槽有关,所以自己只需要给程序一张策略表,上面记录了每个状态下出每种技能的概率分别是多少就行了。

但是计策很有计策,决策知道计策会偷偷潜入他的电脑偷看他的程序和策略表。但是由于决策使用了当前系统时间作为随机种子,所以计策并不能知道这一次到底会出什么,只知道出每种技能的概率。

现在决策找到了你,请你找出一种方案使得自己的胜率不低于 50%50\%

但同时计策也找到了你,他给了你决策的策略表,请你找出一种方案使得胜率最大。

与此同时鏼也找到了你,他给出了两个人的策略表,想请你算出每个人有多少的胜率。

输入格式

多组数据。第一行为测试点编号,数据组数 Case\mathrm{Case} 和数据类型 type\mathrm{type}

对于每一组数据,第一行两个正整数分别表示能量槽上限 nn 和小技能种类数 mm

type=1\mathrm{type}=1 则你需要解决鏼的询问,若 type=2\mathrm{type}=2 则你需要解决计策的询问,若 type=3\mathrm{type}=3 则你需要解决决策的询问。

接下来一行 mm 个整数 v1,,vmv_1, \dots, v_m 分别表示小技能对能量槽的改变量,即使用后使用者的能量会加上 viv_ivi<0v_i \lt 0 表示消耗型,vi=0v_i = 0 表示免费型,vi>0v_i>0 表示补给型。

接下来 mm 行每行 mm 个数,第 ii 行第 jj 列如果为 11 表示 ii 号小技能克 jj 号小技能,如果为 1-1 表示 jj 号小技能克 ii 号小技能,如果为 00 表示没有相克关系。保证对角线上元素均为 00 且第 ii 行第 jj 列的元素等于第 jj 行第 ii 列的元素的相反数。

假如 type3\mathrm{type} \neq 3,接下来 n2n^2 行为决策的策略表

假如 type=1\mathrm{type} = 1,接下来 n2n^2 行为计策的策略表。

策略表的输入输出格式

每个能量槽有 n+1n + 1 种状态,所以游戏局面共 (n+1)2(n + 1)^2 种。很明显假如有人能量槽满了的话他一定会放大技能,所以策略表只用记录 n2n^2 种局面的策略。

n2n^2 行,第 ii 行(从 00 开始编号)表示己方能量为 in\lfloor \frac{i}{n} \rfloor,对方能量为 imodni \bmod n 时的策略。

每个策略占一行,共 mm 个整数,分别表示使用小技能 1,,m1, \dots, m 的概率乘以 10910^9 后的结果。保证这些数加起来为 10910^9,保证当前不可使用的小技能的使用概率为 00(即某些消耗型)。

输出格式

如果 type=1\mathrm{type} = 1,输出一行一个浮点数表示决策的胜率,和标准答案的绝对误差在 10610^{-6} 之内均算作正确。

如果 type=2\mathrm{type} = 2,输出一个策略表,设该策略表对决策的策略表的胜率为 xx,我们提供的参考解胜率为 yy,那么当 x>y106x>y-10^{-6} 时算作正确。

如果 type=3\mathrm{type} = 3,输出一个策略表,我们会生成一张策略表,设你的策略表对我们的策略表的胜率为 xx,那么当 x>0.5106x>0.5-10^{-6} 时算作正确。

注:测评时为了防止精度误差,在假如某个状态只有低于 10810^{-8} 的概率转移出死循环时直接将该状态胜率置为 0.50.5

0 1 1
2 3
-1 0 1
0 0 1
0 0 0
-1 0 0
0 0 1000000000
0 1000000000 0
0 0 1000000000
333333334 333333333 333333333
0 0 1000000000
0 1000000000 0
0 0 1000000000
333333334 333333333 333333333
0.5000000000
0 1 2
2 3
-1 0 1
0 0 1
0 0 0
-1 0 0
0 0 1000000000
0 1000000000 0
0 0 1000000000
333333334 333333333 333333333
0 0 1000000000
0 1000000000 0
0 0 1000000000
333333334 333333333 333333333
0 1 3
2 3
-1 0 1
0 0 1
0 0 0
-1 0 0
0 0 1000000000
0 1000000000 0
0 0 1000000000
333333334 333333333 333333333

提示

数据范围

测试点编号 Case\mathrm{Case} nn mm type\mathrm{type} 备注
11 =1=1 =5=5 =30=30 11 输入见附件 jc1.in
22 =100=100
33 =3=3 =5=5 22
44 =30=30 =5=5 =30=30
55 =1=1 =3=3 =3=3 33 游戏局面与样例一相同
66 =5=5
77 =100=100 =2=2 =5=5
88 =5=5
99 =2=2 =30=30
1010 =10=10 =5=5

除了第 5,65,6 两个点,其他点数据均为随机生成。

随机生成方式:

  • 对于每个技能,有 13\frac{1}{3} 的概率是免费型,13\frac{1}{3} 是消耗型,13\frac{1}{3} 是补给型,且消耗型和补给型的 xx 的绝对值不超过 33
  • 保证三种技能至少都有一个。
  • 小技能的相克关系生成方式:
    • 对于每一对技能,有 20%20\% 的概率有相克关系:
      • 假如使用后能量损失相同则各有 50%50\% 概率克对方。
      • 假如使用后不同则收益大的一方有 20%20\% 的概率克对方,收益小的一方有 80%80\% 的概率克对方。
      • 保证每个补给型技能至少被一个技能克。
    • 保证至少存在一个补给型技能使得只有消耗型技能才能克它。
  • 策略表生成方式:
    • 对于一个状态,把可使用的小技能的使用概率置为均等。由于必须要是 10910^{-9} 的整数倍有可能无法均匀分配,保证任意两个可使用的小技能的使用概率之差的绝对值不超过 10910^{-9}
    • 然后进行 100100 次操作,每次操作选择两个不同的可使用的小技能 i,ji, j,产生一个 10910^{-9}ii 技能的使用概率之间的均匀随机数 δ\delta,且 δ\delta10910^{-9} 的整数倍。将 ii 的概率减少 δ\delta,将 jj 的概率加上 δ\delta

如果不理解可以参考 11 号点。