1737 - K Siruri

From Bitnami MediaWiki

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>