484 Numere 5

[•ucc_5]

Va rog sa mariti limita la 660 Kb, sau daca nu sa imi spuneti ce e gresit in sursa mea de are 3 MLE-uri:

Cod:

#include <fstream.h>   
#define min(a,b) a<b?a:b   
  
ifstream f("numere5.in");   
ofstream g("numere5.out");   
  
int n;   
char v[500001];   
long limita;   
  
void citire ()   
{ long aux;   
 f>>n;   
 limita=min(n*n,500000);   
  for (short int i=1; i<=n; i++)   
   for (short int j=1; j<=n; j++)   
    { f>>aux; if (aux<=limita) v[aux]=1; }   
  f.close ();   
}   
  
int main ()   
{ citire ();     
  long i=1;   
  while (v[i]) i++;   
  g<<i<<" ";   
  i=limita;   
    
while (v[i]) i--;   
  g<<i;   
  g.close ();   
  return 0;   
}  

[editat de moderator] foloseste tagul code cand postezi cod sursa.

[•klamathix]

Pai in mod evident foloseste prea multa memorie 

Uita-te prin restul topicului . Poti gasi multe solutii la aceasta problema  si chiar una care ruleaza in O(1) memorie   

[•andrici_cezar]

Va rog sa mariti limita la 660 Kb, sau daca nu sa imi spuneti ce e gresit in sursa mea de are 3 MLE-uri:

Cod:

#include <fstream.h>   
#define min(a,b) a<b?a:b   
  
ifstream f("numere5.in");   
ofstream g("numere5.out");   
  
int n;   
char v[500001];   
long limita;   
  
void citire ()   
{ long aux;   
 f>>n;   
 limita=min(n*n,500000);   
  for (short int i=1; i<=n; i++)   
   for (short int j=1; j<=n; j++)   
    { f>>aux; if (aux<=limita) v[aux]=1; }   
  f.close ();   
}   
  
int main ()   
{ citire ();     
  long i=1;   
  while (v[i]) i++;   
  g<<i<<" ";   
  i=limita;   
    
while (v[i]) i--;   
  g<<i;   
  g.close ();   
  return 0;   
}  

[editat de moderator] foloseste tagul code cand postezi cod sursa.

Tu cred ca nu ai observat ca scrie ca sunt cifre consecutive
Acest lucru te avantajeaza.
Gandestete ca ai sirul
1 0 0 0 5 6 7 8 9

Suma cifrelor prezente este 36
Sunt 3 numere absente
Suma sirului este 45

Pentru exemplu

Cod:

a=suma_sirului - suma_cifrelor_prezente; //a=9
b=numarul_de_cifre_absente; //b=3
x=(a-(b*b+b)/2)/b; //x=1
pozitie_inceput=x+1; // pi=2
pozitie_final=x+b; //pf=4

sper sa iti foloseasca

[•codrin]

  pffffffff
deci am facut-o in doua moduri...

1. cu vector de 500.000 imi iese la 3 teste din memorie desi pe forum zice lumea ca le-a intrat:

Cod:

#include<fstream.h>

char a[500005];

int main()
{
 ifstream fin("numere5.in");
 ofstream fout("numere5.out");
 long i,n,aux,auxi;
 fin>>n;
 aux=n*n;
 if(aux>500000)
	aux=500000;
 for(i=1;i<=aux;i++)
	{
		fin>>auxi;
		if(auxi)
			a[auxi]=1;
	}
 for(i=1;i<=aux;i++)
	if(a[i]==0)
		{
			fout<<i<<" ";
			break;
		}
 for(i=aux;i>=1;i--)
	if(a[i]==0)
		{
			fout<<i<<"\n";
			break;
		}
return 0;
}

2. cu sume si iau incorect pe 4 teste si cu formula chiar cea de mai sus pentru capetele de interval

Cod:

#include<fstream.h>

int main()
{
 ifstream fin("numere5.in");
 ofstream fout("numere5.out");
 long i,n,aux,auxi,suma=0,sumb=0,a,b=0,x;
 fin>>n;
 aux=n*n;

 if(aux>500000)
	aux=500000;

 for(i=1;i<=aux;i++)
	{
		suma+=i;
		fin>>auxi;
		if(auxi)
			sumb+=auxi;
		else
			b++;
	}

 a=suma-sumb;
 x=(a-(b*b+b)/2)/b;

 fout<<x+1<<" "<<x+b;

 fin.close();
 fout.close();

return 0;
}

deci pe bune nu stiu care e greseala in niciuna dintre ele dar ma frustreaza 0-ul 

[•andrici_cezar]

Pai la varianta a doua vezi ca tu trebuie sa stii cate numere nu sunt, si suma celor care sunt si inca ceva suma aia care creste cu i este egala cu suma=(n*n*n*n+n*n)/2  .. Si apoi faci ce ti-am zis:D 

Ai incercat sa pui 500001?

[•codrin]

nu inteleg ce vrei sa spui...ce nu e corect mai exact la varianta a doua??
suma=suma numerelor de la 1 la n(da ma rog are si formula n(n+1)/2 dar nu e asta marea problema)
sumb=suma numerelor care sunt
b=cate nu sunt
a=suma celor care nu sunt

ce imi mai trebuie in afara astora?

[•andrici_cezar]

vezi ca 50000*500000 depaseste long trebuie sa pui long long  scz la inceput eram cam somnoros  am testat sursa ta cu long long si ia 100;) noroc in continuare

[•codrin]

pfff...corect...uitasem de asta
ms fain 

[•zloteanu.adrian]

http://infoarena.ro/job_detail/309913
chiar am nevoie de ajutor
am lucrat 5 ore azi la ea si tot nu functioneaza

[•Robytzza]

