#!/usr/bin/env python3

u0 = 42
a = 46613
b = 17
m = (2**31) - 1

u = [u0]
for i in range(6000000):
    u.append( (a * u[-1] + b) % m )


def q1(n):
    return str(u[n]%1000)

print("Q1 : "+(q1(1))+" "+q1(98)+" "+q1(9876))


#### Q1 / Q2


def B(n,k,alpha):
    return [u[alpha*i]%n+1 for i in range(k) ]

def capacite(l):
    res = 0
    for i in l:
        res += i
    return res

b1 = B(9,5,13)
b2 = B(98,54,17)
b3 = B(987,543,41)
b4 = B(98765,54321,97)

print("Q2 : "+str(capacite(b1))+" "+str(capacite(b2))+" "+str(capacite(b3))+" "+str(capacite(b4)))


#### Q2 / Q3

def premier(b,l):
    for i in range(len(l)):
        if b<=l[i]:
            return i
    return -1

print("Q3 : "+str(premier(9,b1))+" "+str(premier(86,b2))+" "+
             str(premier(975,b3))+" "+str(premier(98123,b4)))


#### Q3 / Q4

def domineJusqua(l1,l2):
    id1 = 0
    for id2 in range(len(l2)):
        while id1<len(l1) and l1[id1]<l2[id2]:
            id1+=1
        if id1==len(l1):
            return id2
        id1 += 1
    return len(l2)

print("Q4 : "+str(domineJusqua(b1,B(9,10,14)))
         +" "+str(domineJusqua(b2,B(98,68,43)))
         +" "+str(domineJusqua(b3,B(987,673,174)))
         +" "+str(domineJusqua(b4,B(98765,65431,81))))


#### Q4 / Q5

