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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 同问之前的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 的大作中提到】
: 同问之前的starscraft的那个题
: http://stackoverflow.com/questions/4701154/facebook-hacker-cup-
: 用-b/2a为什么testcase差了好几万?求教。
i*r
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)
那两个数字里面,哪一个是超车的概率,哪一个是正常的概率,似乎题目没有说明白。
很不喜欢这种靠猜测题意的题目
*
【在 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
17 楼
大家战况如何?
我是没戏了,第一道题边界情况没处理好,来不及改了。
我是没戏了,第一道题边界情况没处理好,来不及改了。
p*2
18 楼
上次不是有5000人通过预赛了吗?怎么这次才有一半人参加?
i*r
19 楼
第一题想了半天没啥好办法,写了个巨naive的程序
还好在6分钟之内跑完提交
还好在6分钟之内跑完提交
相关阅读
Faculty On-Site后,多久会有消息啊?网上投简历的身份问题大家有没有生统得interview阿,是不是现在情况特别不好?请教一个题目服装问题请教关于export control authorization的申请请问现在还能申请去年10月份生效的H-1B么?有谁把LD招到自己组里的吗?有什么不好的影响? (转载)12月初寄出OPT申请的同学你们都approved了吗?(VSC)onsite 求祝福兼问问题12月递交的H1申请,现在还没有批怎么训练看bug的能力?要ON-SITE了Openning for entry level ASIC engineer一般F1能否通过security vetting process?master 毕业的gap?opt最多每周多少小时昨天面试MS招聘信息-职位方向:国内金融机构宏观经济学家,PhD required * (转载)下个月微软onsite~ 有疑问 求帮助与祝福