1737 - K Siruri
Se consideră un număr natural K
și o secvență de N
șiruri s[1]
, s[2]
, …, s[N]
. Fiecare șir este format din cifre distincte. Pentru două șiruri s[i]
și s[j]
se definește operația de scădere (–
) astfel: s[i]-s[j]
va conține doar șirul de cifre care apar în s[i]
, dar nu apar în s[j]
. De exemplu, dacă s[i]=(1,3,8)
și s[j]=(2,9,3)
, atunci s[i]-s[j]=(1,8)
. Această operație nu este asociativă, (s[i]-s[j])-s[p]
este diferită de s[i]-(s[j]-s[p])
. De aceea, dacă se alege un subșir s[i1]
, s[i2]
, …, s[ip]
din secvență, atunci convenim ca s[i1]-s[i2]-...-s[ip]
să se execute de la dreapta la stânga.
Exemplu: (1,2,3)-(2,3)-(1,3)=(1,2,3)-(2)=(1,3)
. S-au obținut două cifre distincte.
Cerința
Să se determine numărul subșirurilor nevide s[i1]
, s[i2]
, …, s[ip]
din secvența s[1]
, s[2]
, …, s[N]
asupra cărora, dacă se efectuează operația de scădere (adică s[i1]-s[i2]-...-s[ip]
), se obțin cel puțin K
cifre distincte. Pentru că numărul subșirurilor poate fi foarte mare, atunci el se va calcula modulo 123457
.
Date de intrare
Fișierul de intrare ksiruriIN.txt
conține pe prima linie numerele naturale K
și N
. Pe următoarele N
linii se află câte un șir s[i]
. Linia i+1
, i = 1..N
, va conține valorile m c[1] c[2] .. c[m]
, unde m
este numărul de termeni al șirului s[i]
, iar c[1]
, c[2]
, …, c[m]
sunt cifrele distincte ale șirului s[i]
. Î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 ksiruriOUT.txt
va conține reprezentând numărul de subșiruri, modulo 123457
.
Restricții și precizări
1 ≤ K ≤ 8
2 ≤ N ≤ 50 000
1 ≤ i1 < i2 < ... < ip ≤ N
Exemplu 1:
ksiruriIN.txt
3 3 5 5 6 7 8 9 3 4 5 6 3 7 8 9
ksiruriOUT.txt
6
Explicație
s1 = 5 6 7 8 9
s2 = 4 5 6
s3 = 7 8 9
Cele șase subșiruri nevide sunt:
s1
, s1-s2
, s1-s2-s3
, s2
, s2-s3
, s3
Exemplu 2:
ksiruriIN.txt
9 3 5 5 6 7 8 9 3 4 5 6 3 7 8 9
ksiruriOUT.txt
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>