loj#P2490. 「2018 集训队互测 Day 4」小修和小栋玩♂游戏

    ID: 15760 problem_type.undefined ms MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>图论提交答案搜索构造随机化模拟退火2018集训队互测

「2018 集训队互测 Day 4」小修和小栋玩♂游戏

Cannot parse: undefinedms error parsing time

题目描述

这是一道提交答案题

小修和小栋在合作玩一个游戏。

小修会随机拿到 [0,m1][0,m-1] 中的一个整数,然后走进一个房间。

房间有 nn 盏灯排成一行,小修进入房间之前它们被随机设定着状态,并且小修和小栋预先都不知道灯的状态。

进入房间后,小修可以搬动开关改变其中至多一盏灯的状态,也可以不改变,然后她走出房间并且不与小栋交谈。

接下来小栋需要走进房间,观察灯的状态并猜测小修拿到了哪个数,如果猜对那么两人获胜。

游戏开始前小修和小栋需要商量一个计划,该计划是小栋在看到的灯的每种状态下会猜测哪一个字母,而小修的策略是尽可能使得小栋的猜测是正确的。

请你帮他们设计一个获胜局面尽可能多的计划。

输入格式

输入文件包含三个整数 n,m,pn,m,pn,mn,m 含义见上,pp 表示该测试点的分数。

输出格式

输出一行 2n2^n 个整数,其中第 ii 位表示灯的状态用二进制数表示为 i1i-1 时,小栋会猜测的数。

3 3 1
0 0 1 2 2 1 0 2

评分方式

如果你的计划不合法,得 00 分。

当你的计划对于所有 2nm2^n\cdot m 种局面都可以获胜,得 pp 分。

否则记 cc 为你的计划中不能获胜的局面总数,得分为 p1.05c\frac{p}{1.05^{c}}