Rezolvare completă PbInfo #1373 reactivi

Enunt

Într-un laborator de analize chimice se utilizează N reactivi. Se ştie că, pentru a evita accidentele sau deprecierea reactivilor, aceştia trebuie să fie stocaţi în condiţii de mediu speciale. Mai exact, pentru fiecare reactiv x, se precizează intervalul de temperatură [minx, maxx] în care trebuie să se încadreze temperatura de stocare a acestuia.
Reactivii vor fi plasaţi în frigidere. Orice frigider are un dispozitiv cu ajutorul căruia putem stabili temperatura (constantă) care va fi in interiorul acelui frigider (exprimată într-un număr întreg de grade Celsius).

Cerința

Scrieţi un program care să determine numărul minim de frigidere necesare pentru stocarea reactivilor chimici.

Date de intrare

Fişierul de intrare reactivi.in conţine:

  • pe prima linie numărul natural N, care reprezintă numărul de reactivi;
  • pe fiecare dintre următoarele N linii se află min max (două numere întregi separate printr-un spaţiu); numerele de pe linia x+1 reprezintă temperatura minimă, respectiv temperatura maximă de stocare a reactivului x.

Date de ieșire

Fişierul de ieşire reactivi.out va conţine o singură linie pe care este scris numărul minim de frigidere necesar.

Restricții și precizări

  • 1 <= N <= 8000
  • -100 <= minx <= maxx <= 100 (numere întregi, reprezentând grade Celsius), pentru orice x de la 1 la N
  • un frigider poate conţine un număr nelimitat de reactivi

Exemplu

reactivi.in

3
-10 10
-2 5
20 50

reactivi.out

2

Explicație

Sunt necesare 2 frigidere pentru a stoca reactivii.

reactivi.in

4
2 5
5 7
10 20
30 40

reactivi.out

3

Explicație

Sunt necesare 3 frigidere pentru a stoca reactivii.

reactivi.in

5
-10 10
10 12
-20 10
7 10
7 8

reactivi.out

2

Explicație

Sunt necesare 2 frigidere pentru a stoca reactivii.

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

#include <stdio.h>

struct Frigider
         {
           char min;
           char max;
         }f[10001], r[10001];

int Cate, i, j, N;
char min, max;

FILE* Fisier;

char Maxim(char x, char y)
{
  if (x>y) return x;
  else return y;
}

char Minim(char x, char y)
{
  if (x<y) return x;
  else return y;
}

int Cauta(char min, char max)
{
  int i, Unde;
  for (i=1; i<= Cate; i++)
    {
      if ((f[i].max>=min) && (f[i].max<=max)) Unde=i;//am gasit frigiderul i
      if ((f[i].min>=min) && (f[i].min<=max)) Unde=i;//am gasit frigiderul i
      if ((f[i].min<=min) && (f[i].max>=max)) Unde=i;//am gasit frigiderul i
      if ((f[i].max<min) || (f[i].min>max)) Unde=-1; //nu am gasit frigider
    }
  return Unde;
}

void Intersectie(int j, char min, char max)
{
  f[j].min=Maxim(min, f[j].min);//modific temperatura minima din frigider
  f[j].max=Minim(max, f[j].max);//modific temperatura maxima din frigider
}

void Ordoneaza(void)
{                      //sortare prin selectie
  int i, j, ptmin;
  char tmax, tmin;
  for (i=1; i<=N-1; i++)
    {
      tmin=r[i].min; tmax=r[i].max; ptmin=i;
      for (j=i+1; j<=N; j++)
        if (r[j].min<tmin)   //crescator dupa temperatura minima
          { tmax=r[j].max; tmin=r[j].min; ptmin=j; }
        else
          if (r[j].min==tmin)//pentru temperatura minima egala
            if (r[j].max>tmax)     //descrescator dupa cea maxima
              { tmax=r[j].max; tmin=r[j].min; ptmin=j; }
      r[ptmin].min=r[i].min; r[ptmin].max=r[i].max;
      r[i].min=tmin; r[i].max=tmax;
    }
}

int main()
{
  char x, y;
  Fisier=fopen("reactivi.in", "rt");
  fscanf(Fisier, "%d", &N);
  for (i=1; i<=N; i++)
    fscanf(Fisier, "%d %d", &r[i].min, &r[i].max, &x, &y);
  Ordoneaza();      //ordonez intervalele de temperatura
                    //crescator dupa temperatura minima si
                    //descrescator dupa temperatura maxima
  //pun primul reactiv (deci cel cu intervalul cel mai mare)
  //in primul frigider
  f[1].min=r[1].min; f[1].max=r[1].max; Cate=1;
  for (i=2; i<= N; i++)          //pentru toate celelalte
    {
      min=r[i].min; max=r[i].max;
      j=Cauta(min, max);  //caut un frigider in care a mai fost pus ceva
      if (j>0)                //daca gasesc
        Intersectie(j, min, max);//ajustez temperatura din frigider
      else                    //altfel
        {
          Cate++;                //"deschid" un frigider nou
          f[Cate].min=min;       //si pun aici reactivul
          f[Cate].max=max;
        }
    }
  fclose(Fisier);
  Fisier=fopen("reactivi.out", "wt");
  fprintf(Fisier, "%d\n", Cate);
  fclose(Fisier);
  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 #1373 reactivi

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