infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Dan-Leonard Crestez din Martie 08, 2004, 20:03:49

Titlul: 017 Triunghi
Scris de: Dan-Leonard Crestez din Martie 08, 2004, 20:03:49

Aici puteţi discuta despre problema Triunghi (http://infoarena.ro/problema/triunghi).

Titlul: 017 Triunghi
Scris de: Anton Alexandru din Februarie 19, 2005, 13:34:41

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

Citat

Exemple

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

mai gasit si solutia

Citat

12
9 3
7 2 1

Titlul: 017 Triunghi
Scris de: Bindea Calin din Februarie 19, 2005, 14:55:57

Citat

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. :P

Titlul: 017 Triunghi
Scris de: Anton Alexandru din Februarie 19, 2005, 17:02:56

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!!!

Titlul: 017 Triunghi
Scris de: Pavel Mircea din Aprilie 25, 2005, 18:21:54

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) :?: .

Titlul: 017 Triunghi
Scris de: cristi8 din Aprilie 25, 2005, 21:57:07

Citat din mesajul lui: mips

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

ba da :)

Titlul: Rezolvare triunhi
Scris de: Johny Deep din Aprilie 27, 2005, 07:03:01

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

Titlul: 017 Triunghi
Scris de: Mihai Pantis din Iunie 14, 2005, 09:19:18

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 :).

Titlul: 017 Triunghi
Scris de: Mircea Pasoi din Iunie 14, 2005, 10:37:33

Citat din mesajul lui: supernova

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

Titlul: 017 Triunghi
Scris de: Mihai Pantis din Iunie 14, 2005, 10:53:45

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).

Titlul: 017 Triunghi
Scris de: Mircea Pasoi din Iunie 14, 2005, 13:04:29

Citat din mesajul lui: 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).

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

Titlul: 017 Triunghi
Scris de: Andrei Grigorean din Iulie 02, 2005, 21:23:40

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...

Titlul: 017 Triunghi
Scris de: Alb Gabriel din Iulie 03, 2005, 00:07:21

Citat din mesajul lui: 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.

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

Titlul: 017 Triunghi
Scris de: Filip Cristian Buruiana din Iulie 03, 2005, 09:06:41

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!]

Titlul: 017 Triunghi
Scris de: Andrei Grigorean din Iulie 03, 2005, 10:06:13

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?

Titlul: 017 Triunghi
Scris de: Cristian Strat din Iulie 06, 2005, 08:09:26

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

Titlul: 017 Triunghi
Scris de: vladut.forum din Iulie 09, 2005, 00:50:45

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...

Titlul: 017 Triunghi
Scris de: vladut.forum din Iulie 09, 2005, 00:53:23

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

Titlul: 017 Triunghi
Scris de: Titus C din Ianuarie 24, 2006, 23:27:43

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....

Titlul: Răspuns: 017 Triunghi
Scris de: Dragos din Iunie 25, 2009, 22:47:39

n mie imi da killed by signal 11 sigsecv la sursa urmatoare :annoyed:
: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.

Titlul: Răspuns: 017 Triunghi
Scris de: Richard Mihai Andrei din Septembrie 14, 2009, 22:26:00

Mie imi da numai 10 pct :x (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.

Titlul: Răspuns: 017 Triunghi
Scris de: Codrea Marcel din Septembrie 14, 2009, 22:45:46

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:

Titlul: Răspuns: 017 Triunghi
Scris de: Richard Mihai Andrei din Septembrie 15, 2009, 00:20:11

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 :D.

Titlul: Răspuns: 017 Triunghi
Scris de: Vidrean Mihai din Ianuarie 23, 2012, 19:11:30

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... :sad:

Titlul: Răspuns: 017 Triunghi
Scris de: Paul-Dan Baltescu din Ianuarie 23, 2012, 23:12:55

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 (http://infoarena.ro/problema/rucsac) si cu programarea dinamica in general.

Titlul: Răspuns: 017 Triunghi
Scris de: Vidrean Mihai din Februarie 03, 2012, 23:32:39

Nu poti sa imi decrii un pic mai detaliat rezolvarea problemei??Chiar nu imi dau seama cum as putea gasi numerele acelea de la baza.:D( nu sunt grozav la dinamica)

Titlul: Răspuns: 017 Triunghi
Scris de: Paul-Dan Baltescu din Februarie 06, 2012, 21:11:19

Se calculeaza V[ i ] cu cat se modifica suma totala a triunghiului daca incrementezi cu 1 celula a i-a de pe baza. Se observa ca daca incrementezi cu x celula a i-a, atunci suma totala creste cu x*V[ i ]. Vectorul V il poti calcula brute force, simuland efectiv.

Apoi se face o dinamica foarte asemanatoare cu cea de la problema rucsacului, astfel: dp[ i ][ j ] = 1 sau 0 daca (sau nu) se poate obtine suma j cu valorile V[ 1 ], ..., V[ i ], fiecare putand fi folosita de oricate ori.

Titlul: Răspuns: 017 Triunghi
Scris de: Vidrean Mihai din Februarie 06, 2012, 22:12:03

Am o intrebare.Nu prea am inteles cum faci cu formula de la baza.Deci am un sir V care reprezinta numerele de la baza.Sa presupunem ca avem asa: n=3 si la inceput am pe V la baza numa valori de 1 pe toate pozitiile.O sa am:

Cod:

4
2 2
1 1 1

acestea au suma 11
daca incrementez cu unu pozitia 2:

Cod:

6
3 3
1 2 1

suma este 16,iar tu ai zis ca,creste cu x(adica 1)*V[2]==> creste cu 1,dar creste cu 5
Asta nu inteleg nu ar trebui sa conteze daca numarul care il incrementez i pe pozitia 1 sau n pt.ca atunci nu ar intra in suma finala de acelasi numar de ori ca si un numar care este pe poz dintre 1 si n.

Si daca am determinat poz de la baza de ce mai trebuie sa fac rucsacu pe ele nu ar trebui sa calculez numai liniile de mai sus??(cum determin triughiu doar cu rucsacu??)
Scuze ca tot intreb,dar chiar nu am inteles. ](*,)
Multumesc pt. ajutor [-o<

Titlul: Răspuns: 017 Triunghi
Scris de: Mihai Calancea din Februarie 06, 2012, 22:32:50

Citat din mesajul lui: FMI - Paul-Dan Baltescu din Februarie 06, 2012, 21:11:19

Se calculeaza V[ i ] cu cat se modifica suma totala a triunghiului daca incrementezi cu 1 celula a i-a de pe baza.

Ai inteles gresit ce reprezinta V-ul.

Titlul: Răspuns: 017 Triunghi
Scris de: Paul-Dan Baltescu din Februarie 06, 2012, 22:40:54

Pentru n = 3, V este [3, 5, 3]. V nu reprezinta vectorul valorilor de la baza, ci cu cat creste suma totala daca incrementezi cu 1 o anume pozitie de la baza. Dupa cum bine ai observat, daca baza devine 1 2 1, suma creste cu 5. La fel, daca baza devine 1 3 1, suma mai creste cu 5 si tot asa.

Acum tot ce trebuie sa mai faci este sa gasesti niste valori A1, ..., AN, cu Ai >= 1, astfel incat A1*V1 + ... + AN*VN = S. Pasul dificil este sa vezi daca aceste valori exista si aici trebuie sa faci dinamica de tip rucsac de care ti-am spus mai sus. Valorile efective le poti reconstitui dupa cum am explicat aici (http://infoarena.ro/forum/index.php?topic=6970.0). Avand valorile A1, ..., AN, adica baza triunghiului, este banal sa obtii si rezultatul final.

Titlul: Răspuns: 017 Triunghi
Scris de: George Popoiu din Februarie 07, 2012, 09:58:46

Iau TLE pe trei teste cu N*S, se poate optimiza ceva ? Pentru dinamica declar o matrice bitset cu 2 linii, iar pentru reconstituire una cu N linii.

Ar putea sa fie din cauza declararii matricei cu N linii ? Am citit in topicul dat de Paul ca se poate face reconstituirea si cu un vector, dar nu cred ca e de la asta, pentru ca matricea de bitset de reconstituire ocupa doar ~2MB, ceea ce e foarte putin.

Titlul: Răspuns: 017 Triunghi
Scris de: Vidrean Mihai din Februarie 12, 2012, 22:45:01

Deci nu inteleg de ce nu functioneaza.... ](*,).AM determinat vectorul V cu cat creste suma daca incrementezi cu 1.Dupa am facut rucsacul sa vad daca se poate obtine suma.Am retinut intr-o matrice bool daca b[ i ] [ j ] 1 sau 0 daca DP[j]=DP[ j - V[ i ] ]+V[ i ] sau din DP[ j ].Si daca suma de pe DP[ s ]==s suma care o citesc atunci am pornit de la capat si am daca b[ x ][ y ]==1 atunci icrementez poz x de la baza cu unu si y=y-V[ x ],altfel x=x-1.Pe exemplu merge ,dar per total iau doar 10 pct cu 2 teste TLE si restul wrong answer.
P.S.:In triunghiu pe care il afisez apar si 0-uri ,nu am reusit sa fac altcumva.

Cod:

#include<fstream>
using namespace std;
int tri[20][20],V[20],DP[1000001];
bool B[19][1000001];
int nr;
void back(int n,int x){
	nr++;
	if(x-1>=1 && x-1<=n-1 && n-1>=1)
		back(n-1,x-1);
	if(x>=1 && x<=n-1 && n-1>=1)
		back(n-1,x);
}
int main(){
	int n,s,i,j,x,y;
	ifstream f("triunghi.in");
	f>>n>>s;
	f.close();
	V[1]=V[n]=n;
	for(i=2;i<=n-1;i++){
		nr=0;
		back(n,i);
		V[i]=nr;
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=s;j++){
			if(DP[j-V[i]]+V[i]>=DP[j])
				B[i][j]=1;
			if(j>=V[i])
				DP[j]=max(DP[j],DP[j-V[i]]+V[i]);
		}
	}
	ofstream g("triunghi.out");
	if(DP[s]!=s)
		g<<"imposibil"<<"\n";
	else{
	x=n;y=s;
	while(x!=1 && y!=1){
		if(B[x][y]==1){
			y=y-V[x];
			tri[n][x]++;
		}
		else{
			x--;}
	}
	for(i=n-1;i>=1;i--)
		for(j=1;j<=i;j++)
			tri[i][j]=tri[i+1][j]+tri[i+1][j+1];
	for(i=1;i<=n;i++){
		for(j=1;j<=i;j++){
			g<<tri[i][j]<<" ";
		}
		g<<"\n";
	}
	}
	return 0;
}

Titlul: Răspuns: 017 Triunghi
Scris de: George Marcus din Februarie 13, 2012, 22:28:42

Citat din mesajul lui: George Popoiu din Februarie 07, 2012, 09:58:46

Eu am scos 100 (la limita) cu observatia ca nu e nevoie sa calculez v-ul si rucsacul decat pana la (n+1)/2, deoarece de acolo se repeta in ordine inversa. Declar un bitset de ~n/2 linii si reconstituirea o fac in functie de valorile din bitset.

Titlul: Răspuns: 017 Triunghi
Scris de: TOMA ALEX din Februarie 25, 2012, 20:15:55

Primesc TLE pe testele 2 si 5 si nu imi dau seama dc , se poate sa fie ceva cazuri speciale pe care sa nu le fi atins?
Ma poate ajuta cineva?

Titlul: Răspuns: 017 Triunghi
Scris de: Drumea Vasile din August 10, 2015, 17:45:03

Numerele din triunghi.out trebuie sa fie > 0 sau pot fi si = 0?

Titlul: Răspuns: 017 Triunghi
Scris de: Dragos-Alin Rotaru din August 10, 2015, 21:30:33

În enunţ se specifică strict pozitive, deci > 0.

Titlul: Răspuns: 017 Triunghi
Scris de: Barbu Dorel din August 19, 2015, 21:50:58

Eu am luat 70. Iese de 100 si fara observatia ca ruscacul si vectorul v trebuie facute pana la (N+1)/2 ? Sau e alta chichita?

Titlul: Răspuns: 017 Triunghi
Scris de: Adrian Buzea din Septembrie 27, 2016, 13:56:21

Eu am un program in O(S*N/2) si iau doar 60p pe el :x

Titlul: Răspuns: 017 Triunghi
Scris de: mihai craciun din Octombrie 09, 2016, 19:31:49

Ma ajuta si pe mine cineva, pt ca nu imi iese generarea matricii a.i. sa nu existe elem 0
uitati codul:
#include <bits/stdc++.h>
#define min(a, b)(a < b?a:b)
#define maxi(a, b)(a>b?a:b)
FILE *fin, *fout;
int mat[22][22];int b[22][1000001];int DP[1000000];
long long v[20];
int r[1000001];

int main() {
fin = fopen("triunghi.in", "r");
fout = fopen("triunghi.out", "w");
int n, s;
fscanf(fin, "%d%d", &n, &s);
int i, j, k;

///Generarea vectorului v-cu cat creste elementul de pe pozitia i daca adunam 1 la elementul de pe pozitia i
///se observa ca vectorul v este palindrom
///Ma va ajuta sa scap de TLE
long long sum;
v[0] = n;
v[n - 1] = n;
for(i = 1;i <= n / 2;i++) {
sum = 1;
mat[n] = 1;
for(j = n - 1;j >= 1;j--)
for(k = 0;k < j;k++)
mat[j][k] = mat[j + 1][k] + mat[j + 1][k+1], sum += mat[j][k];
v = sum;
v[n - i - 1] = sum;
memset(mat, 0, 500);
}
//for(i = 0;i <= n - 1;i++)
// printf("%d ", v);

///acum trebuie sa rezolvam problema rucsacului a.i. sa vedem
///daca exista a[0],...,a[n-1] a.i. a[0] * v[0] +...a[n-1] * v[n-1] = s
   for(i=1;i<=n;i++){
      for(j=i;j<=s;j++){
         if(DP[j-v[i-1]]+v[i-1]>=DP[j])
            b[j]=1;
         if(j>=v[i-1])
            DP[j]=maxi(DP[j],DP[j-v[i-1]]+v[i-1]);
      }
      }
   if(DP!=s)
      fprintf(fout, "imposibil");
else {
int x, y;
x=n;y=s;
   while(x>=1 && y >= 1){
         //printf("%d %d %d\n", b
[y], x, y);
      if(b
[y] == 1){
         y-=v[x - 1];
         mat[n]
++;
      }
      else
       x--;
       //if(x == 1)
   }
   //printf("%d %d", x, y);
   for(i=n-1;i>=1;i--)
      for(j=1;j<=i;j++)
         mat[j]=mat[i+1][j]+mat[i+1][j+1];
   for(i=1;i<=n;i++){
      for(j=1;j<=i;j++){
         fprintf(fout, "%d ", mat[j]);
      }
      fprintf(fout, "\n");
   }
}
fclose(fin);)
fclose(fout);
return 0;
}

