TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4249
  • 题目
  • P4249打气球
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1s
    问题描述

    周末何老板到磁器口游玩。街边有小贩在组织一种打气球游戏,何老板很感兴趣。
    店家立了一块布,布上画了N*N的方格,有的方格里挂上了气球,有的没有。
    游戏规则如下:
    第1步.观察。如果每一行都至少有一个方格没有气球,同时每一列都至少有一个方格没有气球,游戏结束。否则进行第2步。
    第2步.抛骰子。店家拿出一个特制的骰子,该骰子有N个面,上面依次有1到N这N个数字。玩家先后抛两次骰子,设第一次抛出的数字为x,设第二次抛出的为y (注:抛出的数字是随机的)。
    第3步.打气球。若坐标为(x,y)的格子里有气球,玩家必须将其打爆。子弹1块钱一发。如果该格子没有气球,忽略该格子,玩家不用开枪,但玩家也需要支付给店家1块钱。
    第4步.继续。执行第1步。

    何老板是个神枪手,他能做到百发百中。他想你帮他算算,对于当前给出的这局游戏,预计要花多少钱才能结束。

    输入格式

    第一行,两个整数n和m,n表示方格的尺寸,m表示游戏开始时,有m个格子里是没有气球的。
    接下来m行,每行两个整数x,y,表示坐标为x,y的格子里没有气球。

    输出格式

    一行,一个实数,完成游戏预计花费,保留2个小数位。

    样例输入 1

    5 2
    2 3
    4 1

    样例输出 1

    11.77

    样例输入 2

    2 2
    1 1
    1 2

    样例输出 2

    2.00

    样例输入 3

    1 1
    1 1

    样例输出 3

    0.00

    提示

    1 ≤ n ≤ 2*10^3
     0 ≤ m ≤ min(n^2, 2*10^4)
    1≤x,y≤n


    来源  改编自CF 398B