def capaciteL(n):
    if n <= 1:
        return n
    return capaciteL(n//2)+n+capaciteL(n-1-(n//2))
    
print("Q5 : "+str(capaciteL(6))
         +" "+str(capaciteL(987))
         +" "+str(capaciteL(98765))
         +" "+str(capaciteL(9876543)))

#### Q5 / Q6

def index_lexi(l, capa):
    before = 0
    for v in l:
        if capa < v:
            return -1
        before += 1+2**capa-2**(capa-v+1)
        capa -= v
    return before

b5 = B(2,4,13)
b6 = B(3,6,17)
b7 = B(3,8,41)
b8 = B(5,8,97)

print("Q6 : "+str(index_lexi(b5,7))
         +" "+str(index_lexi(b6,15))
         +" "+str(index_lexi(b7,20))
         +" "+str(index_lexi(b8,25)))

#### Q6 / Q7

k_parmi_n = [ [1]*1000 ]

for k in range(999):
    k_parmi_n.append([0]*1000)
    for n in range(999):
        k_parmi_n[k+1][n+1] = k_parmi_n[k][n]+k_parmi_n[k+1][n]

def index_size_lexi(l, capa):
    
    before = 1
    # d'abord compter les sequences plus petites:
    for s in range(1,len(l)):
        for c in range(s,capa+1):
            before += k_parmi_n[s-1][c-1]

    for i in range(len(l)):
        if capa < l[i]:
            return -1
        restant = len(l)-1-i
        if restant == 0:
            before += l[i]-1
        else:
            for pose in range(1,l[i]):
                for capa2 in range(restant,capa-pose+1):
                    before += k_parmi_n[restant-1][capa2-1]
        capa -= l[i]
    return before

b5 = B(2,4,13)
b6 = B(3,6,17)
b7 = B(3,8,41)
b8 = B(5,8,97)

print("Q7 : "+str(index_size_lexi(b5,7))
         +" "+str(index_size_lexi(b6,15))
         +" "+str(index_size_lexi(b7,20))
         +" "+str(index_size_lexi(b8,25)))



#### Q7 / Q8


def somme(l1,l2):
    return [l1[i]+l2[i] for i in range(len(l1))]

def diff(l1,l2):
    return [l1[i]-l2[i] for i in range(len(l1))]

def filtre(l):
    return [max(1,e) for e in l]

def universelle(n):
    if n == 0:
        return []
    
    return universelle(n//2)+[n]+universelle(n-(n//2)-1)

b9 = filtre(
    somme(universelle(16),
          diff(
              B(8,16,13),
              B(10,16,14))))

b10 = filtre(
    somme(universelle(67),
          diff(
              B(13,67,15),
              B(18,67,16))))

b11 = filtre(
    somme(universelle(678),
          diff(
              B(21,678,17),
              B(24,678,18))))

b12 = filtre(
    somme(universelle(987),
          diff(
              B(72,987,19),
              B(68,987,20))))



def max_universelle(l):
    dyn = [0]+[0 for _ in l]
    maxi = []
    length = len(l)
    for pos in range(len(l)-1,-1,-1):
        univ_for = length-pos
        while len(maxi)>0 and l[maxi[-1]] <= l[pos]:
            del maxi[-1]
        maxi.append(pos)
        maxi_id = len(maxi)-1
        v = 1
        while v <= univ_for:
            while maxi_id >= 0 and v>l[maxi[maxi_id]]:
                maxi_id -= 1
            if maxi_id < 0:
                univ_for -= 1
            else:
                univ_for = min(univ_for,dyn[maxi[maxi_id]+1]+v)
            v+=1
        dyn[pos]=univ_for
    return dyn[0]

print("Q8 : "+str(max_universelle(b9))
         +" "+str(max_universelle(b10))
         +" "+str(max_universelle(b11))
         +" "+str(max_universelle(b12)))


def max_universelle(l):
    suffixe_univ = [0]*(len(l)+1)
    length = len(l)
    for pos in range(len(l)-1,-1,-1):
        # le suffixe de longeur length-pos est
        # au plus universel pour length-pos
        univ_for = length-pos
    
        pose = 1
        # La variable univ_for va contenir la valeur maximale
        # pour laquelle le suffixe courant est n-universel
        # Si univ_for est à la bonne valeur alors pour chaque
        # suite qui commence par 0 < pose <= univ_for on peut
        # construire une suite qui pose ``pose'' le plus tôt
        # possible puis qui construit ensuite unesuite
        # (univ_for-pose)-universelle.

        # ou_poser va contenir le plus petit indice supérieur à pos
        # tel que l[ou_poser] >= pose
        ou_poser = pos
        
        while pose <= univ_for: # on teste toues les valeurs
        
            #on trouve un endroit où poser la valeur pose
            while ou_poser < len(l) and pose>l[ou_poser]:
                ou_poser += 1
            
            # si ou_poser == len(l) cela veut dire que l'on a pas trouvé
            # et qu'il faut diminuer l'ambition de univ_for à pose-1
            if ou_poser == len(l):
                univ_for = pose-1
            else:
                # on doit maintenant vérifier qu'après l'endroit
                # où ``pose'' est placé on ait bien un suffixe
                # (univ_for-pose)-universel
                # Si non, on en déduit une nouvelle borne
                # pour univ_for
                univ_for = min(univ_for,
                               suffixe_univ[ou_poser+1]+pose)
            pose += 1 
        suffixe_univ[pos]=univ_for
    return suffixe_univ[0]

print("Q8 : "+str(max_universelle(b9))
         +" "+str(max_universelle(b10))
         +" "+str(max_universelle(b11))
         +" "+str(max_universelle(b12)))


#### Q8 / Q9

import sys
sys.setrecursionlimit(50000)

def nb_domin_rec(l1,l2):
    memo = [ [None for _ in l2] for _ in l1]
    modulo = 10**6

    def nb(i,j):
        if j==len(l2):
            return 1
        if i==len(l1):
            return 0

        if memo[i][j] == None:
            memo[i][j] = nb(i+1,j)
            if l1[i]>=l2[j]:
                memo[i][j] += nb(i+1,j+1)
            memo[i][j] %= modulo 
                
        return memo[i][j]

    
    return nb(0,0)



def nb_domin_dyn(l1,l2):
    nb = [ [0 for _ in range(1+len(l2))] for _ in range(1+len(l1))]
    modulo = 10**6

    nb[0][0]=1
    for j in range(len(l2)):
        for i in range(len(l1)):
            if l1[i] >= l2[j]:
                nb[i+1][j+1] = (nb[i+1][j+1]+nb[i][j])%modulo
            nb[i+1][j] = (nb[i+1][j]+nb[i][j])%modulo
    
            
    return nb[len(l1)][len(l2)]


def nb_domin_fast(l1,l2):

    cur = [ 0 for _ in range(1+len(l1))]
    modulo = 10**6

    cur[0]=1
    for v in l2:
        nxt = [ 0 for _ in cur]
        for i in range(len(l1)):
            if l1[i] >= v:
                nxt[i+1] = cur[i]
            cur[i+1] = (cur[i]+cur[i+1])%modulo
        cur = nxt
            
    return sum(cur)%modulo


print("Q9 :"
         +" "+str(nb_domin_fast(b1,B(5,3,42)))
         +" "+str(nb_domin_fast(b2,B(69,23,43)))
         +" "+str(nb_domin_fast(b3,B(789,145,174)))
         +" "+str(nb_domin_fast(B(98765,5432,97),B(56789,1234,81))))