Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (111)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (50)
Tipul înregistrare (26)
Recursivitate (57)
Alocarea dinamică a memoriei (2)
Liste înlănţuite (25)
Algoritmul lui Lee (1)
Clasa a XI-a
Metoda "Divide et impera" (12)
Metoda Backtracking (86)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (40)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (14)
Programare vizuală în C# (19)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)
Se citeste un numar natuural n si apoi in intervale inchise cu limitele numere intregi.
a) Calculati si afisati numarul maxim de intervale care se intersecteaza.
b) Determinati numarul maxim de intervale disjuncte si afisati-le.
Exemplu:
6
1 3
4 6
5 7
2 6
3 10
8 10
a) 4 (intervalele care se intersecteaza sunt [4,6], [5,7], [3,10] si [2,6]
b) [1,3] [4,6] [8,10] 3

#include<fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

struct interval {int a,b;};

void citire(interval &x)
{
	fin>>x.a>>x.b;
}

void afisare(interval x)
{
	fout<<"["<<x.a<<","<<x.b<<"] ";
}

void ordonarea(int n, interval x[100])
{
	int i,gata;
	interval aux;
	do
	{
		gata=1;
		for(i=1;i<n;i++)
			if(x[i].a>x[i+1].a) 
			{
				aux=x[i];
				x[i]=x[i+1];
				x[i+1]=aux;
				gata=0;
			}
	}
	while(!gata);
}

void ordonareb(int n, interval x[100])
{
	int i,gata;
	interval aux;
	do
	{
		gata=1;
		for(i=1;i<n;i++)
			if(x[i].b>x[i+1].b) 
			{
				aux=x[i];
				x[i]=x[i+1];
				x[i+1]=aux;
				gata=0;
			}
	}
	while(!gata);
}

int main()
{
	int n,i,max1=0,max2=0,k,ls,p;
	interval x[100];
	fin>>n;
	for(i=1;i<=n;i++) citire(x[i]);
	ordonarea(n,x);
	k=1;
	ls=x[1].b;
	i=2;
	while(i<=n)
	{   if(x[i].a<=ls)
		{
			k++;
			if(x[i].b<ls) ls=x[i].b;
		}
		else
		{
			if(k>max1) max1=k;
			k=1;
			p=i;
			while(x[i-1].b>=x[p].a && i>=1) i--;
			ls=x[i].b;
		}
		i++;
	}	
	if(k>max1) max1=k;
	fout<<max1;	
	fout<<endl;
	
	ordonareb(n,x);
	max2=1;
	afisare(x[1]);
	ls=x[1].b;
	for(i=2;i<=n;i++)
		if(x[i].a>ls) 
		{ max2++;
		  afisare(x[i]);
		  ls=x[i].b;
		}
	fout<<max2;
	fin.close();
	fout.close();
	return 0;
}

20 apr 2024
Site-ul conține 884 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian