View source for 1737 - K Siruri

Se consideră un număr natural <code>K</code> și o secvență de <code>N</code> șiruri <code>s[1]</code>, <code>s[2]</code>, …, <code>s[N]</code>. Fiecare șir este format din cifre distincte. Pentru două șiruri <code>s[i]</code> și <code>s[j]</code> se definește operația de scădere (<code>–</code>) astfel: <code>s[i]-s[j]</code> va conține doar șirul de cifre care apar în <code>s[i]</code>, dar nu apar în <code>s[j]</code>. De exemplu, dacă <code>s[i]=(1,3,8)</code> și <code>s[j]=(2,9,3)</code>, atunci <code>s[i]-s[j]=(1,8)</code>. Această operație nu este asociativă, <code>(s[i]-s[j])-s[p]</code> este diferită de <code>s[i]-(s[j]-s[p])</code>. De aceea, dacă se alege un subșir <code>s[i1]</code>, <code>s[i2]</code>, …, <code>s[ip]</code> din secvență, atunci convenim ca <code>s[i1]-s[i2]-...-s[ip]</code> să se execute de la dreapta la stânga.

Exemplu: <code>(1,2,3)-(2,3)-(1,3)=(1,2,3)-(2)=(1,3)</code>. S-au obținut două cifre distincte.

= Cerința =
Să se determine numărul subșirurilor nevide <code>s[i1]</code>, <code>s[i2]</code>, …, <code>s[ip]</code> din secvența <code>s[1]</code>, <code>s[2]</code>, …, <code>s[N]</code> asupra cărora, dacă se efectuează operația de scădere (adică <code>s[i1]-s[i2]-...-s[ip]</code>), se obțin cel puțin <code>K</code> cifre distincte. Pentru că numărul subșirurilor poate fi foarte mare, atunci el se va calcula modulo <code>123457</code>.

= Date de intrare =
Fișierul de intrare <code>ksiruriIN.txt</code> conține pe prima linie numerele naturale <code>K</code> și <code>N</code>. Pe următoarele <code>N</code> linii se află câte un șir <code>s[i]</code>. Linia <code>i+1</code>, <code>i = 1..N</code>, va conține valorile <code>m c[1] c[2] .. c[m]</code>, unde <code>m</code> este numărul de termeni al șirului <code>s[i]</code>, iar <code>c[1]</code>, <code>c[2]</code>, …, <code>c[m]</code> sunt cifrele distincte ale șirului <code>s[i]</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Date de ieșire =
Fișierul de ieșire <code>ksiruriOUT.txt</code> va conține reprezentând numărul de subșiruri, modulo <code>123457</code>.

= Restricții și precizări =

* <code>1 ≤ K ≤ 8</code>
* <code>2 ≤ N ≤ 50 000</code>
* <code>1 ≤ i1 < i2 < ... < ip ≤ N</code>

= Exemplu 1: =
<code>ksiruriIN.txt</code>
 3 3
 5 5 6 7 8 9
 3 4 5 6
 3 7 8 9 
<code>ksiruriOUT.txt</code>
 6

=== Explicație ===
<code>s1 = 5 6 7 8 9</code>

<code>s2 = 4 5 6</code>

<code>s3 = 7 8 9</code>

Cele șase subșiruri nevide sunt:

<code>s1</code>, <code>s1-s2</code>, <code>s1-s2-s3</code>, <code>s2</code>, <code>s2-s3</code>, <code>s3</code>

== Exemplu 2: ==
<code>ksiruriIN.txt</code>
 9 3
 5 5 6 7 8 9
 3 4 5 6
 3 7 8 9 
<code>ksiruriOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare == 
<syntaxhighlight lang="python" line="1">
import sys
from functools import reduce

nmax = 50005
MOD = 123457
inFile = "ksiruriIN.txt"
outFile = "ksiruriOUt.txt"

a = [0] * nmax
d = [0] * 1030
v = [0] * 1030

def verifica_restrictii(K, n):
    if not (1 <= K <= 8 and 2 <= n <= 50000):
        return False
    return True

def citire():
    global a, K, n
    try:
        with open(inFile, 'r') as fin:
            K, n = map(int, fin.readline().strip().split())
            if not verifica_restrictii(K, n):
                return False
            for i in range(1, n + 1):
                linie = list(map(int, fin.readline().strip().split()))
                m = linie[0]
                for x in linie[1:m+1]:
                    a[i] |= (1 << x)
        return True
    except Exception as e:
        print(f"Eroare la citire: {e}")
        return False

def nr_biti(n):
    cnt = 0
    while n > 0:
        cnt += 1
        n &= (n - 1)
    return cnt

def dinamica():
    global a, d, v, n, MOD
    d[a[n]] = 1
    for i in range(n - 1, 0, -1):
        for j in range(1024):
            v[j] = d[j]
        x = a[i]
        v[x] += 1
        if v[x] == MOD:
            v[x] = 0
        for j in range(1024):
            if d[j] > 0:
                y = x ^ (x & j)
                v[y] += d[j]
        for j in range(1024):
            d[j] = v[j] % MOD

def afisare():
    cnt = 0
    for i in range(1024):
        if nr_biti(i) >= K and d[i] > 0:
            cnt += d[i]
    cnt %= MOD
    with open(outFile, 'w') as fout:
        fout.write(f"{cnt}\n")

def main():
    if not citire():
        with open(outFile, 'w') as fout:
            fout.write("Datele nu corespund restrictiilor impuse\n")
        return
    dinamica()
    afisare()

if __name__ == "__main__":
    main()

</syntaxhighlight>