uva online judge self describing sequence problem solution python | uva 10049

The self describing sequence problem  (uva 10049) is also very straight forward and easy programming challenge in competitive programming once understood well. Which can be stated as (from online judge)

Solomon Golomb’s self–describing sequence ⟨f(1),f(2),f(3),...⟩ is the only nondecreasing sequence of positive integers with the property that it contains exactly f(k) occurrences of k for each k. A few moments thought reveals that the sequence must begin as follows:

n	1	2	3	4	5	6	7	8	9	10	11	12
f(n)	1	2	2	3	3	4	4	4	5	5	5	6

In this problem you are expected to write a program that calculates the value of f(n) given the value of n.

Sample Input

100 

9999 

123456 

1000000000 

0

Sample Output

21 

356 

1684 

438744

Programming Explanation

This is very simple problem states that for given range of n as input (as shown in above image), we have to find Golomb’s self–describing sequence.

Golomb’s self–describing sequence can be explained as : 

At position '1' value is 1, thus '1' repeated 1 time.

At position '2' value is 2, thus '2' repeated for 2 times.

At position '3' value is 2, thus '3' repeated for 2 times. 

At position '4' value is 3, thus '4' is repeated for 3 times and so on.

Code

size = int(input())

N, FN = list(), list()

for i in range(1, size+1):

    N.append(i)

i = 1

FN.append(1)

FN.append(2)

while(1):

    times = N[i]

    if (len(FN) > size):

        break

    for j in range(0,FN[i]):

        if (len(FN) > size):

            break

        FN.append(times)

    if(i==1):

        FN.remove(2)

    i+=1

print(N,"\n",FN)

Here, for each index value we add value at that index, index times. (value is 3 and index is 4, add 3 four times ) and obtain result.

Related keywords: self describing sequence, self describing sequence problem, self describing sequence problem solution, self describing sequence problem explanation, self describing sequence online judge, self describing sequence uva, self describing sequence solution python, self describing sequence source code, uva 10049, uva 10049 source code python, self describing sequence programming challenge.