w*******x
发帖数: 489 | 1 这个上面的：
http://www.codechef.com/MARCH12/problems/CIELQUAK
2x2,2x3的手算很容易。给出的那个例子7x7，就感觉没解析解了。只能MC吗，这题？10
^18x8这么大的怎么搞？
code run 的时间限制８秒。
The country in which Chef Ciel lives has many earthquakes. Since Ciel's
restaurant is far away from an evacuation center, Ciel is afraid of
earthquakes. So, Ciel would like to know the probability that Ciel can reach
from Ciel's restaurant to the evacuation center when an earthquake occurs.
Your task is calculating the probability under the following assumptions.
Ciel's city has R*C junctions (i, j) for 1 ≤ i ≤ R, 1 ≤ j ≤ C. There is
a two-way road between the junctions (r1, c1) and (r2, c2) if and only if |
r1 - r2| + |c1 - c2| = 1. When an earthquake occurs, each road is destroyed
with probability p, and these events are statistically independent of each
other. Ciel's restaurant is in the junction (1, 1), and the evacuation
center is in the junction (R, C). Ciel only considers a big earthquake, so
you can assume that p is not less than 0.1.
Input
The first line contains an integer T, the number of test cases. Then T test
cases follow. Each test case has 3 numbers R, C and p, where R and C are
integers.
Output
For each test case output the required probability. Your answer must have an
absolute error no more than 0.000001 (10-6).
Constraints
1 ≤ T ≤ 50
1 ≤ R ≤ 8
1 ≤ C ≤ 1000000000000000000 (10^18)
0.1 ≤ p ≤ 1
p has at most four digits after the decimal point.
Sample Input
5
2 2 0.5
3 2 0.7
2 3 0.7
1 1 0.2
7 7 0.8
Sample Output
0.4375
0.0768204
0.0768204
1
0.000003962379607 |
P*****s
发帖数: 758 | 2 太难了吧，cf上面只有三个成功提交的，其中一个还是楼教主。。。 |
w*******x
发帖数: 489 | 3 对啊对啊 所以说出个难题 可以多想想。
我想了会没什么idea，觉得这个题还挺有意思的，放这里看这里有牛人能提示提示我不
【在 P*****s 的大作中提到】
: 太难了吧，cf上面只有三个成功提交的，其中一个还是楼教主。。。
|
A**u
发帖数: 2458 | 4 喔
你经常做这类题目？
和面试题目比，有什么好处呢
topcoder也好多这样题目 |
P*****s
发帖数: 758 | 5 都是各种算法题目吧，有空玩玩还不错，
不过LZ这个题目难度有点大。。。
CF都是阿三，排名还分开，看着不爽
【在 A**u 的大作中提到】
: 喔
: 你经常做这类题目？
: 和面试题目比，有什么好处呢
: topcoder也好多这样题目
|
C***m
发帖数: 120 | 6 我觉得可能是用递归的想法来做，coding的时候注意保存计算过的结果。
【在 w*******x 的大作中提到】
: 对啊对啊 所以说出个难题 可以多想想。
: 我想了会没什么idea，觉得这个题还挺有意思的，放这里看这里有牛人能提示提示我不
|
w*******x
发帖数: 489 | 7 以前准备面试之前做比较多，topcoder，google cod jam都有做做
很多题目出的很好
和面试题目比更有意思吧，当然面试题也有很有意思的
对算法非常有帮助
【在 A**u 的大作中提到】
: 喔
: 你经常做这类题目？
: 和面试题目比，有什么好处呢
: topcoder也好多这样题目
|
P*****s
发帖数: 758 | 8 实际面试题我感觉一般没有这些难。。。
【在 w*******x 的大作中提到】
: 以前准备面试之前做比较多，topcoder，google cod jam都有做做
: 很多题目出的很好
: 和面试题目比更有意思吧，当然面试题也有很有意思的
: 对算法非常有帮助
|
A***d
发帖数: 25 | 9 大牛，那实际面试题都是什么难度呢？有没有好的推荐参考书？谢谢！
【在 P*****s 的大作中提到】
: 实际面试题我感觉一般没有这些难。。。
|
Q*T
发帖数: 263 | 10 状态数增长太快了。试了一下暴力递归，4x4用了十多秒，7x7就不用想了。
肯定有提高的余地，不过除非有很好的trick，感觉没啥希望。
Monte Carlo的话，要达到10^-6的精度貌似也不容易
【在 C***m 的大作中提到】
: 我觉得可能是用递归的想法来做，coding的时候注意保存计算过的结果。
|
C***m
发帖数: 120 | 11 我很傻，开始想得太简单了。请不要把那个评论当回事
【在 Q*T 的大作中提到】
: 状态数增长太快了。试了一下暴力递归，4x4用了十多秒，7x7就不用想了。
: 肯定有提高的余地，不过除非有很好的trick，感觉没啥希望。
: Monte Carlo的话，要达到10^-6的精度貌似也不容易
|
k*****y
发帖数: 744 | 12 Looks like an interesting problem.
I am thinking of using connected components on each ending Coloumn as states
(about 4k states for all decomposition into subsets for 8 elements), then
one might possibly figure out the transition matrix(though it still looks
hard to do it).
Then the problem should reduce to a Markov problem(calculating power
matrices?), using binary search for 10^18 should not be a problem though.
Actually there are further restrictions on the states, hopefully the number
of states can be reduced greatly.
Any other suggestions to the problem? Thanks.
10
reach
.
【在 w*******x 的大作中提到】
: 这个上面的：
: http://www.codechef.com/MARCH12/problems/CIELQUAK
: 2x2,2x3的手算很容易。给出的那个例子7x7，就感觉没解析解了。只能MC吗，这题？10
: ^18x8这么大的怎么搞？
: code run 的时间限制８秒。
: The country in which Chef Ciel lives has many earthquakes. Since Ciel's
: restaurant is far away from an evacuation center, Ciel is afraid of
: earthquakes. So, Ciel would like to know the probability that Ciel can reach
: from Ciel's restaurant to the evacuation center when an earthquake occurs.
: Your task is calculating the probability under the following assumptions.
|
