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[edit | edit source]
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[edit | edit source]
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[edit | edit source]
Fișierul de ieșire ksiruriOUT.txt
va conține reprezentând numărul de subșiruri, modulo 123457
.
Restricții și precizări[edit | edit source]
1 ≤ K ≤ 8
2 ≤ N ≤ 50 000
1 ≤ i1 < i2 < ... < ip ≤ N
Exemplu 1:[edit | edit source]
ksiruriIN.txt
3 3 5 5 6 7 8 9 3 4 5 6 3 7 8 9
ksiruriOUT.txt
6
Explicație[edit | edit source]
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:[edit | edit source]
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[edit | edit source]
<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>