Hi,

I'm struggling with the problem ASCDFIB. I think I understood the principle concept (Fibbonacci and modulus). So i coded an approach using pre-generation of one period of fibonacci numbers. With this, all the code has to do is some apropriate slicing and ordering of the precalculated list.

""" SPOJ class. 15980. Ascending Fibonacci Numbers. Problem code: ASCDFIB """
##from __future__ import print_function
import sys
_MOD = 10**5
_PER = 15*10**4
_ALL = [0, 0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 5, 5, 5, 7, 8, 8, 9, 9, 9,
        11, 13, 13, 13, 15, 16, 16, 17, 17, 17, 19, 21, 21, 21, 23, 24, 24, 25,
        25, 25, 27, 29, 29, 29, 31, 32, 32, 33, 33, 33, 34, 34, 34, 34, 34, 34,
        34, 34, 35, 37, 37, 37, 39, 40, 40, 41, 41, 41, 43, 45, 45, 45, 47, 48,
        48, 49, 49, 49, 51, 53, 53, 53, 55, 56, 56, 57, 57, 57, 59, 61, 61, 61,
        63, 64, 64, 65]
def iter_fibos(num):
    fibos = [0] * num
    fibos[1] = 1
    for idx in range (2, num):
        fibos[idx] = (fibos[idx-1] + fibos[idx-2]) % _MOD
    return fibos
def calc_asc_fib(start, length, fibs):
    if length >= _PER:
        return _ALL
    start_relevant = start % _PER
    length_relevant = min(_PER, length)
    if start_relevant + length_relevant <= _PER:
        fibs_chosen = fibs[start_relevant-1:start_relevant+length_relevant]
    else:
        fibs_chosen = (fibs[:(start_relevant+length_relevant) % _PER] +
                        fibs[start_relevant-1:])
    fibs_chosen.sort()
    return fibs_chosen[:100]
def main():
    cases = sys.stdin.read().split('\n')
    output = sys.stdout.write
##    cases = [ c for c in cases if c]
    fibs = iter_fibos(_PER)
    results = []
    for num, line in enumerate(cases[1:]):
        start, length = map(int, line.split())
        res = calc_asc_fib (start, length, fibs)
        res = ' '.join(map(str, res))
        results.append('Case %d: %s' % (num+1, res))
    output('\n'.join(results))
    output('\n')
if __name__ == '__main__':
    main()

But I got TLE. With a little bit of optimization for large input values

##    if length >= _PER:
##        return _ALL

I got NZEC.

Any hints for optimization?
Regards
DaftWullie

Thank you very much for your checks and the immediate response.

I was somewhat astonished to read that my optimization is wrong but you're absolutely right. I must have been so happy to detect the period in the fib sequence that I jumped to this wrong conclusion. But understanding that I have to consider elements of the sequence outside its period makes it even worse when it comes to returning the 100 smallest elements ... Perhaps I need another data structure?

The read.split('\n') was my favourite since adjusting the input reading for some early i/o related problems at spoj and I have used it without (known) problems since then... Do you recommend to use sys.stdin.readlines()?

Now I got AC Although it was the very next attempt submitted, I had to perfom some rework on the code. The perfomance issue was solved (although not in the same magnitude as your submission) using a different sorting algorithm. Thanks again!