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].

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

Exemplul 1

ksiruriin.txt

3 3

5 5 6 7 8 9

3 4 5 6

3 7 8 9

ksiruriout.txt

6

Exemplul 2

ksiruriin.txt

5 4

4 5 6 7 8

3 6 7 8

4 5 7 8

3 9 7 8

ksiruriout.txt

2

Rezolvare

<syntaxhighlight lang="python" line>

1. 1737 - K Siruri

def count_subsequences(K, N, sequences):

   result = 0
   mod = 123457

   for i in range(N):
       current_sequence = set(sequences[i][1:])
       result += 1  # Adăugați șirul curent la rezultat

       for j in range(i - 1, -1, -1):
           current_sequence -= set(sequences[j][1:])
           if len(current_sequence) >= K:
               result = (result * 2) % mod

   return result

1. Citirea datelor de intrare

with open("ksiruriin.txt", "r") as infile:

   K, N = map(int, infile.readline().split())
   sequences = [list(map(int, line.split()[1:])) for line in infile]

1. Verificarea restricțiilor

if not (1 <= K <= 8 and 2 <= N <= 50000):

   print("Fals")

else:

   # Calculul rezultatului
   result = count_subsequences(K, N, sequences)

   # Scrierea rezultatului în fișierul de ieșire
   with open("ksiruriout.txt", "w") as outfile:
       outfile.write(str(result))

</syntaxhighlight>

Explicatie

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