486 Reactivi

[•jupanu92]

Am o intrebare la uitati programul meu si sputetimi si mie daca as putea sa modific ceva la el astfel incat sa obtin 100 de p sau trebuie sa ma gandesc la alt algorit mai eficient ?

Cod:

#include<fstream>
using namespace std;
int main()
{int n,j,i,nr;
 int tempmin[250],gasit,tempmax[250],min[8001],max[8001],aux,maxx,minn;
ifstream fin("reactivi.in");
ofstream fout("reactivi.out");

fin>>n;
for(i=1;i<=n;i++)
  fin>>min[i]>>max[i];

for(i=1;i<n;i++)
  for(j=i+1;j<=n;j++)        //sortez vectorul in functie de temp minima
     if(min[i]>min[j])
	{aux=min[i];
	 min[i]=min[j];
	 min[j]=aux;
	 aux=max[i];
	 max[i]=max[j];
	 max[j]=aux;
	 }


tempmin[1]=min[1];     //tempmin temperatura minima a fiecarui frigider

tempmax[1]=max[1];      //tempmax temperatura maxima a fiecarui frigider
nr=1;
for(i=2;i<=n;i++)
	 {gasit=0;
	   for(j=1;j<=nr && gasit==0;j++)
		{ if(min[i]<tempmin[j])minn=tempmin[j];
		     else minn=min[i];
		  if(tempmax[j]>max[i]) maxx=max[i];
		      else maxx=tempmax[j];
		  if(minn<=maxx)
		       {gasit=1;
			tempmin[j]=minn;   //vad daca intersectia celor doua intervale este nula
			tempmax[j]=maxx;
			}
		 }
	       if(gasit==0)
		   {nr++;                //daca nu e nula ajustez temperaturile din frigider
		    tempmin[nr]=min[i];
		    tempmax[nr]=max[i];
		    }
	       }

fout<<nr;
return 0;
}

Va rog spunetimi si mie

[•toni2007]

