- Problem A (Osmos):
- Small Set: 4668/7250 users (64%)
- Large Set: 3537/4578 users (77%)
- Problem B (Falling Diamonds):
- Small Set: 952/1882 users (51%)
- Large Set: 525/724 users (73%)
- Problem C (Garbled Email):
- Small Set: 444/896 users (50%)
- Large Set: 255/345 users (74%)
More information are on go-hero.net.
Osmos
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def howBigDoIget(A, motes):
while len(motes) > 0 and A > min(motes):
A += min(motes)
motes.remove(min(motes))
return A
def stepsNeededForNext(A, motes):
m = min(motes)
steps = 0
if m >= 1 and A == 1:
return 10 ** 12
while A <= m:
A += A - 1
steps += 1
return steps
def solve(A, motes):
steps = 0
A = howBigDoIget(A, motes)
while len(motes) > 0 and A <= max(motes):
if stepsNeededForNext(A, motes) >= len(motes):
steps += len(motes)
return steps
else:
A += A - 1
A = howBigDoIget(A, motes)
steps += 1
return steps
if __name__ == "__main__":
testcases = input()
for caseNr in range(1, testcases + 1):
A, N = map(int, raw_input().split(" "))
motes = sorted(map(int, raw_input().split(" ")))
copyed = motes[:]
solution = solve(A, motes)
if solution > N:
solution = N
print("Case #%i: %s" % (caseNr, solution))
Falling Diamonds
Once you've read the task, you should understand some very basic ideas:
- First of all, diamonds only fall at $x=0$ !
- If your target coordinates are $(x,y)$ , you have the same output as for $(-x,y)$ , as everything is symmetric.
- You have to get a basis for your diamonds pyramid. I've colored the basis in yellow in the images below.
- When your target is above the ground, you can let the diamond slide down to calculate the size of the basis.
Note that you don't have to calculate a probabilty for the yellow pyramids. You get those with probability of 1.
What I've forgot: You should also catch the case that you can fill up the next bigger pyramid. If this is possible, you can guarantee that you will reach your target \((x,y)\).
The rest is simple math. You have \(rest\) diamonds left after you've build the base (yellow). Then you need \(y+1\) diamonds slide to the right side. The probability that you have exactly \(k\) hits while making \(N\) tries with a probability of 50% is \(\binom{N}{k} \cdot (\frac{1}{2})^N\). You want at least \(k\) hits, so you want \(\sum_{i=k}^N \binom{N}{i} \cdot (\frac{1}{2})^N\).
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import gmpy
""" Calculate the binomial coefficient """
def binomial(n, k):
return gmpy.comb(n, k)
def solve(N, x, y):
"""
@param N: Number of diamonds
@param x,y: Target coordinate
@return: possiblity, that a diamond will be at coordinate (x,y)
"""
if x == 0:
n = y + 1
if N >= (n * n + n) / 2:
return 1.0
else:
return 0.0
# From this point, x != 0 is True
xTmp = x + y # let target slide down
n = xTmp - 1
baseDiamands = (n ** 2 + n) / 2
# are there enough diamonds left after you've build the basis?
rest = N - baseDiamands
if rest <= 0:
return 0.0
# are there enough diamonds left so that you can guarantee that
# you will fill up the next bigger pyramid at least to the
# target position?
biggerBaseDiamonds = baseDiamands + n + 2 + y
if N >= biggerBaseDiamonds:
return 1.0
# some math:
# bernoulli
prob = 0.0
hitsNeeded = y + 1
for k in range(hitsNeeded, rest + 1):
prob += binomial(rest, k)
return prob / 2 ** rest
if __name__ == "__main__":
testcases = input()
for caseNr in range(1, testcases + 1):
N, x, y = map(int, raw_input().split(" "))
print("Case #%i: %.9Lf" % (caseNr, solve(N, abs(x), y)))