De asemenea, cum pot sa optimizez(am 4 TLE si 5 WA :sad:)

Titlul: Răspuns: 017 Triunghi
Scris de: Iancu Vlad din Iulie 29, 2017, 16:21:37

totul depinde de primul rand cel mai de jos, baza triunghiului,
daca avem de exemplu N=4 si notam numerele de pe cutiile de la baza triunghiului cu x1, x2, x3, x4 obtinem:
suma bazei este
x1+x2+x3+x4
suma bazei plus cea a nivelului de trei cutii
x1+x2+x3+x4+x1+x2+x2+x3+x3+x4
adica
2x1+3x2+3x3+2x4
iar suma bazei a nivelului cu trei cutii si a nivelului cu doua cutii este
x1+x2+x3+x4+x1+x2+x2+x3+x3+x4+x1+x2+x2+x3+x2+x3+x3+x4
adica
3x1+6x2+6x3+3x4
adica ca sa nu va mai inebunesc cu siruri lungi de adunari, fiecare termen care nu este in margine isi dubleaza numarul de ori de care apare in sir pe masura ce crestem nivelul piramidei(sau al triunghiului dupa caz).
Acum problema e cum facem ecuatia si cum ii gasim solutiile caci sunt patru necunoscute, iar de aici avem exact ce s-a spus mai inainte ca exista solutii multiple