1042 - Subsecvente: Difference between revisions

From Bitnami MediaWiki
Pagină nouă: Fie n un număr natural și M={S1,S2,…,Sn} o mulțime de șiruri de caractere nevide. Fie Sk un șir de caractere din M. Atunci, orice caracter al lui Sk aparține mulțimii {'a','b'}. Notăm prin |Sk| numărul caracterelor șirului Sk sau, echivalent, lungimea sa. O subsecvență Sk[i:j] a lui Sk este formată din caracterele situate pe pozițiile consecutive i, i+1, .., j. Astfel, dacă Sk = 'abbbaababa', atunci Sk[3:6] = 'bbaa' sau subsecvența evidențiată: 'abbbaabab...
 
No edit summary
 
Line 1: Line 1:


Fie n un număr natural și M={S1,S2,…,Sn} o mulțime de șiruri de caractere nevide. Fie Sk un șir de caractere din M. Atunci, orice caracter al lui Sk aparține mulțimii {'a','b'}. Notăm prin |Sk| numărul caracterelor șirului Sk sau, echivalent, lungimea sa. O subsecvență Sk[i:j] a lui Sk este formată din caracterele situate pe pozițiile consecutive i, i+1, .., j. Astfel, dacă Sk = 'abbbaababa', atunci Sk[3:6] = 'bbaa' sau subsecvența evidențiată: 'abbbaababa'.
Fie <code>n</code> un număr natural și <code>M={S1,S2,…,Sn}</code> o mulțime de șiruri de caractere nevide. Fie <code>Sk</code> un șir de caractere din <code>M</code>. Atunci, orice caracter al lui <code>Sk</code> aparține mulțimii <code>{'a','b'}</code>. Notăm prin <code>|Sk|</code> numărul caracterelor șirului <code>Sk</code> sau, echivalent, lungimea sa. O subsecvență <code>Sk[i:j]</code> a lui <code>Sk</code> este formată din caracterele situate pe pozițiile consecutive <code>i, i+1, .., j</code>. Astfel, dacă <code>Sk = 'abbbaababa'</code>, atunci <code>Sk[3:6] = 'bbaa'</code> sau subsecvența evidențiată: <code>'abbbaababa'</code>.
== Cerința ==
Fiind dată o mulțime M, se cere să se determine lungimea maximă a unei subsecvențe care se găsește în toate șirurile din M.
== Date de intrare ==
Fișierul de intrare subsecventein.txt conține pe prima linie un număr natural n egal cu cardinalul mulțimii M. Pe fiecare din următoarele n linii se găsește câte un șir din mulțimea M.
== Date de ieșire ==
Fișierul de ieșire subsecventeout.txt va conține pe prima linie un singur număr natural egal cu lungimea subsecvenței găsite.
== Restricții și precizări ==
*1 < n < 5
*Dacă |S| = |S1| + |S2| + … + |Sn|, atunci |S| < 50 001
*Se garantează că va exista întotdeauna soluție
*Se garantează că rezultatul nu va depăși 60
*Pentru 30% din teste: |S| < 101
*Pentru 55% din teste: |S| < 3 501
*Pentru 80% din teste: |S| < 10 001
== Exemplu 1 ==
; subsecventin.txt
: 4
: abbabaaaaabb
: aaaababab
: bbbbaaaab
: aaaaaaabaaab
; subsecventeout.txt
: 5
<br>
== Exemplu 2 ==
; subsecventin.txt
: 4
: abba
: abab
: baaa
: aaa
; subsecventout.txt
: 4
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#1042 - Sudef lungime_subsecventa_maxima(M):
    # Verificare restricții
    if not (1 < len(M) < 5):
        return "Fals"


    total_length = sum(len(s) for s in M)
= Cerința =
Fiind dată o mulțime <code>M</code>, se cere să se determine lungimea maximă a unei subsecvențe care se găsește în toate șirurile din <code>M</code>.


    if not (total_length < 50001 and total_length > 0):
= Date de intrare =
        return "Fals"
Fișierul de intrare <code>subsecventeIN.txt</code> conține pe prima linie un număr natural <code>n</code> egal cu cardinalul mulțimii <code>M</code>. Pe fiecare din următoarele <code>n</code> linii se găsește câte un șir din mulțimea <code>M</code>.


    chars_set = set(M[0])