tu ai o sortare in N*N care nu este foarte eficienta... incearca sa pui alta... presupun ca nu stii qsort cu structuri  ... gandeste-te ca tu ai temperaturile cuprinse intre -100 si 100... te ajuta la ceva? (le pui in galeti (cate sunt cu -100 cate cu -99... etc (bucket sort  o(n+200)   )      ) adica incearca bucket sort sau incearca cu qsort... amandoua merg rapid (cu sort din STL nu prea stiu exact cum e pt structuri pt ca eu lucrez in c nu in c++)

[•jupanu92]

Eu cred ca ar trebui sa mariti limita de timp la 0,2 ptr ca la oji e de o secunda ... parerea mea este ca daca voi reusiti  sa faceti pr in timp foarte scurt nu trebuie sa puneti asa de mici limitele de timp . Daca ati mai mari limitele ar putea si cei incepatori sa faca cate ceva ..... daca intra vreun incepator care e prin a 9 a si care a facut pr asta de 100 de p la oji si intra pe site-ul asta ptr prima oara si adauga sursa lui si vede ca a obtinut doar 30 de p eu cred ca nu face altceva decat sa se descurajeze sau sa zica ca e evaluatorul gresit  ptr ca la oji a obtinut 100 de p cum am zis si eu .......
Asta e parerea mea ..... sper sa nu va suparati ... adica nici nu aveti de ce .

[•fireatmyself]

limita de timp difera deoarece sistemele de operare si compilatoarele sunt diferite fata de oji. o sursa evaluata pe windows va rula mai incet decat aceeasi sursa rulata sub linux. gnu face niste optimizari atunci cand executa o sursa, optimizari pe care borland-ul nu le face. plus de asta, sursa oficiala intra sub 0.1 pe infoarena, asa ca nu vad de ce ar trebui marita limita.

[•jupanu92]

Ai dreptate ca intra ca si eu am incercat acu dar totusi nu mi se pare prea diferita sursa de la oji fata de aia a mea si totusi iau TLE pe 3 teste o sa o iau de la capat peste o sap sa vad daca reusesc sa o fac singur de 100

[•fireatmyself]

inseamna ca ai un algoritm mai incet decat cel al comisiei, deci mai poate fi imbunatatit

[•mordred]

Orice frigider are un dispozitiv cu ajutorul caruia putem stabili temperatura (constanta) care va fi in interiorul acelui frigider (exprimata intr-un numar intreg de grade Celsius).

Temperatura minima, respectiv maxima a fiecarui reactiv sunt cuprinse in intervalul [-100,100].

Chiar daca nu are nicio relevanta, si-a dat seama cineva ca intr-un frigider e usor aiurea sa ai 100 de grade? 

[•rEbyTer]

da, lol ....

e geniala faza

[•c_e_manu]

Chiar daca nu are nicio relevanta, si-a dat seama cineva ca intr-un frigider e usor aiurea sa ai 100 de grade?

Bine zici ... eventual daca le zicea incaperi speciale... frigider ce poate fierbe apa?... probabil s-a stricat

[•MciprianM]

Am luat wrong answer pe testul 5 cu sort din stl. Pe testul 5 de la sectiunea downloads/oji2004... cand rulez la mine pe calculator imi baga valori straine in sir.
Cam asa arata partea de sortare.:

Cod:

#include<fstream>    
#include<algorithm>    
using namespace std;    
struct Interval{    
  int x,y;    
};    
Interval reac[8192];    
int cmp(Interval a, Interval b){    
  if(((a).x)>((b).x)) return 0;      
  else{  
    if( ((a).x)==((b).x) )  
        if(((a).y)>((b).y))  
           return 0;  
  }  
  return 1;    
}    
......

sort(reac, reac+n, cmp); 

daca inlocuiesc sortul cu un bubblesort iau 100

[•toni2007]

Fa ceva de genul asta:

Cod:

#include<fstream>    
#include<algorithm>    
using namespace std;    
struct Interval{    
  int x,y;    
};    
Interval reac[8192];    
int cmp(Interval a, Interval b){    
  if (a.x != b.x)
     return a.x < b.x;
  return a.y > b.y;
}    
......

sort(reac, reac+n, cmp);

[•wefgef]

Functia de comparare trebuie sa intoarca true cand primul parametru este stric mai mic decat al doilea, si false in caz contrar.

[•MciprianM]

@toni: imi merge cum ai zis. ms.
@wefgef: de ce nu merge daca returnez true in functia de cmp in cazul in care primul parametru e egal cu al doilea?

[•wefgef]

Pentru ca nu e bine. Nu stiu exact cum functioneaza sortul din STL, dar are nevoie de < strict.

[•MciprianM]

Cu mai mic strict iau 100. O sa tin minte pe viitor.

[•Cristian_B]

Eu nu inteleg de ce pentru
-10 10
10 12
-20 10
7 10
7 8
se afiseaza 2 pt ca mie mi se pare ca trebuie un singur frigider. Scuzati-ma poate gresesc eu aici, anume frigiderul cu -20 10 le cuprinde pe toate, nu?

PS: Ce-i aia karma si cum iti creste si cum iti scade ?

[•Mishu91]

Frigiderele sunt setate la o temperatura, nu un interval de temperaturi.
In exemplul de mai sus, ai un frigider setat la 10 grade si unul la 7 sau 8 grade.

Karma poate fi modificata de ceilalti utilizatori in functie de impresia pe care o faci

[•Cristian_B]

M-am prins, multumesc.

[•robigi]

salut, imi puteti explik shi mie pls k pt un prost dc sortarea asta:

Cod:

void ordonare()  
{    for (int i=100; i>=-100; i--)  
     for (int j=1; j<=n; j++)  
         if (mi[j]==i)  
         {  int aux1=mi[j], aux2=ma[j];  
        for (int k=j-1; k>=1; k--)  
        {    mi[k+1]=mi[k];  
             ma[k+1]=ma[k];  
        }  
        mi[1]=aux1;  
        ma[1]=aux2;  
         }  
}  

este mai ineficienta k bubble? .. ms
[editat de moderator] foloseste tag-ul "code" cand postezi cod pe forum

[•Florian]

void ordonare() 
{    for (int i=100; i>=-100; i--) 
     for (int j=1; j<=n; j++) 
         if (mi[j]==i) 
         {  int aux1=mi[j], aux2=ma[j]; 
        for (int k=j-1; k>=1; k--) 
        {    mi[k+1]=mi[k]; 
             ma[k+1]=ma[k]; 
        } 
        mi[1]=aux1; 
        ma[1]=aux2; 
         } 
} 

Chiar nu inteleg ce faci acolo, dar banuiesc ca in loc de

Cod:

 mi[1]=aux1;  
        ma[1]=aux2;  

ar trebui sa pui

Cod:

mi[j] = aux1; ma[j] = aux2;

Asta e ceea ce am remarcat. S-ar putea sa fie si altceva. Incearca totusi o sortare O(N) [ hint: foloseste faptul ca mi[] si ma[] sunt foarte mici. (din intervalul -100,100) ]

[•Prostu]

salut, imi puteti explik shi mie pls k pt un prost dc sortarea asta:

Cod:

void ordonare()  
{    for (int i=100; i>=-100; i--)  
     for (int j=1; j<=n; j++)  
         if (mi[j]==i)  
         {  int aux1=mi[j], aux2=ma[j];  
        for (int k=j-1; k>=1; k--)  
        {    mi[k+1]=mi[k];  
             ma[k+1]=ma[k];  
        }  
        mi[1]=aux1;  
        ma[1]=aux2;  
         }  
}  

este mai ineficienta k bubble? .. ms

Sortarea este corecta, si are complexitatea O(n²), deci in cazul problemei de fata difera fata de bubble-sort doar printr-o constanta.
O rezolvare a problemei folosind acest algoritm nu va intra in timp, cum nu intra nici folosind algoritmul bubble-sort. Trebuie folosita o sortare in O(n*log(n)) sau O(n).

[•robigi]

aha ms de raspuns (o sa ma gandesc la faptu k valorile is mici nush ink nu miam dat seama de nik da vad io) shi ink nush ces alea cu sortari shi functii in O(n*logn) sau orice fel de structuri imbunatatite shi nici nush de unde sanvat asta e marea mea dilema oricum ms

[•c_e_manu]

Mie mi-a intrat cu sortarea asta, nu am folosit Quick sau Merge...

Cod:

for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
		if(a[i].y>a[j].y)
		{	aux=a[i];
			a[i]=a[j];
			a[j]=aux;
		}

[•robigi]

se poate oricum mi-am dat seama de cum s-ar putea sorta mult mai eficient shi acum iau 100 

[•zloteanu.adrian]

Cod:

#include<fstream.h>
#include<algorithm>
struct casa {int a,b;};
int func(casa a,casa b)
{if(a.a==b.a)
return a.b<b.b;
return a.a<b.a;}
int main()
{int n,i,frig=1,nr;
casa v[101];
...
sort(v+1,v+n+1,func);
...
return 0;}

Da eroare: "sort was not declared in this scope"