Într-un loc îndepărtat amplasat strategic, se află mai mulţi soldați identificaţi prin numere naturale nenule unice. Ordinea și disciplina militară impun aşezarea soldaților în linie la apelul de dimineață. Fiecare soldat a primit la sosirea în unitate numărul său și numerele de identificare ale camarazilor care trebuie să fie în stânga și în dreapta sa la aliniere. Excepţie fac doi soldaţi santinele care primesc doar numărul propriu de identificare şi se vor aşeza pe prima, respectiv pe ultima poziţie din linie. Uneori, unii soldaţi sunt plecați în misiuni, iar apelul de dimineaţă în unitate se face astfel: fiecare dintre cei prezenţi strigă cele trei numere primite – numărul lui, numărul camaradului din stânga lui şi al camaradului din dreapta lui, chiar dacă aceștia lipsesc.

Ei nu ştiu însă că, după un zid, stă pitită spioana Bulbuka, trimisă în recunoaștere. Ea îi ascultă şi înregistrează toate tripletele de numere care sunt strigate. După cele trei numere strigate de fiecare soldat, Bulbuka, fiind foarte inteligentă, deduce corect câte grupuri de soldaţi care și-au strigat prezența sunt până în momentul respectiv. Ea consideră că un grup este format din toţi acei soldaţi care şi-au strigat propriul număr şi care sunt aşezaţi unul lângă celălalt (dacă un soldat a strigat numărul camaradului, acesta din urmă nu este inclus în grup decât dacă a strigat şi el propriul număr).

Cerința

Aflați care sunt numerele de grupuri de soldați deduse de Bulbuka în fiecare moment.

Date de intrare

Pe prima linie a fişierului spion.in se află N, numărul de soldaţi ce îşi vor striga prezența. Pe următoarele N linii se află câte 3 numere x[i], s[i] și d[i], separate prin câte un spaţiu, reprezentând tripletele pe care le strigă fiecare soldat (x[i] numărul soldatului, s[i] numărul camaradului din stânga lui şi d[i] numărul camaradului din dreapta lui).

Date de ieșire

Fişierul de ieşire spion.out va conţine N linii. Pe fiecare dintre cele N linii se va scrie numărul de grupuri dedus de Bulbuka la momentul respectiv.

Restricții și precizări

1 < N < 500000
1 < x[i], s[i], d[i] < 50000000, i=1,2,3,....,N
Soldaţii santinele sunt mereu prezenţi, nu se strigă singuri (dar pot fi strigaţi de către camarazii vecini) și nu fac parte din niciun grup.
Numerele strigate sunt corespunzătoare unei ordini corecte.

Exemplu

spion.in

spion.out

Explicație

Prima dată strigă soldatul 9 care e notat prezent, deci primul grup este format doar din el. Camarazii 2 și 3 ar trebui să fie în stânga și dreapta lui dar nu și-au strigat prezența încă. În consecință, nu fac parte în acest moment din grupul lui 9.

Strigă soldatul 8, se formează două grupuri: {9} și {8}.

Strigă 5, el va intra în grupul lui 8, deci vor fi tot două grupuri: {9} și {8,5}.

Strigă 7, dar pentru că cei doi camarazi nu s-au strigat încă prezenţi, 7 va forma un grup singur. Vor fi acum trei grupuri: {7}, {9} și @{8,5} etc.

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

#include <stdio.h>
#include <bitset>
#include <unistd.h>
#define NMAX (1600000)

using namespace std;

int n = 0;
int grupuri = 0;

int soldati[NMAX];

inline int bindex(int b) { return b / 32; }
inline int boffset(int b) { return b % 32; }

void set_bit(int b) {
    soldati[bindex(b)] |= 1 << (boffset(b));
}

bool get_bit(int b) {
    return (soldati[bindex(b)] & (1 << (boffset(b)))) != 0;
}

int main() {

    freopen("spion.in", "rt", stdin);
    freopen("spion.out", "wt", stdout);

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        int x, s, d;
        scanf("%d %d %d", &x, &s, &d);

        int prezenta = get_bit(s) + get_bit(d);
        grupuri += 1 - prezenta;

        printf("%d
", grupuri);

        set_bit(x);
    }

    fclose(stdin);
    fclose(stdout);

    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 #610 Spion

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

Rezolvare completă PbInfo #610 Spion