484 Numere 5

[•alexandru92]

Nu pot sa inteleg de ce primesc kill by signal 11 , pe totate testele mele merge perfect  

[•SpiderMan]

Incearca testele OJI, care sunt aici

[•alexandru92]

Am gasit ce era, cand marcam eu consideram ca un numar apartie intre [ 1, 500 000 ] nu [ 1, 1000000 ].

[•pauldb]

@Simoiu Robert & Dornescu Vlad

Ar trebui sa incetati amandoi. Fiecare aveti cate un - la karma pentru tot al doilea post si aveti destul de multe posturi raportat la data in care v-ati inscris pe site. E destul de clar ca cel mai des spuneti aberatii amandoi. Ar trebui sa va mai opriti din postat intr-una, sa ajutati doar atunci cand sunteti siguri ca sunteti in masura sa faceti asta si sa acordati o mare atentie celor spuse, fie ca cereti sau ca dati sfaturi.

[•SpiderMan]

Dar eu l-am ajutat pe Idomir Alin, poate sa va spuna si el cand intra ...

[•rares192]

Nu intelg de ce la testele 5, 7 si 8 primesc Memory limit exceeded ca eu am impresia ca ma incadrez in memorie

<code>

Cod:

#include<fstream>
using namespace std;

ifstream fin("numere5.in");
ofstream fout("numere5.out");

bool a[500004];

int main()
{
	long c, i, n, b;
	fin>>n;
	
	b=n*n;
	if(b>500003)
	b=500003;
	
	for(i=1; i<=n*n; i++)
	{
		fin>>c;
		if(c<=500003)
		a[c]=true;
	}
	fin.close();
	
	for(i=1; i<=b; i++)
		if(a[i]==0)
		{
			fout<<i<<" ";
			i=n*n+3;
		}
		
	for(i=b; i>0; i--)
		if(a[i]==0)
		{
			fout<<i;
			i=0;
		}
		
fout.close();
return 0;
}

</code>    

Multumesc anticipat pentru ajutor!

Editat de moderator: foloseste tagurile [ code] si [ /code] cand postezi cod, nu <code> </code>.

[•SpiderMan]

Incearca in loc de

Cod:

bool a[500004];

asta :

Cod:

bitset<1000001>a

Si trebuie inclus headerul <bitset>; .

[•toni2007]

Merge si vector < bool >.

[•rares192]

Asa merge. Multumesc mult ! 

[•ana.z]

 

Cod:

#include<stdio.h>
int main()
{int n,i,j;
freopen("numere5.in","r",stdin);
freopen("numere5.out","w",stdout);
scanf("%d",&n);
n=n*n;
char v[500001];
for(i=1;i<=n;i++)
{scanf("%d",&j);
if(j<=500000)
v[j]='1';}
if(500000<n)
n=500000;
for(i=1;i<=n;i++)
if(v[i]!='1')
{printf("%d ",i);
i=n+1;}
for(j=n;j>=1;j--)
if(v[j]!='1')
{
printf("%d",j);
j=0;
}
return 0;}

ce e gresit la sursa asta???imi da la 2 teste memory limit exeeded

Editat de admin: Foloseste tagul "code" atunci cand postezi surse.

[•SpiderMan]

Incearca in loc de

Cod:

char v[500001];

asta :

Cod:

bitset<500001>v

Si trebuie inclus headerul <bitset>; .

[•truenight]

Sursa mea pica la 3 teste. Ma poate ajuta cineva? Multumesc!

Cod:

#include <stdio.h>

#define IN "numere5.in"
#define OUT "numere5.out"
#define N 60000

char v[N + 1];

int main(void) {

    long a, i, n, m;

    for(i = 1; i <= N; ++i) v[i] = 0;

    freopen(IN, "r", stdin);
    freopen(OUT, "w", stdout);

    scanf("%ld", &n);

    m = n * n;
    while(m--) { scanf("%ld", &a); if(a <= N) ++v[a]; }

    for(i = 1; v[i] && i <= n * n; ++i) ;
    printf("%ld ", i);

    for(; !v[i] && i <= n * n; ++i) ;
    printf("%ld", --i);

    return 0;
}

[•SpiderMan]

Pune in loc de N = 60.000, N = 500.000, si ar trebui sa mearga . Si daca nu intra in memorie, incearca variantele de mai sus.

[•maritim]

In sfarsit mi-a dat si mie cu memorie O(1) ! E una dintre probleme "mici" de la care ai ce invata.

[•vendetta]

pt vectorul de marcare puneti limita 1000000...primeam diferite raspunsuri, cand aveam limita 500000: killed by signal , time limit, memory limit iar dupa ce am schibat limita am luat 100 pct

[•calin98]

Lucrez in FreePascal si primesc eroarea Non-zero exit status. Acesta este programul:

Cod:

01.var a:array[1..500,1..500]of longint; 
02.b:array[1..250000]of byte; 
03.f,g:text; 
04.n:integer; 
05.m,min,max,i,j:longint; 
06.begin
07.assign(f,'numere.in'); 
08.assign(g,'numere.out'); 
09.reset(f); 
10.rewrite(g); 
11.readln(f,n); 
12.m:=sqr(n); 
13.for i:=1 to n do
14.        
for j:=1 to n do
15.                
if j=n then readln(f,a[i][j]) 
16.                        
else read(f,a[i][j]); 
17.for i:=1 to m do b[i]:=0; 
18.for i:=1 to n do
19.        
for j:=1 to n do
20.                
if a[i][j]>0 then b[a[i][j]]:=1; 
21.min:=250000; 
22.max:=0; 
23.for i:=1 to m do
24.        
if b[i]<1 then
25.        
begin
26.        
if min>i then min:=i; 
27.        
if max<i then max:=i; 
28.        
end; 
29.write(g,min,' ',max); 
30.close(f); 
31.close(g); 
32.end.

