1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
#include <stdlib.h>

int shift( long** tablica, int number,int size) {
	for (int i = 0; i < number; i++) {
		for (int j = 1; j < size - i; j++) {
			if (tablica[j-1][i] > tablica[j][i]) { tablica[j-1][i] = tablica[j][i]; }
		}
	}
	for (int j = 1; j < size - number; j++) {
		tablica[j-1][number] = tablica[j][number] < tablica[j-1][number+1] ? tablica[j][number] : tablica[j-1][number+1];
	}
	for (int i = number+2; i < size; i++) {
		for (int j = 0; j < size - i; j++) {
			tablica[j][i-1] = tablica[j][i];
		}
	}

	return size-1;
};

int* minimum(long** tablica,int size,int* zwrotka) {
	long minimum = tablica[0][0]; zwrotka[0] = 0; 
	for (int i = 0; i<size;i++) {
		if (i == 0) { if (minimum > tablica[0][i]) { minimum = tablica[0][i]; zwrotka[0]=i;} }
	}
	if (tablica[zwrotka[1]-1][zwrotka[2]] < minimum) { minimum = tablica[zwrotka[1]-1][zwrotka[2]]; zwrotka[1]--; }
	if (tablica[zwrotka[1]-1][zwrotka[2]+1] < minimum) { minimum = tablica[zwrotka[1]-1][zwrotka[2]+1]; zwrotka[1]--;zwrotka[2]++; }
	if (zwrotka[1]+1+zwrotka[2] < size and tablica[zwrotka[1]+1][zwrotka[2]] < minimum) { minimum = tablica[zwrotka[1]+1][zwrotka[2]]; zwrotka[1]++; }
	if (zwrotka[2]> 0 and tablica[zwrotka[1]+1][zwrotka[2]-1] < minimum) { minimum = tablica[zwrotka[1]+1][zwrotka[2]]; zwrotka[1]++;zwrotka[2]--; }
	zwrotka[3] = minimum;
	return zwrotka;
}

int* move_zwrotka(int* zwrotka) {
	if (zwrotka[1] == -1) { return zwrotka; }
	if (zwrotka[0] < zwrotka[2]) { zwrotka[2]--; }
	return zwrotka;
}

int* first_minimum(long** tablica,int size,int* zwrotka) {
	long minimum = tablica[0][0]; zwrotka[0] = 0; int mod = 2;
	for (int i = 0;i<size;i++) {
	for (int j = 0;j<size;j++) {
		if (i+j >= size) {continue;}
		if (i == 0) { if (minimum > tablica[i][j]) { minimum = tablica[i][j]; zwrotka[0]=j; } }
		else {
			if (tablica[i][j]+tablica[i-1][j] < mod * minimum) {mod = 1;minimum = tablica[i][j]+tablica[i-1][j]; zwrotka[0]=j;zwrotka[1]=i-1;zwrotka[2]=j;}	
			if (tablica[i][j]+tablica[i-1][j+1] < mod * minimum) {mod = 1;minimum = tablica[i][j]+tablica[i-1][j+1]; zwrotka[0]=j;zwrotka[1]=i-1;zwrotka[2]=j+1;}	
		}
	}}
	zwrotka[3] = minimum;
	return zwrotka;
}

main() {
int size = 5;
scanf("%d",&size);
int original_size = size;
long** tablica;
tablica = (long**) malloc (sizeof(long*)*size);
for (int k = 0; k < size; k++) { tablica[k] = (long*) malloc(sizeof(long)*5); }
for (int i = 0; i < size; i++) {
for (int k = 0; k < size-i; k++) { scanf("%ld",&tablica[i][k]); }
}
//tablica[0][0] = 1; tablica[0][1] = 2; tablica[0][2] = 3; tablica[0][3] = 4; tablica[0][4] = 5;
//tablica[1][0] = 4; tablica[1][1] = 3; tablica[1][2] = 2; tablica[1][3] = 1;
//tablica[2][0] = 3; tablica[2][1] = 4; tablica[2][2] = 5;
//tablica[3][0] = 2; tablica[3][1] = 1;
//tablica[4][0] = 5;
int* wynik;
int suma = 0;
wynik = (int*) malloc (sizeof(int)*4);
wynik[1] = -1;
while(size) {
	wynik = (wynik[1]==-1) ? first_minimum(tablica,size,wynik) : minimum(tablica,size,wynik);
	suma += wynik[3];
//	for (int i=0;i<4;i++) { printf("%d ",wynik[i]);} printf("\n"); 
	size = shift(tablica,wynik[0],size);
	if (wynik[1]==0 and size) { size = shift(tablica,wynik[0],size); wynik[1]=-1; }
	wynik = move_zwrotka(wynik);
}
printf("%ld \n",suma);
/*
for (int i=0; i < dupa; i++) {
for (int j=0; j < dupa; j++) {
	if (i+j >= dupa) {continue;}
	printf("%d",tablica[i][j]); 
	printf(" ");
}
printf("\n");
}
*/
//for (int k=0; k < original_size-1; k++) { free(tablica[k]); }
//free(tablica);
return(0);
}