Codeforces: A. Double Cola

The problem is from codeforces http://www.codeforces.com/problemset/problem/82/A

This is interesting because it seems like those guys thing: acting strange. This problem can be transformed into the following: 12345 1122334455 11112222333344445555 …. find the n-th value of the infinite sequence. If you check carefully, there is a pattern with this sequence. The number of each new component is 5, 10, 20, 40 …. The number of each number’s appearance in the component is 1, 2, 4, 8, 16 … If you notice this, you will have a solution soon.

The solution is to simulate this sequence and find out which component the n-th item lies in. If you know which component, you can easily compute the exact value.

The python solution is below. It is accepted within the time scale (60ms, maximum allowed 2 seconds) because the numbers grow exponentially. The complexity is roughly O(log5(n)) which is acceptable. However, I believe there is another solution which is purely mathematical. You could compute which component directly without loops. I leave it to you guys.

from math import ceil

names = ['Sheldon', 'Leonard', 'Penny', 'Rajesh', 'Howard']

n = int(raw_input())

i = 0
j = 1
k = len(names)

while i <= n:
    i += k
    k += k
    j += j

print names[int(ceil((n - (i - k * 0.5)) / (j * 0.5)) - 1)]

–EOF (The Ultimate Computing & Technology Blog) —