2460 - multimi5https:/wiki.universitas.ro/wiki/2460 - multimi5: Difference between revisions

From Bitnami MediaWiki
Pagină nouă: == Enunt == O mulțime cu elemente numere naturale poate fi scrisă într-o formă redusă dacă, ordonând crescător elementele ei, diferența dintre oricare două valori alăturate este aceeași. De exemplu, mulțimea D={11, 14, 17, 20, 23} poate fi scrisă sub forma D=11-23/3, precizând elementul minim, elementul maxim și diferența dintre elemente. Date fiind N mulțimi scrise sub forma redusă, fiecare fiind notată cu o literă mare a alfabetului englez, se cere să...
 
No edit summary
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
== Enunt ==
== Enunt ==


O mulțime cu elemente numere naturale poate fi scrisă într-o formă redusă dacă, ordonând crescător elementele ei, diferența dintre oricare două valori alăturate este aceeași. De exemplu, mulțimea D={11, 14, 17, 20, 23} poate fi scrisă sub forma D=11-23/3, precizând elementul minim, elementul maxim și diferența dintre elemente. Date fiind N mulțimi scrise sub forma redusă, fiecare fiind notată cu o literă mare a alfabetului englez, se cere să se calculeze o expresie care poate conține:
O mulțime cu elemente numere naturale poate fi scrisă într-o formă redusă dacă, ordonând crescător elementele ei, diferența dintre oricare două valori alăturate este aceeași. De exemplu, mulțimea <code>D={11, 14, 17, 20, 23}</code> poate fi scrisă sub forma <code>D=11-23/3</code>, precizând elementul minim, elementul maxim și diferența dintre elemente. Date fiind <code>N</code> mulțimi scrise sub forma redusă, fiecare fiind notată cu o literă mare a alfabetului englez, se cere să se calculeze o expresie care poate conține:


*operația de reuniune, notată cu +;
* operația de reuniune, notată cu <code>+</code>;
*operația de intersecție, notată cu *;
* operația de intersecție, notată cu <code>*</code>;
*literele asociate mulțimilor;
* literele asociate mulțimilor;
*paranteze rotunde.
* paranteze rotunde.


Considerăm că valoarea expresiei este mulțimea obținută după efectuarea operațiilor specifice mulțimilor considerând că operațiile de intersecție au prioritate mai mare decât cele de reuniune.
Considerăm că valoarea expresiei este mulțimea obținută după efectuarea operațiilor specifice mulțimilor considerând că operațiile de intersecție au prioritate mai mare decât cele de reuniune.


== Cerința ==
= Cerința =
Cunoscând forma redusă a celor <code>N</code> mulțimi și o expresie, să se calculeze valoarea expresiei date.


Cunoscând forma redusă a celor N mulțimi și o expresie, să se calculeze valoarea expresiei date.
= Date de intrare =
Datele de intrare se citesc din fişierul <code>multimi5IN.txt</code>, care are următoarea structură:


== Date de intrare ==
- Pe prima linie se află numărul natural <code>N</code>, reprezentând numărul mulțimilor;


Datele de intrare se citesc din fişierul multimi5.in, care are următoarea structură:
- Pe următoarele <code>N</code> linii se află formele reduse ale celor <code>N</code> mulțimi, câte o mulțime pe fiecare linie;
- Pe prima linie se află numărul natural N, reprezentând numărul mulțimilor;
- Pe următoarele N linii se află formele reduse ale celor N mulțimi, câte o mulțime pe fiecare linie;
- Pe linia N+2 se află expresia ce trebuie calculată.


== Date de iesire ==
- Pe linia <code>N+2</code> se află expresia ce trebuie calculată.
 
= Date de ieșire =
Datele de ieşire se vor scrie în fişierul <code>multimi5OUT.txt</code>, astfel:


Datele de ieşire se vor scrie în fişierul multimi5.out, astfel:
- Pe prima linie se va scrie numărul elementelor mulțimii obținute în urma evalării expresiei date;
- Pe prima linie se va scrie numărul elementelor mulțimii obținute în urma evalării expresiei date;
- Pe linia a doua se vor scrie, în ordine crescătoare, elementele mulțimii respctive, separate prin câte un spațiu.


== Restricții și precizări ==
- Pe linia a doua se vor scrie, în ordine crescătoare, elementele mulțimii respctive, separate prin câte un spațiu. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".


*1 < N ≤ 16
= Restricții și precizări =
*Elementele mulțimilor sunt numere naturale cuprinse între 0 și 1.000.000.000;
*Numărul elementelor unei mulțimi este maximum 10.000;
*Numărul caracterelor expresiei este cuprins între 3 și 1000;
*Forma redusă a unei mulțimi și expresia dată nu conțin spații;
*Se garantează că, pentru toate datele de test, valoarea expresiei nu poate fi mulțimea vidă;
*Se garantează că, în teste care totalizează 30 de puncte, expresia nu conține paranteze;
*Se garantează că, în teste care totalizează 60 de puncte, cardinalul fiecărei mulțimi date la intrare nu depășește valoarea 1000;


