i*r
2 楼
对进入前500名不抱啥期望。。。
c*e
7 楼
我在组建一支黑客小分队。我们应该讨论一下过去的问题。
v*a
8 楼
去TopCoder,把历年的题目做一遍,轻松应对FB的TopCoder
i*r
10 楼
如果加上time penalty
必须及时返回结果,否则无法计算罚时
必须及时返回结果,否则无法计算罚时
c*e
12 楼
Can anybody look at this problem? The answer seems different from mine. 我觉
得答案不对。
Facebook Hacker Cup 2011 Round 1A
First or Last
As a top driver in European racing circles, you find yourself taking more
than your fair share of risks. You go into every race knowing it may be your
last, but generally with the suspicion it won't be. Today, however, may
turn out to be different. The Fédération Internationale de l'Automobile
has sanctioned a new track in the Bernese Alps that may prove to be death of
anyone that dares brave its tight, awkwardly-banked turns and cliff-
adjacent straightaways.
Since you are a professional racing driver, you have considerable financial
backing and support in preparing for your first race on this new course. A
veritable consortium of physicists, software engineers, and drivers more
expendable than yourself have determined, for each corner on the track, the
probability of crashing during normal fast-paced driving and the probability
of crashing during an overtake maneuver. A single crash will end the race
for you. It is left to you to use this information to formulate your overall
racing strategy.
The race you will participate in will include R racers including yourself.
Given your history of apparently effortlessly cruising past all opponents to
victory, you will be starting at the rear of the pack to keep things
interesting. You must use your knowledge of the track to get to first place
by the time you have passed through the final turn. You can only overtake
opponents during a turn, so you must choose the R-1 turns during which to
overtake that will maximize your likelihood of finishing the race. This isn'
t the charitable sort of racing that awards accolades like "second place",
so your only goal here is to defeat every single opponent.
Input
Your input file will begin with a single integer N, the number of test cases
to follow, followed by a newline. Each test case begins with a single line
containing two integers, R as specified above and T, the number of turns on
the track. Following this will be T pairs of integers where the ith pair
represents the likelihood of crashing while overtaking and the likelihood of
crashing during normal driving, respectively during the ith turn. For each
of these integers p, consider the probability of the corresponding event to
be 1/p.
Output
Output, for each test case, the reduced fraction representing the
probability that you will win the race. Your outputs should be separated
only by whitespace.
Constraints
10 <= N <= 30
1 <= T <= 50
1 <= R < T
1 <= p <= 500
Example input
5
3 5 10 2 5 3 10 4 3 3 9 7
2 2 118 80 400 316
3 3 339 250 301 199 109 34
2 4 9 9 482 417 211 120 151 69
4 5 244 132 65 46 12 11 129 81 487 342
Example output
Case #1: 54/175
Case #2: 36855/37288
Case #3: 161352/164045
Case #4: 495040/566703
Case #5: 11435776/12904515
得答案不对。
Facebook Hacker Cup 2011 Round 1A
First or Last
As a top driver in European racing circles, you find yourself taking more
than your fair share of risks. You go into every race knowing it may be your
last, but generally with the suspicion it won't be. Today, however, may
turn out to be different. The Fédération Internationale de l'Automobile
has sanctioned a new track in the Bernese Alps that may prove to be death of
anyone that dares brave its tight, awkwardly-banked turns and cliff-
adjacent straightaways.
Since you are a professional racing driver, you have considerable financial
backing and support in preparing for your first race on this new course. A
veritable consortium of physicists, software engineers, and drivers more
expendable than yourself have determined, for each corner on the track, the
probability of crashing during normal fast-paced driving and the probability
of crashing during an overtake maneuver. A single crash will end the race
for you. It is left to you to use this information to formulate your overall
racing strategy.
The race you will participate in will include R racers including yourself.
Given your history of apparently effortlessly cruising past all opponents to
victory, you will be starting at the rear of the pack to keep things
interesting. You must use your knowledge of the track to get to first place
by the time you have passed through the final turn. You can only overtake
opponents during a turn, so you must choose the R-1 turns during which to
overtake that will maximize your likelihood of finishing the race. This isn'
t the charitable sort of racing that awards accolades like "second place",
so your only goal here is to defeat every single opponent.
Input
Your input file will begin with a single integer N, the number of test cases
to follow, followed by a newline. Each test case begins with a single line
containing two integers, R as specified above and T, the number of turns on
the track. Following this will be T pairs of integers where the ith pair
represents the likelihood of crashing while overtaking and the likelihood of
crashing during normal driving, respectively during the ith turn. For each
of these integers p, consider the probability of the corresponding event to
be 1/p.
Output
Output, for each test case, the reduced fraction representing the
probability that you will win the race. Your outputs should be separated
only by whitespace.
Constraints
10 <= N <= 30
1 <= T <= 50
1 <= R < T
1 <= p <= 500
Example input
5
3 5 10 2 5 3 10 4 3 3 9 7
2 2 118 80 400 316
3 3 339 250 301 199 109 34
2 4 9 9 482 417 211 120 151 69
4 5 244 132 65 46 12 11 129 81 487 342
Example output
Case #1: 54/175
Case #2: 36855/37288
Case #3: 161352/164045
Case #4: 495040/566703
Case #5: 11435776/12904515
c*e
13 楼
The first test case is
3 5 (10 2) (5 3) (10 4) (3 3) (9 7).
There are 3 contesters, including you. There are 5 corners. You need to
choose 2 (=3-1) corners to overtake the other 2 contesters.
The answer choose to normal driving at the 1st, 2nd, and 4th corner, but
over take at the 3rd and 5th. So the overall survival probability is 9/10 *
4/5 * 3/4 *
2/3 * 6/7 = 54/125 = 0.309.
However, based on my answer, you normal drives at 1st, 2nd, 3rd corner and
overtake at the 4th and 5th corner, the overall surival (winning)
probability is
9/10 * 4/5 * 9/10 * 2/3 * 6/7 = 324/875 = 0.370. This is greater than 54/125
=0.309.
So the Facebook answer is wrong! Anybody help?
your
of
【在 c**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: Can anybody look at this problem? The answer seems different from mine. 我觉
: 得答案不对。
: Facebook Hacker Cup 2011 Round 1A
: First or Last
: As a top driver in European racing circles, you find yourself taking more
: than your fair share of risks. You go into every race knowing it may be your
: last, but generally with the suspicion it won't be. Today, however, may
: turn out to be different. The Fédération Internationale de l'Automobile
: has sanctioned a new track in the Bernese Alps that may prove to be death of
: anyone that dares brave its tight, awkwardly-banked turns and cliff-
3 5 (10 2) (5 3) (10 4) (3 3) (9 7).
There are 3 contesters, including you. There are 5 corners. You need to
choose 2 (=3-1) corners to overtake the other 2 contesters.
The answer choose to normal driving at the 1st, 2nd, and 4th corner, but
over take at the 3rd and 5th. So the overall survival probability is 9/10 *
4/5 * 3/4 *
2/3 * 6/7 = 54/125 = 0.309.
However, based on my answer, you normal drives at 1st, 2nd, 3rd corner and
overtake at the 4th and 5th corner, the overall surival (winning)
probability is
9/10 * 4/5 * 9/10 * 2/3 * 6/7 = 324/875 = 0.370. This is greater than 54/125
=0.309.
So the Facebook answer is wrong! Anybody help?
your
of
【在 c**********e 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: Can anybody look at this problem? The answer seems different from mine. 我觉
: 得答案不对。
: Facebook Hacker Cup 2011 Round 1A
: First or Last
: As a top driver in European racing circles, you find yourself taking more
: than your fair share of risks. You go into every race knowing it may be your
: last, but generally with the suspicion it won't be. Today, however, may
: turn out to be different. The Fédération Internationale de l'Automobile
: has sanctioned a new track in the Bernese Alps that may prove to be death of
: anyone that dares brave its tight, awkwardly-banked turns and cliff-
a*d
14 楼
同问之前的starscraft的那个题
http://stackoverflow.com/questions/4701154/facebook-hacker-cup-
用-b/2a为什么testcase差了好几万?求教。
http://stackoverflow.com/questions/4701154/facebook-hacker-cup-
用-b/2a为什么testcase差了好几万?求教。
c*e
15 楼
M/2G may not be an integer. Also need to make sure M/2W is an integer.
The key point in this problem is that the integer is too big, and the
accuracy of double is not enough.
By the way, the Facebook answer looks wrong.
【在 a********d 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 同问之前的starscraft的那个题
: http://stackoverflow.com/questions/4701154/facebook-hacker-cup-
: 用-b/2a为什么testcase差了好几万?求教。
The key point in this problem is that the integer is too big, and the
accuracy of double is not enough.
By the way, the Facebook answer looks wrong.
【在 a********d 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 同问之前的starscraft的那个题
: http://stackoverflow.com/questions/4701154/facebook-hacker-cup-
: 用-b/2a为什么testcase差了好几万?求教。
i*r
16 楼
这题我也不是很理解
那两个数字里面,哪一个是超车的概率,哪一个是正常的概率,似乎题目没有说明白。
很不喜欢这种靠猜测题意的题目
*
【在 c**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: The first test case is
: 3 5 (10 2) (5 3) (10 4) (3 3) (9 7).
: There are 3 contesters, including you. There are 5 corners. You need to
: choose 2 (=3-1) corners to overtake the other 2 contesters.
: The answer choose to normal driving at the 1st, 2nd, and 4th corner, but
: over take at the 3rd and 5th. So the overall survival probability is 9/10 *
: 4/5 * 3/4 *
: 2/3 * 6/7 = 54/125 = 0.309.
: However, based on my answer, you normal drives at 1st, 2nd, 3rd corner and
: overtake at the 4th and 5th corner, the overall surival (winning)
那两个数字里面,哪一个是超车的概率,哪一个是正常的概率,似乎题目没有说明白。
很不喜欢这种靠猜测题意的题目
*
【在 c**********e 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: The first test case is
: 3 5 (10 2) (5 3) (10 4) (3 3) (9 7).
: There are 3 contesters, including you. There are 5 corners. You need to
: choose 2 (=3-1) corners to overtake the other 2 contesters.
: The answer choose to normal driving at the 1st, 2nd, and 4th corner, but
: over take at the 3rd and 5th. So the overall survival probability is 9/10 *
: 4/5 * 3/4 *
: 2/3 * 6/7 = 54/125 = 0.309.
: However, based on my answer, you normal drives at 1st, 2nd, 3rd corner and
: overtake at the 4th and 5th corner, the overall surival (winning)
i*e
17 楼
大家战况如何?
我是没戏了,第一道题边界情况没处理好,来不及改了。
我是没戏了,第一道题边界情况没处理好,来不及改了。
p*2
18 楼
上次不是有5000人通过预赛了吗?怎么这次才有一半人参加?
i*r
19 楼
第一题想了半天没啥好办法,写了个巨naive的程序
还好在6分钟之内跑完提交
还好在6分钟之内跑完提交
相关阅读
Bless xdjm who file H1 at the last day.[合集] experience with MS and Google[合集] Bloomberg Onsite Interview Question谈谈找工作(二)发现OPT start date确实可以顺延过grace periodH1-B和OPT同时申请的详细分析[合集] 亚马逊面食样题拿到Offer了,和大家share 一下我找工作的经验和感受Onsite经历之三:回答问题和Presentation[合集] 攒人品了!没有毕业证也可以办h1[合集] thankyou letter的subject大家都写啥H-1B ADV最新更新(07/26)之分析OPT办理教训,仅供参考.找工作的经历 公司清单 面试题 I(长篇)[合集] 通解Re: 前几天的概率题,自己算了一下:[合集] bloomberg的工作有意思么[合集] 谈谈加入ICC对个人的影响关于薪水的negotiate,个人意见,仅供参考攒人品了!没有毕业证也可以办h1[合集] 这个offer怎么样? Microsoft, Fresh CS PhD,硅谷