#!/usr/bin/python3

u0=42

#
# Q1
#

maxn = 1000000
_u = [0] * maxn
_u[0] = u0
for i in range(1,maxn):
    _u[i] = (19999999 * _u[i-1]) % 19999981

def u(n):
    return _u[n]

print("1.a %d" % (u(123) % 1000))
print("1.b %d" % (u(456) % 1000))
print("1.c %d" % (u(789) % 1000))

#
# Q2
#

def v(t, p):
    if u(t) % 10000 < p:
        return 1
    else:
        return 0

def nbaretes(n, p):
    s = 0
    for i in range((n-1)*n//2):
        s += v(i, p)
    return s

print("2.a %d" % (nbaretes(10,654)))
print("2.b %d" % (nbaretes(100,543)))
print("2.c %d" % (nbaretes(1000,12)))


def gnp(n,p):
    g = [ [] for i in range(n) ]
    t = 0
    for i in range(n):
        for j in range(i+1,n):
            if v(t, p):
                g[i].append(j)
                g[j].append(i)
            t += 1
    return g

def nbaretes2(g):
    s = 0
    for i in g:
        s += len(i)
    return s

g1 = gnp(10,654)
g2 = gnp(100,543)
g3 = gnp(1000,12)
# On peut vérifier que l'on obtient les mêmes résultats
#print("2.a %d" % (nbaretes2(gnp(10,654))))
#print("2.b %d" % (nbaretes2(gnp(100,543))))
#print("2.c %d" % (nbaretes2(gnp(1000,12))))

#
# Q3
#

def nbconnexe0(g):
    # Marquage des sommets
    m = [ False ] * len(g)
    m[0] = True
    cur = [ 0 ]
    n = 1
    while cur != []:
        s = cur.pop()
        for t in g[s]:
            if not m[t]:
                n += 1
                m[t] = True
                cur.append(t)
    return n

print("3.a %d" % (nbconnexe0(g1)))
print("3.b %d" % (nbconnexe0(g2)))
print("3.c %d" % (nbconnexe0(g3)))

#
# Q4
#

def nbconnexes(g):
    # Marquage des sommets
    m = [ False ] * len(g)

    def nonmarque(start):
        """Trouver un sommet non marqué à partir du sommet 'start'"""
        for i in range(start,len(m)):
            if not m[i]:
                return i
        return None

    def marqueconnexe(start):
        """Marquer la composante connexe contenant 'start'"""
        m[start] = True
        cur = [ start ]
        while cur != []:
            s = cur.pop()
            for t in g[s]:
                if not m[t]:
                    m[t] = True
                    cur.append(t)

    n = 0
    start = 0
    while start != None:
        n += 1
        marqueconnexe(start)
        start = nonmarque(start+1)
    return n
    
print("4.a %d" % (nbconnexes(g1)))
print("4.b %d" % (nbconnexes(g2)))
print("4.c %d" % (nbconnexes(g3)))

#
# Q5
#

def gnp2(n,p):
    g = gnp(n,p)
    for i in range(len(g)-1):
        if i+1 not in g[i]:
            g[i].append(i+1)
            g[i+1].append(i)
    return g

def glouton(g, k):
    n = len(g)
    # Pièces trouvées
    pieces = [ False ] * k

    def trouvepiece(s):
        """Trouve la pièce la plus proche de s
        retourne le nombre de pas et le sommet d'arrivée"""
        m = [ False ] * n
        m[s] = True
        cur = [s]
        small_steps = 0
        min_piece = n
        while cur != []:
            small_steps += 1
            newcur = []
            for s in cur:
                for t in g[s]:
                    if m[t]:
                        # Sommet déjà visité
                        continue
                    if t >= n-k and not pieces[t - (n-k)]:
                        # On a trouvé une nouvelle pièce !
                        if t < min_piece:
                            min_piece = t
                    else:
                        # Il n'y a pas de pièce
                        m[t] = True
                        newcur.append(t)
            if min_piece < n:
                # On a trouvé au moins une pièce, on y va
                pieces[min_piece-(n-k)] = True
                return small_steps, min_piece
            cur = newcur

        # Toutes les pièces sont atteignables
        assert(False)

    start = 0
    steps = 0
    for trouve in range(k):
        small_steps,start = trouvepiece(start)
        steps += small_steps

    return steps

g1 = gnp2(100,32)
g2 = gnp2(200,21)
g3 = gnp2(1000,1)
print("5.a %d" % (glouton(g1,10)))
print("5.b %d" % (glouton(g2,15)))
print("5.c %d" % (glouton(g3,20)))

#
# Q6
#

def distances(g):
    n = len(g)

    dist = [ [ None for i in range(n) ] for j in range(n) ]

    def distance(orig):
        m = [False] * n
        m[orig] = True
        cur = [orig]
        d = 0
        while cur != []:
            d += 1
            newcur = []
            for s in cur:
                for t in g[s]:
                    if m[t]:
                        # déjà visité
                        continue
                    dist[orig][t] = d
                    m[t] = True
                    newcur.append(t)
            cur = newcur

    for s in range(n):
        distance(s)

    return dist

def optim(g, k):
    n = len(g)

    dist = distances(g)

    # On mémoise les résultats, en indiçant par le sommet contenant une
    # pièce duquel on part et l'ensemble des pièces déjà collectées,
    # encodées en binaire
    t = [ [ None ] * (1<<k) for i in range(k) ]
    for i in range(k):
        # Cas de base: on a collecté toutes les pièces
        t[i][(1<<k)-1] = 0

    def parcours_depuis(s,i):
        """Calcule le nombre optimal de mouvements à partir du sommet 's' et en
        ayant déjà collectés les pièces encodées dans 'i'"""
        # mémoisation
        if s != 0 and t[s-(n-k)][i] != None:
            return t[s-(n-k)][i]

        dmin = None
        for s2 in range(k):
            if (i & (1<<s2)) == 0:
                # Pièce non encore collectée, essayons d'aller la chercher
                d = parcours_depuis(n-k+s2, i | (1<<s2))
                d += dist[s][n-k+s2]
                if dmin == None or d < dmin:
                    dmin = d
        if s != 0:
            t[s-(n-k)][i] = dmin
        return dmin

    dmin = parcours_depuis(0,0)
    return dmin

print("6.a %s" % (str(optim(g1,8))))
print("6.b %s" % (str(optim(g2,10))))
print("6.c %s" % (str(optim(g3,12))))

#
# Q7
#
def optim_quelconque(g, k):
    n = len(g)

    dist = distances(g)

    dmax = 0

    # Le sujet ne demande de calculs que pour k=4, on peut donc se contenter
    # d'utiliser 4 boucles pour obtenir le résultat
    assert(k==4)
    for s1 in range(1,n):
        for s2 in range(s1+1,n):
            for s3 in range(s2+1,n):
                for s4 in range(s3+1,n):
                    l = [s1,s2,s3,s4]

                    # On mémoise comme précédemment
                    t = [ [ None ] * (1<<k) for i in range(k) ]
                    for i in range(k):
                        # Cas de base: on a collecté toutes les pièces
                        t[i][(1<<k)-1] = 0

                    def parcours_depuis(s,i):
                        # mémoisation
                        if s != 0 and t[l.index(s)][i] != None:
                            return t[l.index(s)][i]

                        dmin = None
                        for s2 in range(k):
                            if (i & (1<<s2)) == 0:
                                # Pièce non encore collectée, essayons d'aller la chercher
                                d = parcours_depuis(l[s2], i | (1<<s2))
                                d += dist[s][l[s2]]
                                if dmin == None or d < dmin:
                                    dmin = d
                        if s != 0:
                            t[l.index(s)][i] = dmin
                        return dmin

                    dmin = parcours_depuis(0,0)
                    if dmin > dmax:
                        dmax = dmin
    return dmax

g1 = gnp2(10,654)
g2 = gnp2(20,543)
g3 = gnp2(50,432)
print("7.a %s" % (str(optim_quelconque(g1,4))))
print("7.b %s" % (str(optim_quelconque(g2,4))))
print("7.c %s" % (str(optim_quelconque(g3,4))))


#
# Q8
#
# Les résultats indiqués pour ~u0 sont petits, on peut se permettre d'essayer
# un brute-force
def kmax(g,d):
    k = 1
    while True:
        dmin = optim(g,k)
        if dmin > d:
            return k-1
        k += 1

print("8.a %s" % (str(kmax(g1,6))))
print("8.b %s" % (str(kmax(g2,8))))
print("8.c %s" % (str(kmax(g3,10))))


#
# Q9
#
def kmax_glouton(g,dlim):
    n = len(g)
    dist = distances(g)

    # Chemin initial
    l = [0]
    k = 0
    d = 0
    while True:
        k += 1
        if k == n:
            return k
        dmin = None
        for i in range(len(l)-1):
            dmin2 = d + dist[l[i]][n-k] + dist[n-k][l[i+1]] - dist[l[i]][l[i+1]]
            if dmin == None or dmin2 < dmin:
                dmin = dmin2
                ii = i+1

        # essayer à la fin aussi
        dmin2 = d + dist[l[-1]][n-k]
        if dmin == None or dmin2 < dmin:
            dmin = dmin2
            ii = len(l)

        l.insert(ii, n-k)
        if dmin > dlim:
            # On dépasse la limite avec ce k-là
            return k-1
        d = dmin

g1 = gnp2(100,32)
g2 = gnp2(200,21)
g3 = gnp2(1000,1)
print("9.a %s" % (str(kmax_glouton(g1,40))))
print("9.b %s" % (str(kmax_glouton(g2,100))))
print("9.c %s" % (str(kmax_glouton(g3,500))))