017 Triunghi

[•fluffy]

Aici puteţi discuta despre problema Triunghi.

[•LordAnta]

Presupun ca solutia nu este unica, nu?
Pentru ca pentru

Exemple

triunghi.in    triunghi.out
3 34            13
                  6 7
                  1 5 2
 

mai gasit si solutia

12
9 3
7 2 1

[•ParrAzitU]

Restrictii si observatii

§         1 ≤ N ≤ 18

§         1 ≤ S ≤ 1.000.000

§         Daca sunt posibile mai multe solutii se va afisa doar una

eu cred ca nu e unica.  

[•LordAnta]

N-am mai vazut ultima conditie!!! Trebuie sa-mi iau ochelari!!!

Imi puteti da un exemplu mai complex ptr ca oricat debug dau, nu-mi dau seam unde am gresit!!!

[•mips]

Va rog sa-mi spuneti cum se poate revolva problema clasica a "platii unei sume cu diferite monede fara a da rest" in afara de backtracking(asta nu se incadreaza in 0.1 secunde) .

[cristi8]

in afara de backtracking(asta nu se incadreaza in 0.1 secunde)

ba da  

[•johny]

A incercat cineva sa rezolve cu ecuatia diofantica?

  Daca are cineva idee cum se poate determina o solutie
particulara pt o ecuatie diofantica il rog sa scrie adresa

[•supernova]

In problema se specifica ca in fisierul de iesire vor fi scrise pe linia i cate i numere intregi strict pozitive care descriu linia i din triunghi. E ciudat ca am trimis programul meu care afisa si zerouri (cel putin pentru cele doua exemple din enunt), si am luat 100 .

[•domino]

In problema se specifica ca in fisierul de iesire vor fi scrise pe linia i cate i numere intregi strict pozitive care descriu linia i din triunghi. E ciudat ca am trimis programul meu care afisa si zerouri (cel putin pentru cele doua exemple din enunt), si am luat 100 .

Hmm, esti sgiur de asta?
M-am uitat in verificatorul la problema asta si este cam asa

Cod:

        ...
        for (i = 0; i < N; i++)
        for (j = 0; j <= i; j++)
            fscanf(f, "%d", A[i] + j), Sum += A[i][j];
        fclose(f);
        ...

deci n-ar trebui sa mearga daca tu mai afisezi si altceva in afara de i numere

[•supernova]

Nu am pus numere in plus, ma refeream la faptul ca o parte din acele numere erau 0. Deci ar trebui eventual specificat clar in enuntul problemei ca e vorba de numere pozitive (nu neaparat nenule).

[•domino]

Nu am pus numere in plus, ma refeream la faptul ca o parte din acele numere erau 0. Deci ar trebui eventual specificat clar in enuntul problemei ca e vorba de numere pozitive (nu neaparat nenule).

Am modificat evaluatorul mai bine... voi incearca sa fac si o reevaluare  

[•wefgef]

la aceasta problema... k si la ink alte cateva... primesc TLE orice as face.

am trimis o sursa care arata cam asa:

Cod:

var f:text;
    n,s:longint;

begin
  assign(f,'triunghi.in');reset(f);
    read(f,n,s);
  close(f);
end.

si primesc TLE pe toate testele.

eu cred k nu se poate face citirea atunci knd datele de intrare sunt mari.
si la problema numere prime patesc la fel. am trimis o sursa kre nu facea nimic si pe 4 teste am luat WA si pe celelalte 6 TLE. si la fractii... pe 2 teste merge, pe 8 TLE...

[•HeLLHeiM]

la aceasta problema... k si la ink alte cateva... primesc TLE orice as face.

am trimis o sursa care arata cam asa:

Cod:

var f:text;
    n,s:longint;

begin
  assign(f,'triunghi.in');reset(f);
    read(f,n,s);
  close(f);
end.

si primesc TLE pe toate testele.

eu cred k nu se poate face citirea atunci knd datele de intrare sunt mari.

