钉子和小球
Time Limit:1000MS Memory Limit:10000K
Total Submit:577 Accepted:168
Description
有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。
让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落，小球每碰到一个钉子都可能落向左边或右边（概率各1/2），且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。
我们知道小球落在第i个格子中的概率pi=pi=
，其中i为格子的编号，从左至右依次为0,1,...,n。
现在的问题是计算拔掉某些钉子后，小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。
Input
第1行为整数n（2 <= n <= 50）和m（0 <= m <= n）。以下n行依次为木板上从上至下n行钉子的信息，每行中'*'表示钉子还在，'.'表示钉子被拔去，注意在这n行中空格符可能出现在任何位置。
Output
仅一行，是一个既约分数(0写成0/1)，为小球落在编号为m的格子中的概pm。既约分数的定义：A/B是既约分数，当且仅当A、B为正整数且A和B没有大于1的公因子。
Sample Input
5 2
*
* .
* * *
* . * *
* * * * *
Sample Output
7/16
Source
Noi 99
#include
<
iostream
>
#include
<
string
>
using
namespace
std;
struct
FMDATA
{
__int64 a, b;
}
;
__int64 gcd(__int64 a, __int64 b)
{
if
(b
==
0
)
return
a;
else
return
gcd(b, a
%
b);
}
__int64 lcm(__int64 a, __int64 b)
{
if
(a
==
0
||
b
==
0
)
return
0
;
else
if
(a
>
b)
return
a
/
gcd(a,b)
*
b;
else
return
b
/
gcd(a,b)
*
a;
}
__int64 add(FMDATA t1, FMDATA t2, FMDATA
&
result)
{
__int64 t;
result.b
=
lcm(t1.b, t2.b);
result.a
=
result.b
/
t1.b
*
t1.a
+
result.b
/
t2.b
*
t2.a;
t
=
gcd(result.a, result.b);
result.b
/=
t;
result.a
/=
t;
return
0
;
}
int
main()
{
char
c[
100
][
100
];
char
enter[
10001
];
FMDATA dp[
100
][
100
];
FMDATA tmp1, tmp2, tmp3;
__int64 i, j, k, t, p, q;
__int64 n, m;
while
(scanf(
"
%I64d%I64d
"
,
&
n,
&
m)
!=
EOF)
{
gets(enter);
for
(i
=
1
; i
<=
n; i
++
)
{
gets(enter);
k
=
1
;
for
(j
=
0
; j
<
strlen(enter); j
++
)
{
if
(enter[j]
==
'
*
'
||
enter[j]
==
'
.
'
)
c[i][k
++
]
=
enter[j];
}
}
for
(i
=
1
; i
<=
n
+
1
; i
++
)
c[n
+
1
][i]
=
'
*
'
;
for
(i
=
1
; i
<=
n
+
1
; i
++
)
{
for
(j
=
1
; j
<=
i; j
++
)
{
dp[i][j].a
=
0
;
dp[i][j].b
=
1
;
}
}
for
(i
=
1
; i
<=
n; i
+=
2
)
{
t
=
(i
+
1
)
/
2
;
if
(c[i][t]
==
'
*
'
)
{
dp[i][t].a
=
1
;
break
;
}
}
k
=
i;
if
(i
>
n)
{
if
((n
+
2
)
/
2
==
m
+
1
)
printf(
"
1/1\n
"
);
else
printf(
"
0/1\n
"
);
continue
;
}
for
(i
=
k
+
1
; i
<=
n
+
1
; i
++
)
{
for
(j
=
1
; j
<=
i; j
++
)
{
tmp1.a
=
0
;
tmp1.b
=
1
;
if
(i
-
1
>=
1
&&
j
<=
i
-
1
&&
j
>=
1
&&
c[i
-
1
][j]
==
'
*
'
)
{
tmp1.a
=
dp[i
-
1
][j].a;
tmp1.b
=
dp[i
-
1
][j].b
*
2
;
}
tmp2.a
=
0
;
tmp2.b
=
1
;
if
(i
-
1
>=
1
&&
j
-
1
<=
i
-
1
&&
j
-
1
>=
1
&&
c[i
-
1
][j
-
1
]
==
'
*
'
)
{
tmp2.a
=
dp[i
-
1
][j
-
1
].a;
tmp2.b
=
dp[i
-
1
][j
-
1
].b
*
2
;
}
add(tmp1, tmp2, dp[i][j]);
tmp3.a
=
0
;
tmp3.b
=
1
;
if
(i
-
2
>=
1
&&
j
-
1
<=
i
-
2
&&
j
-
1
>=
1
&&
c[i
-
2
][j
-
1
]
==
'
.
'
)
{
tmp3.a
=
dp[i
-
2
][j
-
1
].a;
tmp3.b
=
dp[i
-
2
][j
-
1
].b;
}
add(tmp3, dp[i][j], dp[i][j]);
}
}
printf(
"
%I64d/%I64d\n
"
, dp[n
+
1
][m
+
1
].a, dp[n
+
1
][m
+
1
].b);
}
system(
"
pause
"
);
return
0
;
}
posted on 2006-08-29 14:00
豪 阅读(472)
评论(0) 编辑 收藏 引用 所属分类:
ACM题目