484 Numere 5

[•gabitzish1]

vectorul e de 500000...declara'l de tip char...daca nu ai facut asta pana acum..

[•skyel]

si ar cam trebui sa pui declaratia in afara lu main ca sa nu mai fie nevoie sa initializezi vectoru cu 0, sau orice altceva.
Si mai este oricand varianta rezolvarii pe biti, caz in care un int de 20.000 ar fi chiar prea mult...

[•vicenzo_cnu]

asta era... initializam cu 0 charul.... mc pt sfaturi baieti... am luat si eu 100

[•ciprianf]

Eu unul nu inteleg de ce luam vectorul pana la 500.000 avand in vedere ca numarul maxim care poate fii schimbat este 1 milion...poate careva sa-mi explice?

[•Florian]

Nah. Nici eu nu intelegeam ce era cu a treia precizare. Cred ca a modificat cineva enuntul. A fost modificat acum la loc. Ar trebui sa fie bine. 

[•wefgef]

Dubioasa precizarea aia.

Apropo, stiti ca se poate O(1) memorie, nu?

[•Florian]

Nu!  Da niste indicii... presupun ca trebuie retinute niste capete de intervale... dar nu prea imi dau seama de o solutie concreta.

[•skyel]

hmm, cred ca ai putea sa calculezi suma totala din matrice(intra in long long) si sa numeri elementele lipsa. Si asa aflii suma elementelor lipsa si stii cate sunt si ca sunt consecutive.

[•wefgef]

Corect.

Edit:
Stiind cate numere consecutive sunt lipsa si care e suma lor, poti afla usor intervalul cautat.

[•gabitzish1]

Ai pus toata rezolvarea aici... ajungea ce a scris Razvan, sa mai gandeasca omu cum sa'o rezolve..

[•wefgef]

Eh, pot sa editez .

Apropo, solutia asta merge si la OJI fara numere mari. Se puteau folosi numere reale .

Edit: Am editat mai sus, sa se mai gandeasca lumea

[•Florian]

Tot e prea mult. 

[•pishty]

...

Eu am facut mai simplu din mate s=n(n+1)/2 dar in cazul acesta este s=n*n*(n*n+1)/2 dar imi da eroare  pt ca se imparte la 0 dar nu stiu unde 

Cod:

#include<fstream.h>
int main()
{unsigned long n,a[501][501],i,j,nr=0,dif,s,s1=0;
ifstream f("numere.in");
ofstream g("numere.out");
f>>n;
for (i=1; i<=n; i++)
	for(j=1; j<=n; j++)
   	{f>>a[i][j];
       	 if (a[i][j]==0)
       		nr++;
      	  s1+=a[i][j];
      	 }
s=(n*n*(n*n+1))/2;
dif=s-s1;
i=(dif+1)/nr-1;
j=i+nr-1;
g<<i<<" "<<j;
f.close();
g.close();
return 0;
}

va rog cn imi poate zice unde am gresit?

 

Editat de moderator: folositi tag-ul "code" cand postati bucati din sursa

[•byndrsn]

Nu cred ca impartzi la 0, ci primesti segmentation fault.
Fisierele de intrare/iesire sunt numere5.in, numere5.out. Unde folosesti valorile salvate in matricea a? O(1) memorie e suficient.

Later edit: Codul nu compileaza fara "using namespace std" de exemplu. Formula ta nu cred ca e corecta. Pe exemplul:

Cod:

3
1 2 3
0 0 0
0 0 0

iti da 5 10 nu?

[•Vlad-andrei]

 Nu se poate publica testul 8?E singurul care nu imi merge si fiind corectare grupata,primesc doar 50 de puncte.Are valori chiar asa de mari?Multumesc!

[•gabitzish1]

Tu primesti TLE nu Raspuns gresit. La ce te ajuta daca stii pe ce test iti iese din timp? incearca sa mai optimizezi putin si trebuie sa'ti intre in timp.

[•jupanu92]

Memory limit exces pe ultimele 6 teste ( dar nus de ce ca doar am folosit un vector char cu 500.000 de elemente ....... chiar nu mai inteleg nimik.
Daca nam voie sa postez sursa va explic cum am facut si voi imi spuneti ce am gresit daaca vreti
 - am declarat un vector char de 500.000 elemente
  - am citit n
  - dupaia daca n era mai mare de 500.000 initializam vectorul cu 0 pana la 500.000
   - daca era mai mic initializam vecotrul cu 0 pana la n*n
    - dupaia citeam intro variabila fiecare numar;
   - dupaia daca variabila aia nu era 0 pe elementul c[a]='1';
    -dupaia daca n*n este mai mare decat 500.000 atunci faceam un for de la 1 la 500.000 si cand intalneam un '0' ma opream si il afisam si dupaia un for de la 500.000 la 1 si cand gasea un 0 il afisa si se oprea ;
   - daca n*n era mai mic la fel faceam numai ca primul for mergea pana la n*n si al doile de la n*n ..

edit :Cred ca stiu ce e gresit .... cred ca trebuia sa merg pana la 64000 .....
Eu cred ca am procedat corect daca nu va rog sa imi ziceti si mie ce e gresit

[•fireatmyself]

da. poti sa calculezi memoria inmultind dimensiunea fiecarui tablou cu marimea tipului de date al tabloului si adunand rezultatele [...] aici gasesti o lista cu dimensiunile tipurilor de date. o variabila 'long long' are 8 bytes.

te-ai uitat peste ce ti-am scris eu ieri? limita de memorie este 640KB si tu ai declarat mult mai mult, de aceea iei MLE.

cred ca ai inceput sa-ti creezi un obicei prost, intreband de fiecare data cand nu iti iese ceva. incearca sa debughezi sursele, sa cauti singur greselile, pentru ca altfel nu o sa inveti mai nimic... daca nu iese, citesteste hinuturile de pe forum si daca nici atunci nu iese, consulta solutiile oficiale. intreaba de o problema de-abia dupa ce te-ai chinuit vreo 2-3 zile la ea.
nu vreau sa sune ca un repros, ci ca un sfat, si nici nu vreau sa te descurajez in a pune intrebari. sunt convins ca prin munca, vei gasi raspunsul la multe probleme.

[•jupanu92]

Va rog eu mult bagati id meu in lista voastra pls marius_bv21 vreau si eu niste indicatii la ea sau macar spunetimi ce raspuns este la testul 6 si 9 ...... ptr ca eu cred ca este un rezultat mai mare decat vecotrul meu si de aceea este incorect raspunsul meu ....

edit : Gata sa rezolvat ... chiar ca miam creat un obicei prost de fiecare data cand nu imi iese postez mesaje pe forum  .. de acu nu o sa se mai intample

[•wefgef]

Dupa cum am vazut ca ti-au mai sugerat si altii, sfatul meu este sa te chinui mai mult singur, deoarece asa vei fi cel mai castigat. E bine sa intrebi pe forum ce nu stii, insa nu intr-o maniera excesiva.

Renunta la Borland (ai putea sa incepi folosind Dev C++) si invata sa iti faci generatoare si evaluatoare.

Spor la treaba!

[•jupanu92]

Da am invata alt limbaj si am renuntat la borland ... se vede foarte mult diferenta erau multe pr care nu imi mergeau din cauza asta iar acu imi merg dar asta nici acu nu imi merge ptr ca folosesc un vector char cu multe elemente am marit numarul de elemente pana la limita memoriei dar tot iau incorect pe 2 teste...

[•toni2007]

Da am invata alt limbaj si am renuntat la borland ...

adica ai trecut la pascal? ca pana la urma devu e tot c++ deci e ac limbaj

[•jupanu92]

Nu ma refeream la asta ci la faptul ca nu mai folosesc citirea cu stream-uri ci cu scanf care parerea mea este de 10 ori si de aceea acu iau mai usor 100 la pr inainte aveam 10 pr incercate acu am doar 3 ..eroarea mea mam exprimat gresit

[•codrin]

nu inteleg dc imi da MLE la 3 teste 
 am declarat vectoru bool de 500000 si in rest nu am nimic ce ar putea iesi atat din memorie si totusi nu iau decat la 70 % din teste
ajutati-ma va rog
 

[•fireatmyself]

e declarat global? daca e declarat global, ai grija sa nu faci multe apeluri recursive.