Rezolvare completă PbInfo #687 liste

Numim listă un sir de numere naturale. Avem la dispoziţie mai multe liste aşezate, în ordine, una sub alta. Spunem că două liste L1 şi L2 sunt vecine dacă L1 este imediat deasupra lui L2, sau dacă L2 este imediat deasupra lui L1. Oricare două liste vecine L1 şi L2 pot fi unificate dacă ele au cel puţin un element comun. Prin unificare, noua listă va avea ca elemente toate elementele din L1 la care se adaugă toate elementele din L2. Listele L1 şi L2 vor dispărea şi în locul lor va apărea noua listă.

Cerința

Determinaţi numărul minim de liste care rezultă după aplicarea unui număr suficient de unificări astfel încât să nu mai existe două liste vecine care să poată fi unificate.

Date de intrare

Fişierul liste.in are pe prima linie un număr natural L reprezentând numărul de liste. Fiecare dintre următoarele L linii descriu, în ordine, câte o listă şi au structura: K A[1] A[2] … A[K]. Primul element notat K reprezintă numărul de elemente din listă. În continuare sunt K numere naturale care reprezintă elementele listei. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Pe prima linie a fişierului liste.out se găseşte un singur număr natural reprezentând valoarea cerută.

Restricții și precizări

  • 1 ≤ L ≤ 100.000
  • fiecare listă iniţială are cel mult 10 de elemente;
  • valorile elementelor listelor sunt numere naturale ≤ 120

Exemplu

liste.in

4
2 0 1
1 0
3 1 3 3
1 2

liste.out

2

Explicație

Avem patru liste. Putem unifica prima și a doua listă, acestea fiind înlocuite cu o singură lista. Apoi putem unifica lista rezultată la primul pas cu lista care iniţial era a treia. Obţinem astfel două liste care nu mai pot fi unificate.


Exemplu

liste.in

7
3 1 11 111 
3 2 22 112
3 2 11 113
3 1 22 6
3 5 55 9
3 7 77 9
3 8 88 6

liste.out

3

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

#include <cstdio>
using namespace std;
#define DIM 100100

struct patru {
    int b1;
    int b2;
    int b3;
    int b4;
};

patru S[DIM];
int N, L, x, i, K;

patru B;

inline int si (patru A, patru B) {
    if (A.b1 & B.b1)
        return 1;
    if (A.b2 & B.b2)
        return 1;
    if (A.b3 & B.b3)
        return 1;
    if (A.b4 & B.b4)
        return 1;
    return 0;
}

inline void sau (patru &A, patru B) {
    A.b1 |= B.b1;
    A.b2 |= B.b2;
    A.b3 |= B.b3;
    A.b4 |= B.b4;
}

int main() {
    FILE *f = fopen("liste.in", "r");
    FILE *g = fopen("liste.out", "w");
    
    fscanf(f,"%d",&L);
    for (;L;L--) {
        B.b1 = B.b2 = B.b3 = B.b4 = 0;
        fscanf(f,"%d",&K);
        for (i=1;i<=K;i++) {
            fscanf(f,"%d",&x);
            if (x <= 30)
                B.b1 |= (1<<x);
            else
                if (x<=60)
                    B.b2 |= (1<<x);
                else
                    if (x<=90)
                        B.b3 |= (1<<x);
                    else
                        B.b4 |= (1<<x);
        }
    
        while (N && si(B, S[N])) {
            sau(B, S[N]);
            N--;
        }

        S[++N] = B;
    }
    fclose(f);
    

    fprintf(g,"%d",N);
    fclose(g);
    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 #687 liste

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #687 liste 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!