提示: 欢迎访问OurACM平台。
Problem 2257 Saya的小熊饼干

Accept: 52    Submit: 165
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Saya最近喜欢上了小熊饼干,但是他有非常严重的选择困难症,当然面对这一堆小熊饼干的时候,想起了一句至理名言“犹豫不决么? 那就来RAND()一下吧!”。

于是,Saya把小熊饼干排成了一个N*M的矩阵,每个位置上都放着一块小熊饼干。每当他想吃小熊饼干的时候,他就运行一下代码。(random()为生成一个任意正整数)。

x1=random() mod N+1;

y1=random() mod M+1;

x2=random() mod N+1;

y2=random() mod M+1;

然后将以(x1, y1),(x2, y2)为两个顶点的,四条边平行于边界的一个子矩形内的小熊饼干全部吃掉(两个点的连线为矩形的对角线,如果x1=x2或者y1=y2,则认为矩形的长度或宽度为1)。显然,如果某个位置上的小熊饼干已经被吃掉了,那Saya就什么都吃不到了。

在这题中,我们假定random()函数非常完美,得到每个格子的概率相等。

请你帮忙算一算,K次之内她期望可以吃到块小熊饼干?

Input

包含多组测试数据。

一行内包括三个正整数K,N,M。

0≤K≤10000,1≤N,M≤1000

Output

一个整数,K次之内期望可以吃到的小熊饼干块数(四舍五入精确到整数)。

Sample Input

1 3 3

Sample Output

4

Hint

对于样例简单的解释是这样的:在3*3的格子里取子矩形,取到1*1的方案数为9,取到1*2或2*1的方案数为24,取到1*3或3*1的方案数为12,取到2*2的方案数为16,取到2*3或3*2的方案数为16,取到3*3的方案数为4结果约为(1*9+2*24+3*12+4*16+6*16+9*4) / (9*9) = 3.5679,四舍五入后得4。

PS:最后Saya直接令x1=1,y1=1,x2=n,y2=m。

Source

福州大学第十四届程序设计竞赛_重现赛

Submit  Back  Status  Discuss