伏特找到了 skip 蚤,希望他负责建造月球车站。然而众所周知,skip 蚤是一只大鸽子。于是他掏出了口袋里的硬币,在桌面上摆成了一排,要伏特和他玩一局游戏,结束后就开始干活。
初始时每枚硬币要么正面朝上,要么背面朝上。游戏会一轮轮进行,如果某一时刻(包括初始时刻)所有硬币都是正面,则游戏立刻结束。
每轮的操作如下:
取出最左侧的硬币。
如果这枚硬币正面朝上,则由 skip 蚤选择是否翻转,否则由伏特选择是否翻转。
将这枚硬币放到最右边。
伏特已经被铁路建造弄昏了头,于是他决定随机翻转。每次轮到他决定时,他选择翻转的概率为
skip 蚤是一只非常聪明的鸽子,他通过神秘手段知道了伏特的策略,并且他将以最优策略决定是否翻转来使游戏期望进行轮数尽可能大。
求游戏期望进行几轮,答案对
输入格式
第一行一个长度为
第二行两个整数
输出格式
输出一个整数,表示 skip 蚤在使用最优策略的情况下,游戏结束所需要的期望轮数。
如果游戏轮数的期望不收敛,则输出
否则,题目数据保证了该期望必定可以写成一个分数
样例一
input
10 1 1
output
8
explanation
当局面为 10 时,skip 蚤会选择翻转变为 00。
此时伏特有
接下来伏特有
整体来看,局面为 10 时,期望经过四轮后,有
样例二
input
0011 1 0
output
2
explanation
由于伏特一定会翻转背面硬币,所以两轮以后所有硬币都正面朝上了。
样例三
input
0101 1 0
output
-1
explanation
由于伏特会一直翻转,skip 蚤也只需一直翻转即可保证游戏不会结束。
样例四
见附件下载。
限制与约定
对于
子任务编号 | 特殊性质 | 分值 | |
---|---|---|---|
1 | |||
2 | |||
3 | |||
4 | 无 | ||
5 | 无 |
时间限制:
空间限制:
后记
由于 skip 蚤实在是太鸽了,愤怒的跳蚤国王把 skip 蚤抓回去煲成了汤。