688 Patrat

[•astronomy]

Aici puteţi discuta despre problema Patrat.

[•Matei14]

este un lucru ce nu inteleg ... trebuie afisate numerele care au cel putin 2 moduri de scriere ca suma de patrate sau cele care au doar 2 moduri (in enunt scrie cel putin 2 moduri iar la date de iesire scrie 2 moduri) ... sau nu am inteles eu bine... ?

[•gabor_oliviu1991]

doar cele care au doua moduri

[•Mishu91]

Io le-am afisat pe alea care se pot scrie in cel putin doua moduri si am luat 100 

[•shnako]

Ce are mai special ultimul test ? Iau 90 de puncte si la ultimul incorect  ...

[•gabor_oliviu1991]

ai tratat cazut in care nu gasesti nicio pereche de numere care sa respecte probprietatea?...

In cazul in care intre x si y nu exista niciun numar avand proprietatea ceruta, in fisier se va scrie doar numarul 0.

[•shnako]

Tratat ... Nu era de la aia dar ms oricum 
P.S.: Pentru cei care pica ultimul test (am vazut ca nu sunt singurul), incercati cel mai defavorabil caz

[•Vladimio]

mie imi ies exemplele date de iei si cateva exemple de-ale mele.
dar cand am trimis sursa mi-au dat doar 10 p 
puteti sa mai dati si alte exemple va rog ?

[•vlad_oltean]

  sursa mea foloseste 3 int-uri si 2 bool-uri ca variabile. De unde am 200 de kile de memorie folosita? 

[•danalex97]

  
Programul meu e prea incet
Idei???
P.S.:Lucrez in Pascal

[•miculprogramator]

Am nevoie de putin ajutor la problema asta, iau TLE pe toate testele. Am impresia ca-mi intra intr-o bucla infinita, dar nu ma prind unde  :

Cod:

for (i=1;i<=20000;i++)
        ok[i]=0; 
    for (i=1;i<=sqrt(20000);i++)  
        for (j=i+1;j<=sqrt(20000);j++)
            if (i*i+j*j<=20000) ok[i*i+j*j]=1;
    for (i=X;i<=Y;i++)
        if (ok[i]==1) g<<i<<endl;

[•gabitzish1]

Functia sqrt() mananca ceva timp si tu o apelezi cam de multe ori. Incearca sa retii valoarea intr'o variabila, inainte de for(), si sa parcurgi pana la aia. Sau ar mai merge sa pui asa :

Cod:

for(i = 1; i * i <= 20000; i++)

[•SpiderMan]

Buna. Am vazut pe solutia oficiala http://infoarena.ro/grigore-moisil-2008/solutii o solutie gresita. Acel algoritm afla numerele care se pot scrie ca suma de 2 patrate ,care au minimum o combinatie. In problema se cer toate nr. care se pot scrie ca si o combinatie de 2 patrate, deci nr. 26 nu este bun. Daca o sa faceti dupa acel algoritm o sa observati ca pe 26 si multe alte numere le afiseaza. Eu zic asa: unde scrie asta:

Cod:

daca i * i + j * j <= 20000
          ok[i * i + j * j] = true

Sa arate asa:

Cod:

daca i * i + j * j <= 20000
            ++ok[i * i + j * j] 

Iar ok sa fie de tip short. Iar ultimul pentru o sa verifice daca ok[]<1. Daca este mai mare atunci este solutie.Daca nu nu este!

[•roxana_savulescu]

Exact asa am facut si eu problema.Am facut un vector in care numaram cate sume de patrate imi dau numerele din intervalul (x,y).
Apoi parcurgeam din nou vectorul si le afisam pe cele care erai >=2.
Dar iau 40 de puncte si chiar nu inteleg de ce.Sugestii?

[•VisuianMihai]

cum se poate verifica pe biti daca un numar e patrat perfect?
eu stiam

Cod:

bool patrat(int n)
{
return (n&(n-1))==0;

dar nu imi da, numai pentru unele patrate.

[•SpiderMan]

Nup, aia e pentru putere a lui 2, pentru patrat perfect nu am facut niciodata, dar o sa ma uit .

[•S7012MY]

cum se poate verifica pe biti daca un numar e patrat perfect?
eu stiam

Cod:

bool patrat(int n)
{
return (n&(n-1))==0;

dar nu imi da, numai pentru unele patrate.

Nu se poate verifica daca un numar e patrat perfect be biti. Incearca sa abordezi problema invers