484 Numere 5

[•catalin93]

am si eu o intrebare pt aceasta problema...
Restrictii
0 < N ≤ 1000
Fratele lui Mircea schimba cel putin un numar in fisier.

daca exista un singur numar transformat in 0...atunci eu afisez de 2 ori acel numar sau odata? ca imi cere capetele intervalului transformat in 0

[•Pepelea_Flaviu]

afisezi de doua ori (capetele intervalului .... si [x,x] e un interval)

[•catalin93]

aham mersi oricum pbleme mele apar de la memorie... k imi da sigkill daca dau vectoru de bool la 1 mil... si iau 50 de puncte pt vectoru la 500.000  vreo idee?

[•wefgef]

Citeste pe pagina anterioara. Se poate cu O(1) memorie.

[•zalman]

Help!!
Pe evaluatorul oficial am luat 90 si aici 0.Un singur test corect.
Am un vector char de 64000 si cateva variabile long.
Pe majoritatea imi da wall time limit exceded si pe 2 memory limit exceded. Unde e problema? 

[•c_e_manu]

iti trebuie vector de 500000, nu doar de 64000...si ai grija sa te foloseste de min(n*n, 500000)...

[•zalman]

cu vectorul de 500000 imi iese din timp!

[•zalman]

Am incercat si bool si char!

[•gabor_oliviu1991]

incearca sa faci citirea cu scanf si afisarea cu printf... eu asa am scos 100. cu stringuri mie cel putin nu imi mergea

[•zalman]

cu scanf si printf am facut-o

[•gabor_oliviu1991]

hmmm... defapt iti trebuie vector de 500 002. eu luam 50 de pct cu 2 MLE cu vector de 500 001... cat despre cautarea celor doua capete ale intervalului, daka faceam cu while avea incorect pe 2 teste. am schimbat in for si luam 100. poti incerca, nu asigur ca din aia... oricum problema ii la memorie, ca e foarte la limita

[•Florian]

Vezi ca atunci cand verifici aparitia numerelor, sa verifici doar aparitia acelor numere mai mici decat 500.000. Tu probabil mergi pana la n*n. Mie mi-a mers si o rezolvare cu un vector char[] de 500.000 de elemente. Spor!

ps: Vezi ca problema se poate rezolva si fara vector. [hint: gandeste-te la suma totala din fisier]

[•c_e_manu]

eu am folosit vector bool de 500000 si marcam sumele gasite pana la n*n sau mai mici decat 500000... apoi am parcurs acel vector o data de la inceput si o data de la sfarsit pentru a afla capetele intervalului [x,y]

[•gabor_oliviu1991]

@manu... dupa ce ai zis cum faci tu, acum probabil toti vor lua 100 fara problema. prea evident cum se rezolva problema. nu mai are farmec sa o gandesti, citesti forumul si gata. fi mai putin explicit 

[•zalman]

Pana la urma mi-o mers cu un bool de 500004

[•gabor_oliviu1991]

ps: Vezi ca problema se poate rezolva si fara vector. [hint: gandeste-te la suma totala din fisier]

nu prea vad cum as putea scoate capetele intervalului din suma totala. un hint ceva ?

LE: nu conteaza, am prins ideea

[•shnako]

Se pare ca evaluatorul se face de ras la problema asta ...
Am trimis o sursa, am luat asa : http://infoarena.ro/job_detail/265716
Am mai trimis odata ACEEASI sursa, am luat asa : http://infoarena.ro/job_detail/265717
Am mai trimis inca odata ACEEASI sursa, am luat asa : http://infoarena.ro/job_detail/265718

[•bogdan2412]

Evaluatorul e foarte ok, cand o sa rulezi un program niciodata n-o sa-ti mearga exact la fel cand accesezi memorie prost. In programul tau ai doua while-uri in care iterezi dupa i si i poate sa depaseasca limitele vectorului. Depinde de sistemul de operare sa-ti opreasca programul cand o ia razna cum face al tau pe teste mari si momentul in care ti-l opreste depinde de ce zona de memorie accesezi prost.

Aici sursa ta ia 100, dupa ce corectezi while-urile: http://infoarena.ro/job_detail/265753

As a side note: poti sa iei memory limit exceded si cand trebuie sa iei killed by signal 11.

[•shnako]

Evaluatorul e foarte ok, cand o sa rulezi un program niciodata n-o sa-ti mearga exact la fel cand accesezi memorie prost. In programul tau ai doua while-uri in care iterezi dupa i si i poate sa depaseasca limitele vectorului. Depinde de sistemul de operare sa-ti opreasca programul cand o ia razna cum face al tau pe teste mari si momentul in care ti-l opreste depinde de ce zona de memorie accesezi prost.

Aici sursa ta ia 100, dupa ce corectezi while-urile: http://infoarena.ro/job_detail/265753

As a side note: poti sa iei memory limit exceded si cand trebuie sa iei killed by signal 11.

Intr-adevar era gresita conditia in whileuri. Scuze ca m-am luat de evaluator, nu mi-am dat seama ca acolo iasa Mersi pt sfat 

[•chibicitiberiu]

Salutare
Am rezolvat problema, dar am luat doar 50 puncte pentru ca pentru 2 teste raspunsul e incorect  . De ce???

Cod:

#include <fstream>

using namespace std;

bool nr[250001];

int main()
{
        int n,i,j,temp;
        int min, max;
        ifstream in ("numere5.in");
        in>>n;

        for (i=0;i<n;i++)
            for (j=0;j<n;j++) {
                in>>temp;
                if (temp>0 && temp<250001) nr[temp]=true;
            }

        for (i=1;i<=n*n && i<250001;i++)
            if (nr[i]==false) {min=i; break;}
        while (nr[i]==false && i<250001) i++;
        max=i-1;

        in.close();
        ofstream out ("numere5.out");
        out<<min<<" "<<max;
        out.close();

        return 0;
}

UPDATE: m-am prins acum ca limita era 500 000 nu 250 000, ca eu aveam subiectele de la concurs, nu m-am uitat la cerinta de aici, dar problema e limita de memorie in care nu ma incadrez daca modific..

[•c_e_manu]

Numerele schimbate de fratele lui Mircea sunt mai mici sau cel mult egale cu 500.000

tu ai pus doar 50.001

LE:

Cod:

bool nr[500001];

si ar trebui sa te incadrezi

[•PavelRazvan]

Ce trebuie afisat pentru N=1 ?

[•Florian]

Exact ce iti cere problema.  Fii atent si la a doua restrictie. 

[•PavelRazvan]

multumesc 

[•ucc_5]

Deci e incredibil, imi da MLE la 3 teste si programu e facut perfect. Nu inteleg de ce depasest in halul asta limita.
Macar daca era limita de 660 KB era bine.