= Date de ieșire =
Fișierul de ieșire <code>subsecventeOUT.txt</code> va conține pe prima linie un singur număr natural egal cu lungimea subsecvenței găsite. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".


    for char in chars_set:
= Restricții și precizări =
        count = min(s.count(char) for s in M)
        if count < 1:
            return "Fals"


    result = sum(min(s.count(char) for s in M) for char in chars_set)
* <code>1 < n < 5</code>
    return result
* Dacă <code>|S| = |S1| + |S2| + … + |Sn|</code>, atunci <code>|S| < 50 001</code>
* Se garantează că va exista întotdeauna soluție
* Se garantează că rezultatul nu va depăși <code>60</code>
* Pentru <code>30%</code> din teste: <code>|S| < 101</code>
* Pentru <code>55%</code> din teste: <code>|S| < 3 501</code>
* Pentru <code>80%</code> din teste: <code>|S| < 10 001</code>


# Citirea datelor de intrare din fișierul "subsecventein.txt"
= Exemplu 1: =
try:
<code>subsecventeIN.txt</code>
    with open("subsecventein.txt", "r") as file:
4
        n = int(file.readline())
abbabaaaaabb
        M = [file.readline().strip() for _ in range(n)]
aaaababab
except Exception as e:
bbbbaaaab
    print("Fals")
aaaaaaabaaab
    exit()
<code>subsecventeOUT.txt</code>
5


# Calcularea și afișarea rezultatului în fișierul "subsecventeout.txt"
= Explicație =
result = lungime_subsecventa_maxima(M)
Lungimea unei subsecvenţe comune de lungime maximă este <code>5</code>.


if result == "Fals":
În exemplu subsecvența comună de lungime <code>5</code> este <code>aaaab</code>:
    print(result)
else:
    with open("subsecventeout.txt", "w") as file:
        file.write(str(result) + "\n")
bsecvente


</syntaxhighlight>
<code>abbabaaaaabb</code>, <code>aaaababab</code>, <code>bbbbaaaab</code>, <code>aaaaaaabaaab</code>.
:
 
== Exemplu 2: ==
<code>subsecventeIN.txt</code>
7
abbabaaaaabb
aaaababab
bbbbaaaab
aaaaaaabaaab
<code>subsecventeOUT.txt</code>
Datele nu corespund restrictiilor impuse
 
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import sys
 
# Definim constantele
NODES = 2600100
 
# Inițializăm variabilele
p2, lg, mask, i, j, k, p, q, n = 0, 0, 0, 0, 0, 0, 0, 0, 0
s = [[0] * NODES for _ in range(2)]
cod = [0] * NODES
a = [""] * 50010
 
def sol(nod):
    if not nod or cod[nod] != mask:
        return 0
    sa = sol(s[0][nod])
    sb = sol(s[1][nod])
    return max(sa, sb) + 1
 
def main():
    global p2, lg, mask, i, j, k, p, q, n
    # Citim datele de intrare
    with open("subsecventeIN.txt", "r") as infile:
        data = infile.read().strip().split()
 
    n = int(data[0])
    sequences = data[1:]
 
    # Verificăm restricțiile
    if not (1 < n < 5) or sum(len(seq) for seq in sequences) >= 50001:
        with open("subsecventeOUT.txt", "w") as outfile:
            outfile.write("Datele nu corespund restrictiilor impuse\n")
        return
 
    p2 = 1
    n = 1
    mask = 0
    for sequence in sequences:
        lg = len(sequence)
        mask |= p2
        for i in range(1, lg + 1):
            j = min(i + 59, lg)
            p = 1
            for k in range(i, j + 1):
                q = ord(sequence[k-1]) - ord('a')
                if not s[q][p]:
                    s[q][p] = n + 1
                    n += 1
                p = s[q][p]
                cod[p] |= p2
        p2 <<= 1
 
    cod[1] = mask
    result = sol(1) - 1
    with open("subsecventeOUT.txt", "w") as outfile:
        outfile.write(f"{result}\n")


== Explicatie ==
if __name__ == "__main__":
Lungimea unei subsecvenţe comune de lungime maximă este 5.
    main()


