Robotul Vasile s-a angajat la o fabrică de bomboane. El trebuie să ambaleze bomboanele în cutii. Toate bomboanele au formă dreptunghiulară. Două bomboane sunt de tipuri distincte dacă diferă prin cel puţin una dintre dimensiunile laturilor lor. Robotul determină dimensiunile bomboanelor (exprimate în milimetri) şi trebuie să ambaleze bomboanele în cutii astfel încât în orice cutie să existe exact câte o bomboană de fiecare tip.

Cerința

Scrieţi un program care citeşte dimensiunile bomboanelor şi rezolvă următoarele două cerinţe:
1. determină numărul de tipuri distincte de bomboane;
2. determină numărul maxim de cutii de bomboane pe care robotul Vasile le poate obţine din bomboanele existente, respectând condiţiile din enunţ.

Date de intrare

Fișierul de intrare robot.in conţine pe prima linie cerinţa c care trebuie să fie rezolvată (1 sau 2). Pe a doua linie se află numărul natural n, reprezentând numărul de bomboane. Pe următoarele n linii se află dimensiunile bomboanelor, câte o bomboană pe o linie; o linie care descrie o bomboană conţine două numere naturale separate printr-un spaţiu lg1 lg2, reprezentând lungimile laturilor bomboanei.

Date de ieșire

Fișierul de ieșire robot.out va conţine o singură linie pe care va fi scris un număr natural determinat conform cerinţei c.

Restricții și precizări

2 ≤ n ≤ 500 000
0 < lg1, lg2 < 100
Bomboanele pot fi rotite atunci când sunt plasate în cutii.
Pot exista şi bomboane de formă pătrată (în care cele două laturi au lungimi egale), un pătrat fiind un dreptunghi particular.

Exemplul 1:

robot.in

robot.out

Exemplul 2:

robot.in

robot.out

Explicație

Cele trei tipuri distincte de bomboane existente au dimensiunile 1 2, 3 4, 5 6. Se pot obţine doar două cutii care să conţină câte o bomboană din fiecare tip.

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

//Em. Cerchez 100 puncte
#include <fstream>
#define LMAX 100
#define NMAX 500002

using namespace std;
ifstream fin("robot.in");
ofstream fout("robot.out");
int cerinta, n, nrtip, nrcutii=NMAX;
int nr[LMAX*LMAX];

int main()
{int i, lg1, lg2, aux;
 fin>>cerinta>>n;
 for (i=0; i<n; i++)
     {
     fin>>lg1>>lg2;
     if (lg1>lg2) {aux=lg1; lg1=lg2; lg2=aux;}
     nr[lg1*100+lg2]++;
     }
 for (i=1; i<LMAX*LMAX; i++)
     if (nr[i])
        {nrtip++;
         if (nr[i]<nrcutii) nrcutii=nr[i];}
 if (cerinta==1) fout<<nrtip<<'\n';
    else fout<<nrcutii<<'\n';
 fout.close();
 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 #3382 robot2

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