题目背景
Cool 非常喜欢妹子,以至于 Cool 在百度上有一个非常神奇的 ID 【雾】。
题目描述
Cool 现在搞清楚了女生宿舍的地形。女生宿舍是由很多栋楼构成的,它们可以被抽象成 20×20 的方格。
Cool 的妹子们所处的地方可以被表示为实数类型的坐标。当一个妹子 (x,y) 在楼 (i,j) 中,当且仅当 i≤x<i+1,j≤y<j+1,i,j∈Z。两个妹子之间有距离,当且仅当一个妹子所在的楼的横纵坐标均小于另一个妹子所在的楼,此时她们之间的距离为她们自身坐标的曼哈顿距离。
现在 Cool 要搞一个大统计:求 n 个妹子之间所有距离之和。
输入格式
为了避免输入文件过大无法上传在读入方面消耗过多时间,本题采取数据生成方案。
输入包含两行:
- 第一行,一个整数 n;
- 第二行,包含 6 个整数 rxa,rxc,rya,ryc,rza,rzc。
所有的实数都采用如下方式生成:
- 初始化 x=y=z=0;
- 重复以下过程:
- x=(y×rxa+rxc)modrp;
- y=(z×rya+ryc)modrp;
- z=(x×rza+rzc)modrp。
每次得到的实数即为 (xmod20)+(ymod10)÷10+(zmod10)÷100。rp=2333333。
第 i 个妹子将以第 2i−1 个生成实数为横坐标,第 2i 个生成实数为纵坐标。
输出格式
输出包含一行一个实数,表示 n 个妹子之间所有距离之和的平均值,保留 5 位小数。
提示
数据范围及约定
对于全部数据,保证 1≤n≤5×106。