În exemplu subsecvența comună de lungime 5 este aaaab:
</syntaxhighlight>
<br>
abbabaaaaabb, aaaababab, bbbbaaaab, aaaaaaabaaab.

Latest revision as of 07:20, 18 May 2024

Fie n un număr natural și M={S1,S2,…,Sn} o mulțime de șiruri de caractere nevide. Fie Sk un șir de caractere din M. Atunci, orice caracter al lui Sk aparține mulțimii {'a','b'}. Notăm prin |Sk| numărul caracterelor șirului Sk sau, echivalent, lungimea sa. O subsecvență Sk[i:j] a lui Sk este formată din caracterele situate pe pozițiile consecutive i, i+1, .., j. Astfel, dacă Sk = 'abbbaababa', atunci Sk[3:6] = 'bbaa' sau subsecvența evidențiată: 'abbbaababa'.

Cerința[edit | edit source]

Fiind dată o mulțime M, se cere să se determine lungimea maximă a unei subsecvențe care se găsește în toate șirurile din M.

Date de intrare[edit | edit source]

Fișierul de intrare subsecventeIN.txt conține pe prima linie un număr natural n egal cu cardinalul mulțimii M. Pe fiecare din următoarele n linii se găsește câte un șir din mulțimea M.

Date de ieșire[edit | edit source]

Fișierul de ieșire subsecventeOUT.txt va conține pe prima linie un singur număr natural egal cu lungimea subsecvenței găsite. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări[edit | edit source]

  • 1 < n < 5
  • Dacă |S| = |S1| + |S2| + … + |Sn|, atunci |S| < 50 001
  • Se garantează că va exista întotdeauna soluție
  • Se garantează că rezultatul nu va depăși 60
  • Pentru 30% din teste: |S| < 101
  • Pentru 55% din teste: |S| < 3 501
  • Pentru 80% din teste: |S| < 10 001

Exemplu 1:[edit | edit source]

subsecventeIN.txt

4
abbabaaaaabb
aaaababab
bbbbaaaab
aaaaaaabaaab

subsecventeOUT.txt

5

Explicație[edit | edit source]

Lungimea unei subsecvenţe comune de lungime maximă este 5.

În exemplu subsecvența comună de lungime 5 este aaaab:

abbabaaaaabb, aaaababab, bbbbaaaab, aaaaaaabaaab.

Exemplu 2:[edit | edit source]

subsecventeIN.txt

7
abbabaaaaabb
aaaababab
bbbbaaaab
aaaaaaabaaab

subsecventeOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<syntaxhighlight lang="python" line="1"> import sys

  1. Definim constantele

NODES = 2600100

  1. Inițializăm variabilele

p2, lg, mask, i, j, k, p, q, n = 0, 0, 0, 0, 0, 0, 0, 0, 0 s = [[0] * NODES for _ in range(2)] cod = [0] * NODES a = [""] * 50010

def sol(nod):

   if not nod or cod[nod] != mask:
       return 0
   sa = sol(s[0][nod])
   sb = sol(s[1][nod])
   return max(sa, sb) + 1

def main():

   global p2, lg, mask, i, j, k, p, q, n
   # Citim datele de intrare
   with open("subsecventeIN.txt", "r") as infile:
       data = infile.read().strip().split()
   n = int(data[0])
   sequences = data[1:]
   # Verificăm restricțiile
   if not (1 < n < 5) or sum(len(seq) for seq in sequences) >= 50001:
       with open("subsecventeOUT.txt", "w") as outfile:
           outfile.write("Datele nu corespund restrictiilor impuse\n")
       return
   p2 = 1
   n = 1
   mask = 0
   for sequence in sequences:
       lg = len(sequence)
       mask |= p2
       for i in range(1, lg + 1):
           j = min(i + 59, lg)
           p = 1
           for k in range(i, j + 1):
               q = ord(sequence[k-1]) - ord('a')
               if not s[q][p]:
                   s[q][p] = n + 1
                   n += 1
               p = s[q][p]
               cod[p] |= p2
       p2 <<= 1
   cod[1] = mask
   result = sol(1) - 1
   with open("subsecventeOUT.txt", "w") as outfile:
       outfile.write(f"{result}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>