Oros Ioana Diana at 06:51, 18 May 2024

2024-05-18T06:51:49Z

Oros Ioana Diana: Pagină nouă: 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, d...

2024-01-08T23:33:36Z

Pagină nouă: 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, d...

New page

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
<br>
== 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
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#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

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

# 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
<br>
s2 = 4 5 6
<br>
s3 = 7 8 9

Cele șase subșiruri nevide sunt:

s1, s1-s2, s1-s2-s3, s2, s2-s3, s3

1737 - K Siruri - Revision history

Oros Ioana Diana at 06:51, 18 May 2024