Участник:Novitskiy97/Ascending Fibonacci Numbers Python

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ASCDFIB/

Python (PyPy 2.7.13)

import sys
import re
 
text = sys.stdin.read()
text_splited = re.findall('\d+', text)
all_input_numbers = list(map(int, text_splited))
all_input_numbers.reverse()
 
f = [0] * 1100011
 
MAXN = 1100011
mod = 100000
f[0] = 1
f[1] = 0
for i in range(2, MAXN):
    f[i] = (f[i-1] + f[i-2]) % mod
 
memory = [] # memory[i] -- counts of F[j], j from 0 to (i+1) * mod - 1
A = [0] * mod
 
for i in range(1, MAXN):
    if i % mod == 0:
        memory.append(A[:])
    A[f[i]] += 1
 
def Print(a): # a[i] -- how many times need to print i
    counter = 0
    for i in range(mod):
        for j in range(a[i]):
            counter += 1
            print(i),
            if counter >= 100:
                print('')
                return
    print('')
 
def simple_count(A, B):
    a = [0] * mod
    for i in range(A, B+1):
        a[f[i]] += 1
    return a
 
def count(A, B, trace=False):
    l_block = A // mod
    r_block = B // mod
    if (r_block - l_block <= 1):
        Print(simple_count(A, B))
        return
 
    l = simple_count(A, mod - 1) 
    r = simple_count((B // mod) * mod, B)
    ml = memory[l_block]
 
    mr = memory[r_block - 1]
    z = [l[i] + r[i] + mr[i] - ml[i] for i in range(mod)]
    Print(z)
    return
 
 
t = all_input_numbers.pop()
for i in range(t):
    a0 = all_input_numbers.pop()
    a1 = all_input_numbers.pop()
    print('Case %d:' % (i + 1)),
    count(a0, a0+a1)