娱乐 每 日 算 法 挑 战 【第4期】

[Mr.K 018]

第4期来啦！

前排提示：本题涉及一点概率论，不难，也就高中水平

第4期 芜湖，起飞

 

本期的题目是在飞行棋的棋盘上展开的。棋盘可以想象成一列n个格子，从1到n编号。棋子从第1格开始，每一轮需要掷一枚均匀的6面骰子，取骰子的出目作为前进的格数。当棋子经过第n格（也就是最后一格时），不论是否刚好在这一格停下，就认为是胜利，游戏结束。特别地，棋盘上有若干“飞行通道”，双向连接两个不同编号的格子。若棋子停在了飞行通道的一端，就可以在这一步里直接移动到另一端，也可以选择不移动，直接结束本轮。

已知棋盘的格数n和飞行通道的情况，问从游戏开始到游戏结束，游戏轮数的期望是多少？

输入

有多组测试用例，请读取到文件尾。

每个用例的第一行是两个数n1≤n≤10⁵和k (1≤k≤10³)，分别表示格数和“飞行通道”的数量；
接下来有k行，每行有两个数a­_i和b_i，分别表示第i个飞行通道两个端点在第几格，满足1≤a­_i<b­_i≤n.

输出

对每个测试用例，输出一个小数占一行，表示游戏轮数的期望值，精确到小数点后4位。

 

后排召唤阵：

@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui

四月 13, 2020，由Mr.K 018修改

[Mr.K 018]

刚刚, sgszx 说道:

通道是双向的吗？还是固定从a->b？

双向

[Mr.K 018]

1 小时前, Muriya Tensei 说道:

那么对于飞行通道描述中的，可以选择飞也可以不飞，如何理解

首要的目的是快速通关还是 完全随机（那不就是1/2飞了么），如果为了快速通关，也不必要双向啊

玩家会选择尽可能快地通关。

四月 13, 2020，由Mr.K 018修改