Rezolvare completă PbInfo #2460 multimi5

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

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 multimi5.in, 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

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

  • 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:

multimi5.in

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

multimi5.out

2
4 8

Explicație

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:

multimi5.in

3
A=2-7/1
B=1-5/1
C=3-9/3
B*A+A*C

multimi5.out

5
2 3 4 5 6

Explicație

Mulțimile au următoarele elemente:
A={2, 3, 4, 5, 6,7}
B={1, 2, 3, 4, 5}
C={3, 6, 9}
Efectuând operațiile obținem:
B*A = {2, 3, 4, 5}, A*C = {3, 6}
B*A+A*C = {2, 3, 4, 5, 6}

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema multimi5:

#include <fstream>
#include <cstring>
#include <cassert>

using namespace std;

ifstream fin( "multimi5.in" );
ofstream fout( "multimi5.out" );

int i,j,n,m,k,a,bitmask[ (1<<16) ],s[20],f[20],r[20],ev[300],st[10010],val[300],norm[300],ans[16 * 10010],ok,mini,bmsk;
char tr,multimea,exp[1010],evexp[1019];
int valori[ 20 ];

int INDEX = 0;

char top()
{
    return evexp[ INDEX ];
}

char pop()
{
    return evexp[ INDEX ++ ];
}

int solveR();

int solveP()
{
    if( top() != '(' )
        return pop()-'0';
    else if( top() == '(' )
    {
        pop();
        int rez = solveR();
        pop();
        return rez;
    }
return 0;
}

int solveI()
{
    int rez = solveP();
    while( top() == '*' )
    {
        pop();
        rez = min( rez , solveP() );
    }
    return rez;
}

int solveR()
{
    int rez = solveI();
    while( top() == '+' )
    {
        pop();
        rez = max( rez , solveI() );
    }
    return rez;
}

int main()
{
    fin>>n;
    assert( n <= 16 );

    fin.get();
    for( int i = 1 ; i <= n ; i++ )
    {
        fin>>multimea>>tr>>valori[i]>>tr>>f[i]>>tr>>r[i];
        norm[ multimea ] = 'A' + i - 1;
        ev[ multimea ] = i;
        assert( f[ i ] <= 1000000000 );
    }
    fin.get();
    fin.get( exp , 10005 );
    k = strlen( exp );
    assert( k >= 3 );
    assert( k <= 1000 );

    for( int i = 0 ; i < k ; i++ )
    {
        if( exp[ i ] >= 'A' && exp[ i ] <= 'Z' )
            exp[ i ] = norm[ exp[ i ] ];
    }

    val[ '+' ] = '+';
    val[ '*' ] = '*';
    val[ '(' ] = '(';
    val[ ')' ] = ')';

    for( int i = 0 ; i < ( 1<<(n) ) ; i++ )
    {
        for( int j = 0 ; j < n ; j++ )
        {
            val[ 'A' + j ] = '1';
            if( ( i & (1<<(j)) ) == 0 )
                val[ 'A' + j ] = '0';
        }
        for( int j = 0 ; j < k ; j++ )
            evexp[ j ] = val[ exp[ j ] ];
        INDEX = 0;
        bitmask[ i ] = solveR();
    }

    ok = 1;
    while( ok == 1 )
    {
        ok = 0;
        mini = 1000000009;
        for( int i = 1 ; i <= n ; i++ )
        {
            if( valori[ i ] <= f[ i ] )
            {
                ok = 1;
                mini = min( mini , valori[ i ] );
            }
        }

        bmsk = 0;
        for( int i = 1 ; i <= n ; i++ )
        {
            if( valori[ i ] == mini && valori[ i ] <= f[ i ] )
            {
                bmsk += ( 1 <<(i-1) );
                valori[ i ] += r[ i ];
            }
        }
        if( bitmask[ bmsk ] == 1 )
        {
            ans[ ++ans[ 0 ] ] = mini;
        }
    }

    fout<<ans[ 0 ]<<'\n';
    for( int i = 1 ; i <= ans[ 0 ] ; i++ )
    {
        fout<<ans[ i ]<<' ';
    }


    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2460 multimi5

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2460 multimi5 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!