c**********e
发帖数: 2007 | |
i******r
发帖数: 793 | |
c**********e
发帖数: 2007 | 3 为什么？你不是我景仰的大牛吗？我菜鸟一个，正在准备战斗呢。
【在 i******r 的大作中提到】
: 对进入前500名不抱啥期望。。。
|
i******r
发帖数: 793 | 4 ...........
我资格赛只过了一道题
【在 c**********e 的大作中提到】
: 为什么？你不是我景仰的大牛吗？我菜鸟一个，正在准备战斗呢。
|
p*****2
发帖数: 21240 | 5
过一道不久够了。
【在 i******r 的大作中提到】
: ...........
: 我资格赛只过了一道题
|
c**********e
发帖数: 2007 | 6 我也是。预选赛成绩不带入下一轮。
因为与第500名成绩相同的人就可以过，所以会不止500人。如果用这个规则，用预选赛
的成绩，会有2300人过关。
【在 i******r 的大作中提到】
: ...........
: 我资格赛只过了一道题
|
c**********e
发帖数: 2007 | 7 我在组建一支黑客小分队。我们应该讨论一下过去的问题。 |
v***a
发帖数: 365 | 8 去TopCoder，把历年的题目做一遍，轻松应对FB的TopCoder |
p*****2
发帖数: 21240 | 9
下一轮会用上time penalty吧？
【在 c**********e 的大作中提到】
: 我也是。预选赛成绩不带入下一轮。
: 因为与第500名成绩相同的人就可以过，所以会不止500人。如果用这个规则，用预选赛
: 的成绩，会有2300人过关。
|
i******r
发帖数: 793 | 10 如果加上time penalty
必须及时返回结果，否则无法计算罚时 |
|
|
c**********e
发帖数: 2007 | 11 下一轮（第一关)不用。第二关才用。
【在 p*****2 的大作中提到】
:
: 下一轮会用上time penalty吧？
|
c**********e
发帖数: 2007 | 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 |
c**********e
发帖数: 2007 | 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 的大作中提到】
: 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
发帖数: 195 | |
c**********e
发帖数: 2007 | 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 的大作中提到】
: 同问之前的starscraft的那个题
: http://stackoverflow.com/questions/4701154/facebook-hacker-cup-
: 用-b/2a为什么testcase差了好几万？求教。
|
i******r
发帖数: 793 | 16 这题我也不是很理解
那两个数字里面，哪一个是超车的概率，哪一个是正常的概率，似乎题目没有说明白。
很不喜欢这种靠猜测题意的题目
*
【在 c**********e 的大作中提到】
: 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
发帖数: 63 | 17 大家战况如何？
我是没戏了，第一道题边界情况没处理好，来不及改了。 |
p*****2
发帖数: 21240 | 18 上次不是有5000人通过预赛了吗？怎么这次才有一半人参加？ |
i******r
发帖数: 793 | 19 第一题想了半天没啥好办法，写了个巨naive的程序
还好在6分钟之内跑完提交 |
p*****2
发帖数: 21240 | 20
这么牛呀。我都没试过6分钟这么长时间。
【在 i******r 的大作中提到】
: 第一题想了半天没啥好办法，写了个巨naive的程序
: 还好在6分钟之内跑完提交
|
i******r
发帖数: 793 | 21 当然没有6分钟这么长。。。
只是我觉得自己的做法如果在服务器跑估计要超时
【在 p*****2 的大作中提到】
:
: 这么牛呀。我都没试过6分钟这么长时间。
|
