Hmm, I wouldn't call that solution likeable. As someone already pointed out
(i think), the solution is basically a one-liner:
print 'Case #%d: %d' % (caseNo, ceil(log(ceil(log(P/L, C)), 2)))
>
>
Now this is short and pretty.
ps. if it's any relief, the one above was not my submitted solution either.
I almost had figured it with the two logarithms but being slow thinker could
not come with the proper rounding, so i just went brutal:
def getNumTests(l, p, c):
if l*c >= p:
return 0
else:
mid = (l*p) ** .5
return 1 + max(getNumTests(l, mid, c), getNumTests(mid, p, c))
And guess what, this is still very fast because turns out there will be only
about O(log2 logC P) recursions, so even for P=1e100 (1 googol ;-) ) there
will be only 10 invocations. ha!
- nas
On Sun, May 23, 2010 at 5:22 AM, AT <[email protected]> wrote:
> I liked my solution well enough to post it. It really makes sense this
> way.
>
> (in PYTHON):
>
> if L * C >= P: return 0
> count = 0
> while(True):
> count += 1
> P = P / C
> if L >= P: break
>
> return math.ceil(math.log(count,2))
>
>
>
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
