#include<stdio.h>
#define size 50
void ReadData(int a[][size],int *n){
    FILE *f;
    f = fopen("tam_giac_so.txt","r");
    if (f == NULL){
        printf("Mo file co loi");
        return;
    }
    int i=0, j;
    while (!feof(f))
    {
        for(j = 0; j <= i; j++) //Doc cac phan tu phia duoi duong cheo chinh thoi toi duong cheo chinh 
            fscanf(f,"%d",&a[i][j]);
            i++;
    }
    *n = i;
    fclose(f);
}
void PrintData(int a[][size],int n){ // a la tam giac so, n la so dong 
    int i,j;
    printf("\nTAM GIAC SO da cho\n");
    for(i = 0; i < n; i++){ // i la dong
        for(j = 0; j <= i; j++) // j la cot
            printf("%5d",a[i][j]);
        printf("\n");
    }
}
// Ham tra ve 1 chi so j nao nam o dong i-1 di xuong Fij lam cho Fij lon nhat
int CS_max(int F[][size],int i,int j){ //Xac dinh phan tu dung truoc phan tu F[i][j]
    if(j==0) return (F[i-1][0] > F[i-1][1]) ? 0:1; // Tra ve tri so 0 neu lon hon va nguoc lai
    if(j==i) return i-1; // Tri so cot la i-1
    if(j==i-1) return (F[i-1][i-2] > F[i-1][i-1]) ? i-2:i-1;
    // Tri so phan tu ben trai lon hon tri so phan tu o giua va ben phai thi tra ve ben trai
    if(F[i-1][j-1] > F[i-1][j] && F[i-1][j-1] > F[i-1][j+1]) return j-1;
    // Tri so phan tu o giua lon tri so phan tu ben trai va ben phai 
    if(F[i-1][j] > F[i-1][j] && F[i-1][j] > F[i-1][j+1]) return j;
    // Tri so phan tu ben phai lon hon tri so phan tu ben trai va o giua
    if(F[i-1][j+1] > F[i-1][j] && F[i-1][j+1] > F[i-1][j+1]) return j+1;
}
//Dung cong thuc truy hoi de tao bang F
void Tao_Bang(int a[][size],int n,int F[][size]){
    int i,j;
    // 2 dong dau tien cua bang F duoc xac dinh cu the
    F[0][0] = a[0][0];
    F[1][0] = a[1][0] + F[0][0];
    F[1][1] = a[1][1] + F[0][0];
    //Tu dong thu 3 tro ve sau
    //Moi phan tu cua bang F duoc xac dinh nho vao dong truoc do
    for(i = 2; i < n; i++)
        for(j = 0; j <= i; j++){
            int k = CS_max(F,i,j); //Tri so cot lon nhat nhat co the di xuong F[i][j]
            F[i][j] = a[i][j] + F[i-1][k]; 
        }
}
void In_Bang(int n,int F[][size]){
    int i,j;
    printf("\nBang F\n");
    for(i = 0; i < n; i++){
        for(j = 0; j <= i; j++)
             printf("%5d",F[i][j]);	// voi moi gia tri i va j thi ta in ra gia tri Fij
    	printf("\n");
        }
}
// Phan tu co gtri lon nhat trong dong cuoi cung
int CS_max_dong_cuoi(int F[],int j){
    int somax = F[0];
    int maxindex = 0;
    int k;
    for ( k = 1;k <=j ; k++)
        if (F[k] > somax){
            somax = F[k];
            maxindex = k;
        }
    return maxindex;    
}
//Tra bang F, nhung xac dinh phuong an tu trong tam giac so (bang a)
void Tra_Bang(int a[][size],int n,int F[][size],int PA[]){
    int i,j;
    // Xac dinh chi so j cua phan tu lon nhat trong dong cuoi cua bang F
    j = CS_max_dong_cuoi(F[n-1],n-1);
    
    //Phan tu cuoi cua duong di tuc la PA[n-1] 
    // La phan tu cua dong cuoi cung bang a, ung voi cot j vua tim thay o tren
    PA[n-1] = a[n-1][j];
    for (i = n-1; i >= 1; i--){
    	// Can cu vao chi so cot j cua dong duoi (dong i) cua bang F
    	// ma xac dinh chi so cot j cua dong tren (dong i-1) cua bang F
        j = CS_max(F,i,j);
        
        // PA[i-1] la phan tu cua dong i-1 cua tam giac so a
        // Ung voi cot j vua tim thay o tren 
        PA[i-1] = a[i-1][j];
    }
}
int GiaPA(int PA[],int n){
    int i;
    int sum = 0;
    for ( i = 0; i < n; i++) sum += PA[i];
    return sum;
}
void PrintPA(int PA[],int n){
    int i;
    printf("\nPhuong an la duong di qua cac so : ");
    printf("\%d",PA[0]);
    for ( i = 1; i < n; i++) printf(" => %d",PA[i]);
    printf("\n\nTong cac so tren duong di la %d\n", GiaPA(PA,n));
}

int main(){
    int a[size][size]; // Luu tam giac so
    int n; // So dong` thuc te cua tam giac so duoc luu o trong file 

    ReadData(a,&n); //Doc vao tam giac a voi pp truyen dia chi
    PrintData(a,n); // In ra tam giac a

    int PA[n]; //Phuong an toi uu : mang co n phan tu
    int F[n][n]; // Bang F : mang 2 chieu co n dong,n cot

    Tao_Bang(a,n,F);
    In_Bang(n,F);

    Tra_Bang(a,n,F,PA);
    PrintPA(PA,n);
    return 0;
}