as fi tare recunoscator daca m-ati putea ajuta. Va multumesc.

Editat de admin: Foloseste tagul "code" cand postezi surse.

[•timi96]

cica am memory limit depasit da ce are?
si cica depaseste timpu da nu inteleg numa sa citesc matricia aia si sa trec prin ea inca o data ia mai mult de 0.4 secunde?!?!?!?

[•alexalbu95]

cica am memory limit depasit da ce are?
si cica depaseste timpu da nu inteleg numa sa citesc matricia aia si sa trec prin ea inca o data ia mai mult de 0.4 secunde?!?!?!?

Am vazut sursa ta si iti dau 4 indicii:

1. Nu ai neaparat nevoie de matrice.
2. De a[0] nu ai nevoie
3. Mai citeste o data problema si fii atent la un mic amanunt.
4. In cazul in care iei MLE incearca pe "char".

[•robertstreche]

Incearca in loc de
Cod:
bool a[500004];
asta :
Cod:
bitset<1000001>a
Si trebuie inclus headerul <bitset>; .

imi poate explica si mie cineva ce face o astfel de secventa?

[•veleandu]

imi poate explica si mie cineva ce face o astfel de secventa?

Pe scurt -> e o optimizare de memorie.
Background: Desi bool-ul tine doar 1 si 0, el in memorie ocupa tot un byte, la fel ca si char-ul.

Deci, nu e "chiar" asa de avantajos bool-ul.
Defapt, nu e deloc.

Acum .. ce face acel bitset.
E o structura de date, care iti permite cu niste functii sa iti ti practic un sir de bool-uri la o memorie de 8 ori mai mica.
Bitsetul chiar tine cate un bit pentru un bool, nu 8 ca si tipul de date "bool"

Ce ar trebui sa sti despre bitset ->

Cod:

#include<bitset>
using namespace std;
bitset<100> B;

int main(){
B.set( 10, 1 ); // seteaza a 10-a valoare cu 1
B.test( 10 ); // iti returneaza valoarea bitului 10

Mai multe gasesti aici -> http://www.cplusplus.com/reference/bitset/bitset/ -> iti recomand sa te uiti la exemple si sa citesti explicatiile pt mai multe lamuriri.

Daca vrei, poti sa iti "implementezi" un bitset si manual, dar ai nevoie de ceva cunostinte legate de operati pe biti.

Dar e mai greu, dar principiul e ca un char o sa iti tina 8 bool-uri
Pt fiecare bit, cate un bool
Practic

Cod:

A[x]

devine

Cod:

A[x/8] & ( 1<<( x%8 ) )

// Partea intreaga intra in A[] si restul iti spune bitul
// ca sa afli daca bitul i e setat, faci x&(1<<i)
// daca returneaza ceva != 0, atunci e setat
// defapt poate returna 0 sau 1<<i .. dar asta nu conteaza prea mult

O sa iti fie mai greu sa modifici valorile.
Daca te intereseaza, pot sa completez ..
Dar nu mi se pare mai ok bitsetul, daca te obisnuiesti cu el

[•robertstreche]

mersi mult pentru explicatii am folosit bitset-ul si am luat 100 pct 

[•Johny_Depp22]

Problema asta mi-a dat si mie batai de cap la inceput din cauza memoriei. Dar apoi am rezolvat-o mai eficient, fara matrice si fara vectori, doar cu o mica observatie matematica.

[•Sapientia]

Am incercat sa rezolv cu memorie O(1).Imi intra doar 4 teste..pe celelalte iau incorect.Am observat ca trebuie sa fac "cast"pentru long long..ce inseamna x1LL?

[•freak93]

Cast la long long inseamna sa-ti transformi rezultatul din int (care merge pana la 2^31 - 1) in long long (2^63 - 1). Sunt mai multe feluri:

1) C style : b = (long long)a * c , acum a va f convertit in long long inainte sa fie inmultit cu c

2) C++ style: b = static_cast<long long>(a) * c, la fel ca mai sus

3) Trisand, un pic mai incet, s-ar putea sa te coste (foarte foarte rar) : b = 1LL * a * c, aici 1LL este defapt numarul 1 dar LL de dupa ne spune ca e long long in loc de int. 1LL * a returneaza un long long si nu un int, e chiar a doar ca e long long.

[•vladandrei]

Cod:

#include <iostream>
#include <fstream>
using namespace std;
ifstream  f("numere5.in");
ofstream  g ("numere5.out");
    bool x[500001];
    int i, el, maxx, minn = 0, n, j;

int main(){
    f >> n;
    for (i = 1; i <= n; i++){
        for (j = 1; j <= n; j++){
            f >> el;
            if (el <= 500000){
                x[el]=1;
             }
        }
    }
    if(n*n < 500000){
        for (i = 1; i <= n*n; i++){
            if (x[i] == 0 && minn == 0)
                minn = i;
            else if (x[i] == 0)
                maxx = i;
        }
    }
    else {
        for (i = 1; i <= 500000; i++){
            if (x[i] == 0 && minn == 0)
                minn = i;
            else if (x[i] == 0)
                maxx = i;
        }
    }
    g << minn << " " << maxx;
    f.close();
    g.close();

return 0;
}

Nu inteleg de ce la unele imi da incorect, la altele MLE.
Am incercat si fara sa folosesc vector, doar calculand suma elementelor de pe matrice, daca stiu cate nr imi lipsesc, ca sunt consecutive etc pot sa le aflu, dar la ultimele teste dadea WA.
Eu ma dau batut, habar n-am unde gresesc.