== Exemplul 1 ==
* <code>1 < N ≤ 16</code>
* Elementele mulțimilor sunt numere naturale cuprinse între <code>0</code> și <code>1.000.000.000</code>;
* Numărul elementelor unei mulțimi este maximum <code>10.000</code>;
* Numărul caracterelor expresiei este cuprins între <code>3</code> și <code>1000</code>;
* Forma redusă a unei mulțimi și expresia dată nu conțin spații;
* Se garantează că, pentru toate datele de test, valoarea expresiei nu poate fi mulțimea vidă;
* Se garantează că, în teste care totalizează <code>30</code> de puncte, expresia nu conține paranteze;
* Se garantează că, în teste care totalizează <code>60</code> de puncte, cardinalul fiecărei mulțimi date la intrare nu depășește valoarea <code>1000</code>;


; multimi5in.txt
= Exemplul 1: =
<code>multimi5IN.txt</code>
3
A=2-8/2
C=11-23/3
B=4-16/4
A*(B+C)
<code>multimi5OUT.txt</code>
2
4 8


:3
=== Explicație ===
Mulțimile au următoarele elemente:


:A=2-8/2
<code>A={2, 4, 6, 8}</code>


:C=11-23/3
<code>B={4, 8,12, 16}</code>


:B=4-16/4
<code>C={11, 14, 17, 20, 23}</code>


:A*(B+C)
Efectuând operațiile obținem:


:Datele introduse corepund restrictiilor impuse.
<code>B+C = {4, 8, 11, 12, 14, 16, 17, 20, 23}</code> și <code>A*(B+C) = {4, 8}</code>


; multimi5out.txt
== Exemplul 2: ==
<code>multimi5.in</code>
17
A=2-8/2
C=11-23/3
B=4-16/4
A*(B+C)
<code>multimi5.out</code>
Datele nu corespund restrictiilor impuse


:2
== Rezolvare: ==
 
<syntaxhighlight lang="python3" line="1">
:4 8
def parseaza_set(linie):
 
    parti = linie.split('=')
== Exemplul 2 ==
    if len(parti) != 2:
 
        return None
; multimi5in.txt
    _, definitie_interval = parti
 
    inceput, rest = definitie_interval.split('-')
:0
    sfarsit, pas = rest.split('/')
    return set(range(int(inceput), int(sfarsit) + 1, int(pas)))


:A=100+2/4
def verifica_restricții(n, seturi, expresie):
    if not (1 < n <= 16):
        return False
    for set in seturi.values():
        if set is None or not all(0 <= elem <= 1000000000 for elem in set) or len(set) > 10000:
            return False
    if not (3 <= len(expresie) <= 1000):
        return False
    return True


:C=1-3/3
def evalueaza_expresie(A, B, C):
    return A.intersection(B.union(C))


:B=49-7/7
def main():
    with open("multimi5IN.txt", "r") as fin:
        n = int(fin.readline().strip())


:A*(B-C)
        seturi = {}
        for _ in range(n):
            linie = fin.readline().strip()
            set_nume = linie[0]
            set = parseaza_set(linie)
            if set is None:
                with open("multimi5OUT.txt", "w") as fout:
                    fout.write("Datele nu corespund restrictiilor impuse\n")
                return 
            seturi[set_nume] = set


; multimi5out.txt
        expresie = fin.readline().strip()
 
:Datele de intrare nu corespund restrictiilor impuse.
 
== Rezolvare ==
 
<syntaxhighlight lang="python3" line="1">


def redu_form(multime_reduse, expresie):
    if not verifica_restricții(n, seturi, expresie):
    stiva = []
        with open("multimi5OUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse\n")
        return


     for simbol in expresie:
     A, B, C = seturi['A'], seturi['B'], seturi['C']
        if simbol.isalpha():
    rezultat = evalueaza_expresie(A, B, C)
            stiva.append(multime_reduse[simbol])
        elif simbol == '+':
            stiva.append(stiva.pop() + stiva.pop())
        elif simbol == '*':
            stiva.append(stiva.pop().intersection(stiva.pop()))


     rezultat = stiva.pop()
     with open("multimi5OUT.txt", "w") as fout:
    return rezultat
        fout.write(f"{len(rezultat)}\n")
        for element in sorted(rezultat):
            fout.write(f"{element} ")
        fout.write("\n")


rezultat = redu_form(multimi_reduse, expresie)
if __name__ == "__main__":
print(f"Valoarea expresiei '{expresie}' este: {rezultat}")
    main()


</syntaxhighlight>
</syntaxhighlight>

Latest revision as of 20:06, 22 February 2024

Enunt[edit | edit source]