Aceeasi citire o am si eu, dar am luat 100. Poate e de la implementare, mai gandeste-te.

[•filipb]

Probabil evaluatorul asteapta un posibil raspuns si tine programul tau "agatat". (desi e ilogic, dar de altceva de ce ti-ar da TLE?) Oricum, o simpla citire a doua numere (oricat de mari ar fi ele  :lol: ) este realizata instantaneu. Nu mai trimite surse din astea care fac doar citirea si incearca sa faci pur si simplu un algoritm. La fel si la problema "fractii" (eu faceam de ex. initializari in O(n) si nu mi-a dat TLE cum iti da tie pe for-ul cu instructiunea vida...)

 bubbleSORT

[Later edit: Incearca sa citesti datele de intrare cu READLN!]

[•wefgef]

pai tocmai asta e, initial trimisesem o sursa care facea ceva si de la care ma asteptam la 100 de pct. (am citit si cu readln, to TLE primesc).

acum am trimis o sursa unde sar peste citire, iar n si s sunt constante - n=18 si s=1000000. mi se incadreaza in 0.05 sec si primesc WA. deci e clar ca citirea nu se termina niciodata si din cauza asta iau TLE. cred k o zona de memorie a calculatorului pe care se face evaluarea e stricata, si din cauza asta nu poate sa citeasca.

mi-ati putea da un test sa vad ce primesc?

[•wickedman]

http://info.devnet.ro/forum/viewtopic.php?t=412

[vladut.forum]

Mah, voi cum ati rezolvat problema. Eu am descoperit o ecuatie destul de simpla. ceva de genu x*p+y*q=ceva...(p,q,ceva tb sa le aflati voi), si de aici tb sa aflu x si y. Pai solutia mea si implementarea mea arata a fii corecta. Dar evaluatorul imi da numai 90 pcts. Asa ca m-am uitat mai  bine, nimic gresit. Am mai trimis o sursa care afisa "imposibil", si lua 0, puncte. Sursa mea pica la testul 5(WA). <domino> Poti sa te uiti putin si sa-mi zici ce este testu 5, te rog sa mi le lasi pe privat, doar N e asa de mic (18) deci voi pute testa si manual, vreau sa vad cum se comporta sursa mea pe testu 5. (sa speram sa nu fie evalu, chiar nu este nici un test la care sa dea "imposibil"), ok ms mult <domino>. Voi ce solutii ati gasit...

[vladut.forum]

aa, complexitatea la mine e... O((S-S2)/n); uinde S2 este suma triunghiului cand baza e 1 1 1 1 ....

[•titusu]

Desi a trecut o juma' de an de la ultimul post la threadul asta, ce-i cu testul 5? Am gasit si eu solutia cu ecuatia diofantica, dar testul 5 da WA. Daca se poate....

[•APOCALYPTO]

n mie imi da killed by signal 11  sigsecv la sursa urmatoare
:s1  la mn merge fara probleme pana la n=18 shi s1(am scris s1 in loc de s)= 520.000 shi ceva adik echiv uni triunghi de 18 cu baza numai din 1 shi inclusiv pentru valorile din testele de mai sus nu intzeleg de ce la primul test imi da WA shi la celealte SIGSECV cel puztin indicii par bn

Cod:

#include<fstream.h>
ofstream g("triunghi.out");
int main()
{   long (*a)[20]=new long[20][20],v[20],(*b)[20]=new long[20][20];
    long s;
    long n,i,j,k;
    for(i=0;i<=18;i++)
    {a[i][0]=1;
    a[i][i]=1;
    v[i]=0;}
    for(i=2;i<=18;i++)
      for(j=1;j<=i-1;j++)
       a[i][j]=a[i-1][j]+a[i-1][j-1];
    ifstream f("triunghi.in");
      f>>n;
      f>>s;
    i=n;
    for(i=0;i<=n-1;i++)
      for(k=1;k<=n-i;k++)

       for(j=0;j<=i;j++)
	 v[j+k-1]=v[j+k-1]+a[i][j];


    f.close();
    long s1=0;
    for(i=0;i<=n-1;i++)
	s1+=v[i];

    long *cmax=new long[1000000],(*uz)[20]=new long[1000000][20];
    for(i=0;i<=n-1;i++)
       uz[s1][i]=1;
    for(i=0;i<s1;i++)
       cmax[i]=-1000000;
    for(i=s1+1;i<=s;i++)
       cmax[i]=-1;
    for(i=s1+1;i<=s;i++)
     for(j=0;j<=n-1;j++)
      if(v[j]<=i-s1&&cmax[i-v[j]]>-1)
       {cmax[i]=cmax[i-v[j]]+v[i];
       for(k=0;k<=n-1;k++)
	  uz[i][k]=uz[i-v[j]][k];
       uz[i][j]++;
       }
     for(k=0;k<=n-1;k++)
       b[n][k+1]=uz[s][k];
     for(i=n-1;i>=1;i--)
       for(j=1;j<=i;j++)
	 b[i][j]=b[i+1][j]+b[i+1][j+1];

     for(i=1;i<=n;i++)
       {for(j=1;j<=i;j++)
	 g<<b[i][j]<<" ";
	g<<'\n';
	}

     g.close();



    return 0;

}

am rezolvat generand triunghiul lui pascal apoi un linia n a unui triunghi derivat din acesta retzinuta in vectorul v apoi am folosit ideea de rezolvare de la cunoscuta probleme a rucsacului 0-1 in care v[ i] reprezinta atat costul cat shi greutatea obiectului i obtzinaand astfel ultima linie a triunghiului-solutzie

[Editat de moderator] Foloseste tagul [ code] cand postezi cod sursa.
De asemenea pune niste spatii cand scrii v[ i] deoarece forumul interpreteaza ca vrei sa scrii text italic.

[•mihai_r2005]

Mie imi da numai 10 pct  (singurul raspuns corect e la primul test). Mi-ati putea da un test ca sa vad ce am gresit? Am "fabricat" eu niste teste mai mari decat cele din enuntul problemei si imi dadea raspuns corect.

[•marcelcodrea]

Acolo unde datele de intrare nu genereaza un raspuns unic nu e foarte folositor sa iti dau teste, am postat cateva ca sa vezi ca exista o solutie in caz ca programul tau afiseaza imposibil pe ele. Cel mai util e sa faci un program care citeste din .out si din .in si verifica validitatea triunghiului cerut in .IN(dimensiunea laturii + suma elementelor). Ai putea chiar sa generezi tu date in .IN dar judecand dupa complexitatea problemei ai putea sa gasesti greseala si daca bagi teste de mana.

.IN

Cod:

7 2243

.OUT

Cod:

362 
324 38 
302 22 16 
288 14 8 8 
278 10 4 4 4 
270 8 2 2 2 2 
263 7 1 1 1 1 1 

.IN

Cod:

5 789312

.OUT

Cod:

157867 
157859 8 
157855 4 4 
157853 2 2 2 
157852 1 1 1 1 

.IN

Cod:

4 100

.OUT

Cod:

28 
22 6 
18 4 2 
15 3 1 1 

[•mihai_r2005]

Am pus in triunghi.in ceea ce ai trimis tu si am primit raspunsuri diferite dar oricum suma nr din fisier era =S si orice numar din triunghi era egal cu suma celor doua de sub el. Daca vrei iti voi trimite sursa. Eventual vb pe messenger ca e mai direct  .

[•Mitza444]

Buna!!!Ma puteti ajuta si pe mine cu o idee de rezolvare??Am observat ca trebuie sa descompun acea suma in n*(n+1)/2 numere ,dar nu imi dau seama cum pot afla acele numere cu propritatea din enunt...

[•pauldb]

Observatia importanta este ca de fapt conteaza doar cum alegi valorile de la baza triunghiului. Ca sa rezovli problema nu strica sa fii familiar cu Problema rucsacului si cu programarea dinamica in general.