nu e open source, deci nu pot sa vad cum ai facut, poti incerca sa lucrezi pe biti, sau sa incerci cu hasuri, ma gandesc ca intra in memorie asa

[•zloteanu.adrian]

nu siu ce inseamna sa lucrezi pe biti
oricum,uite sursa

[•Flloryn]

Buna! Va rog sa ma ajutati si pe mine! Lucrez la problema asta de ceva vreme. Am facut un cod simplu dar nu imi dau seama de ce primesc 4 TLE pe ultimele teste cand practic eu fac doar un for pana la n*n. Lucrez in pascal. Iata codul:

         

Cod:

# program pascal;  
#   var f,g:text; n,x,nr,s,nr2,dif,p,sl:int64; j,i:longint;  
#   begin  
#   assign(f,'numere5.in'); reset(f);  
#   assign(g,'numere5.out'); rewrite(g);  
#   readln(f,n);  
#   sl:=0;  nr:=0;  
#   for i:=1 to n*n do  
#            begin  
#            read(f,x);  
#            if x=0 then nr:=nr+1;  
#            sl:=sl+x;  
#            end;  
# n:=n*n;  
# s:=(n*(n+1)) div 2;  
# dif:=s-sl;  
# nr2:=nr-1;  
# p:=nr2*(nr2+1) div 2;  
# dif:=dif-p;  
# i:=dif div nr;  
# j:=i+nr2;  
# write(g,i,' ',j);  
# close(f);  
# close(g);  
# end.  

HELP ME, PLEASE!!!! 

[•andrici_cezar]

vezi daca n*n>500000 sa reintializezi n*n cu 500000 si asa ar trebui sa iti mearga

[•Flloryn]

multumesc mult cezar! foarte repede ai raspuns! am luat in sfarsit 100   iti multumesc tare mult!

[•bacerandrei]

Am si eu o nedumerire. Deci eu fac in felul urmator: calculez suma primelor n*n numere cu formula n*n*(n*n+1)/2, apoi in timp ce citesc numerele le fac suma si aflu cate din ele sunt egale cu 0. Aflu prin diferenta suma numerelor lipsa (sa zicem dif). Stiind ca acestea sunt consecutive ele vor avea forma a , a+1, a+2, ... , a+nr-1 (unde nr reprezinta numarul valorilor egale cu 0). Asadar primul numar va fi egal cu [dif-(nr*(nr-1)/2)]/nr, iar ultimul egal cu primul+nr-1. Cu toate acestea...pe 9 teste obtin mesajul incorrect. Imi poate spune va rog cineva ce este gresit in rationamentul meu? 

[•toni2007]

Iti trebuie long long.

[•bacerandrei]

Cu exceptia lui n toate variabilele ce intervin in programul meu sunt declarate long long

[•toni2007]

Trebuie sa faci cast la long long, daca ai sa zicem s long long si n int, si vrei sa faci s = n * n * (n -1), trebuie s = 1LL * n * n * (n -1).

[•bacerandrei]

Mii de multumiri Toni am reusit sa iau 100

O informatie foarte utila pe viitor

[•dornescuvlad]

Cod:

#include<iostream>
#include<fstream>

using namespace std;

ifstream f("numere5.in");
ofstream g("numere5.out");

int n;
char v[500001];
long int x,i,m;

int main()

{   
	
	f>>n;
	
	if(n*n>500000)
		m=500000;
	else
		m=n*n;
	
    for(i=1;i<=m;i++)
	{
		f>>x;
	    v[x]=1;
	}	
		
		
    for(i=1;i<=m;i++)
	{
        if(v[i]==0 && v[i-1]==1)
		    g<<i<<" ";
		if(v[i]==0 && v[i+1]==1)
		    g<<i;
	}
return 0;
}

un WA pe testul 9, si 4 MLE. Imi spuneti si mie ce e gresit va rog?

Folosesti prea multa memorie. Incearca fara vector.  

pai cum se face fara vector? la comentarii scriau toti ca au facut cu vector

[editat de moderator] ai postat consecutiv...

[•Florian]

Poti face si cu vector. Am gresit eu. Uite, aici:

   for(i=1;i<=m;i++)
   {
      f>>x;
       v

• =1;

   }

x poate fi mai mare de 500.000. Pune conditie!   Mai citeste o data formatul datelor de intrare.

[•dornescuvlad]

nu inteleg, de ce iau Memory Limit Exceeded, ce gresesc?
am dat m=n*n si iau killed by signal 11 pe unul, pe restul mle
am pus long long la toate si iau mle


int n;
char v[500001];
long long m;
long int i,x;


//nu va mai deranjati sa raspundeti ca am aflat greseala/greselile

[•lsorin_94]

shirul de nr incepe de la 1.. ?

[•SpiderMan]

Da, de la 1 la N*N

[•lsorin_94]

poate sa imi spuna cineva de ce nu primesc mai multe puncte??

Cod:

program num5;
const r=1;
type vec=array [1..1000000] of word;
var i,n:longint;
    st,s0,s,sfi:longint;
    k:integer;
    a1,an:longint;
    a:vec;
    f,t:text;
begin
  assign(f,'numere5.in');
  reset(f);
  assign(t,'numere5.out');
  rewrite(t);
  read(f,n);
  n:=n*n;
  for i:=1 to n do
    read(f,a[i]);
  {-----------------------}
  k:=0;s:=0;
  for i:=1 to n do
    if a[i]=0 then k:=k+1
      else S:=s+a[i];
  a1:=1;
  an:=n;
  st:=((n+1)*n) div 2;
  S0:=St-S;
  sfi:=S0*2 div k;
  a1:=(sfi-(k-1)) div 2;
  an:=a1+(k-1);
  {-----------------------}
  write(t,a1,' ',an);
  close(f);
  close(t);
end.