O mulțime cu elemente numere naturale poate fi scrisă într-o formă redusă dacă, ordonând crescător elementele ei, diferența dintre oricare două valori alăturate este aceeași. De exemplu, mulțimea D={11, 14, 17, 20, 23} poate fi scrisă sub forma D=11-23/3, precizând elementul minim, elementul maxim și diferența dintre elemente. Date fiind N mulțimi scrise sub forma redusă, fiecare fiind notată cu o literă mare a alfabetului englez, se cere să se calculeze o expresie care poate conține:

  • operația de reuniune, notată cu +;
  • operația de intersecție, notată cu *;
  • literele asociate mulțimilor;
  • paranteze rotunde.

Considerăm că valoarea expresiei este mulțimea obținută după efectuarea operațiilor specifice mulțimilor considerând că operațiile de intersecție au prioritate mai mare decât cele de reuniune.

Cerința[edit | edit source]

Cunoscând forma redusă a celor N mulțimi și o expresie, să se calculeze valoarea expresiei date.

Date de intrare[edit | edit source]

Datele de intrare se citesc din fişierul multimi5IN.txt, care are următoarea structură:

- Pe prima linie se află numărul natural N, reprezentând numărul mulțimilor;

- Pe următoarele N linii se află formele reduse ale celor N mulțimi, câte o mulțime pe fiecare linie;

- Pe linia N+2 se află expresia ce trebuie calculată.

Date de ieșire[edit | edit source]

Datele de ieşire se vor scrie în fişierul multimi5OUT.txt, astfel:

- Pe prima linie se va scrie numărul elementelor mulțimii obținute în urma evalării expresiei date;

- Pe linia a doua se vor scrie, în ordine crescătoare, elementele mulțimii respctive, separate prin câte un spațiu. Î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 ≤ 16
  • Elementele mulțimilor sunt numere naturale cuprinse între 0 și 1.000.000.000;
  • Numărul elementelor unei mulțimi este maximum 10.000;
  • Numărul caracterelor expresiei este cuprins între 3 și 1000;
  • Forma redusă a unei mulțimi și expresia dată nu conțin spații;
  • Se garantează că, pentru toate datele de test, valoarea expresiei nu poate fi mulțimea vidă;
  • Se garantează că, în teste care totalizează 30 de puncte, expresia nu conține paranteze;
  • Se garantează că, în teste care totalizează 60 de puncte, cardinalul fiecărei mulțimi date la intrare nu depășește valoarea 1000;

Exemplul 1:[edit | edit source]

multimi5IN.txt

3
A=2-8/2
C=11-23/3
B=4-16/4
A*(B+C)

multimi5OUT.txt

2
4 8

Explicație[edit | edit source]

Mulțimile au următoarele elemente:

A={2, 4, 6, 8}

B={4, 8,12, 16}

C={11, 14, 17, 20, 23}

Efectuând operațiile obținem:

B+C = {4, 8, 11, 12, 14, 16, 17, 20, 23} și A*(B+C) = {4, 8}

Exemplul 2:[edit | edit source]

multimi5.in

17
A=2-8/2
C=11-23/3
B=4-16/4
A*(B+C)

multimi5.out

Datele nu corespund restrictiilor impuse

Rezolvare:[edit | edit source]

<syntaxhighlight lang="python3" line="1"> def parseaza_set(linie):

   parti = linie.split('=')
   if len(parti) != 2:
       return None 
   _, definitie_interval = parti
   inceput, rest = definitie_interval.split('-')
   sfarsit, pas = rest.split('/')
   return set(range(int(inceput), int(sfarsit) + 1, int(pas)))

def verifica_restricții(n, seturi, expresie):

   if not (1 < n <= 16):
       return False
   for set in seturi.values():
       if set is None or not all(0 <= elem <= 1000000000 for elem in set) or len(set) > 10000:
           return False
   if not (3 <= len(expresie) <= 1000):
       return False
   return True

def evalueaza_expresie(A, B, C):

   return A.intersection(B.union(C))

def main():

   with open("multimi5IN.txt", "r") as fin:
       n = int(fin.readline().strip())
       seturi = {}
       for _ in range(n):
           linie = fin.readline().strip()
           set_nume = linie[0]
           set = parseaza_set(linie)
           if set is None:
               with open("multimi5OUT.txt", "w") as fout:
                   fout.write("Datele nu corespund restrictiilor impuse\n")
               return  
           seturi[set_nume] = set
       expresie = fin.readline().strip() 
   if not verifica_restricții(n, seturi, expresie):
       with open("multimi5OUT.txt", "w") as fout:
           fout.write("Datele nu corespund restrictiilor impuse\n")
       return
   A, B, C = seturi['A'], seturi['B'], seturi['C']
   rezultat = evalueaza_expresie(A, B, C)
   with open("multimi5OUT.txt", "w") as fout:
       fout.write(f"{len(rezultat)}\n")
       for element in sorted(rezultat):
           fout.write(f"{element} ")
       fout.write("\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>