infoarena

Aici puteţi discuta despre problema Chiftea (http://infoarena.ro/problema/chiftea).

Asta ce vrea sa spuna? -2-ul din parenteza.

In functie de caz, solutia este 4*(radical(N)+1) sau 4*(radical(N)+1)-2.

unde pot gasi solutia la problema asta? :oops:

http://infoarena.ro/winter-challenge-1/solutii

tnx a lot>:D< am luat suta :banana:

Cine poate sa imi dea si mie un contra-argument la problema asta? va rog:D:D:D

raspunsurile corecte fiind:

Pentru exemplul tau mie nu imi da asa ci asa :

Pai din 5 patratele ar trebui sa fie [][][][][] si daca numeri laturile sunt 12 aici e greseala mea si cu algoritmul meu iau 0 puncte  .

pentru n = 5 aranjamentul este:
 _  _
|_|_|_
|_|_|_|

deci perimetrul minim este 10.

Mersi eu credeam ca numai patrate si dreptunghiuri se pot forma . Tanks

Si am o intrebare cum ne dam seama cand acoperim o linie cu patrate si cand acoperim doua . Eu mam gandit ca daca n este par avem mai multe linii si daca e impar numai una  .

poti sa pui mai multe linii si ptr numere impare. De fapt sunt chiar foarte putine numere ptr care pui numai o singura linie. Mai gandestete.

Multumesc mult de tot ai un + la kama de la mine . Am luat 100 .

sa inteleg ca pt n=4 raspunsul este ?10?
                  _ _
pai nu vine  |_|_|
                |_|_|       adica 8?

Pentru 4, 8 da:D

pai mai sus fireatmyself a postat altceva... si asta m-a indus in eroare. Multumesc oricum, acum incerc sa o rezolv, nu pare prea grea.

cum arata figura pentru n=20 ?  #-o

deci perimetru e 18

Am si eu o problema, eu cum as putea afla cat este sqrt(n) fara functia sqrt din cmath? Altfel imi da tle daca folosesc math.h...

Poti folosi cautarea binara, insa ma indoiesc ca e mai eficienta. ( trebuie sa cauti un nr x a.i. x*x = n ). Problema asta se rezolva cu formula, care e aplicata direct. Deci complexitatea timp e O(1). Nu trebuie sa ai tle-uri.  :)

Eu ori nu mă prind de ceva, ori greşesc urât de tot. Adică eu am complexitate O(n), răspunsurile le aflu cu ajutorul formulei, dar tot timpul iau tle. Am încercat chiar şi căutare binară (mulţumesc pentru sfat) dar tot nu merge. Adică dacă trimit o sursă care doar face de t ori sqrt(n), tot iau tle şi cu timpi foarte mari. ](*,) ](*,)

Deci azi mi-a fost dat să trăiesc altă dezamăgire legată de folosirea streamurilor. Eu sunt obişnuit să lucrez cu streamuri, deoarece le scriu mai repede faţă de printf, etc, dar am încercat şi cu stdio.h, şi am luat 100.Mi se pare aiurea, având în vedere că auzisem că în standard fstream e mai rapid. :?
(Mă scuzaţi că nu ştiu să editez mesajele, astfel încât postez de două ori consecutiv)

Ai putea sa incerci sa folosesti streamuri, dar in loc de endl sa pui '\n'. S-ar putea sa intre asa. S-a mai discutat despre faptul ca endl goleste buffer-ul si face afisarea sa mearga mai greu.

Pentru ca sa-ti iti editezi mesajele exista un buton "modifica" in coltul dreapta sus al fiecarui mesaj de-al tau.

Am o problema: folosesc o formula, m-am uitat la raspunsuri si am vazut ca e aceeasi, dar iau WA pe toate testele.

In plus, daca folosesc <fstream> si using namespace std in loc de <fstream.h>, in calculatorul meu imi da 4 erori si nu ruleaza, dar pe infoarena ruleaza... tot WA...

Ma poate ajuta cineva si pe mine? Si niste teste m-ar ajuta. Multumesc anticipat!

Am mai lasat problema cateva zile, acum m-am uitat iar pe ea si tot nu pricep ce gresesc. Pe testul postat de fireatmyself imi da bine. M-ar mai ajuta niste teste, sa vad si eu ce nu merge si sa corectez.
P.S. Nu-mi apare butonul "EDIT". O fi de la browser?

imi puteti da niste teste mai complicate ?
ori ce dau eu imi da bn:|

de ce am luat doar 50 de puncte la sursa asta(http://www.infoarena.ro/job_detail/1263790?action=view-source)

#include <fstream>
#include <cmath>
using namespace std;
ifstream fin ("chiftea.in");
ofstream fout ("chiftea.out");
int main()
{
    int t,n,sol;
    fin>>t;
    for(int i=t;i>=1;i--)
    {
        fin>>n;
        if(n==1)
            fout<<"4"<<'\n';
        if(n==2)
            fout<<"6"<<'\n';
        if(n==3)
            fout<<"8"<<'\n';
        if(n>=4)
        {
            int x=sqrt(n);
                sol=x*4;
            if(x*x+x>=n and x*x!=n)
                sol+=2;
            if(x*x+x<n)
                sol+=4;
        }
        fout<<sol<<'\n';
    }

    return 0;
}

sqrt poate avea erori de precizie. Daca calculezi sqrt(4) poate sa iti rezulte 1.999999 care devine 1 cand ii faci cast la int.

 Am studiat vreo 20-30 de cazuri si pentru toate codul de mai jos era bun, eu am gasit trei cazuri (cand e patrat perfect, cand nu e patrat perfect si e impar, cand e patrat perfect si e par):

#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
ifstream f("chiftea.in");
ofstream g("chiftea.out");
int t,x,i;
int main()
{
    f>>t;
    for (i=1;i<=t;i++)
    {f>>x;
    if (sqrt(x)==(int)(sqrt(x)))
        g<<x-(pow(sqrt(x)-2,2))+4<<"\n";

    if (sqrt(x)!=(int)(sqrt(x))&&x%2==0)
        g<<x+4<<"\n";

    if (sqrt(x)!=(int)(sqrt(x))&&x%2==1)
        g<<x+5<<"\n";
    }
    return 0;
}
  ](*,)

 :readthis: