USACO : Sorting a Three-Valued Sequence



/*
ID: tausiq11
PROG: sort3
LANG: C++
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 100000
#define LL long long

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Pr(x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++) cout << *it << " "; cout << endl;
#define Set(a, s) memset(a, s, sizeof (a))
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

using namespace std;

int main ()
{
	Rd ("sort3.in");
	Wt ("sort3.out");

	int n; scanf ("%d", &n);
	int a [1000 + 10];
	int freq [3 + 2]; Set (freq, 0);

	for ( int i = 0; i < n; i++ ) {
		scanf ("%d", &a [i]);
		freq [a [i]]++;
	}

	int groupFreq [3 + 2] [3 + 2]; Set (groupFreq, 0);
	int len = 0;

	for ( int i = 1; i <= 3; i++ ) {
		for ( int j = 0; j < freq [i]; j++ ) {
			groupFreq [i] [a [len]]++;
			len++;
		}
	}

	int cnt = 0;
	int mini;

	// reduce '2' from group 1
	mini = min (groupFreq [1] [2], groupFreq [2] [1]);
	groupFreq [1] [2] -= mini;
	groupFreq [2] [1] -= mini;
	groupFreq [1] [1] += mini;
	groupFreq [2] [2] += mini;
	cnt += mini;

	// reduce '3' from group 1
	mini = min (groupFreq [1] [3], groupFreq [3] [1]);
	groupFreq [1] [3] -= mini;
	groupFreq [3] [1] -= mini;
	groupFreq [1] [1] += mini;
	groupFreq [3] [3] += mini;
	cnt += mini;

	mini = freq [1] - groupFreq [1] [1];
	cnt += mini;
	groupFreq [1] [1] = freq [1];
	groupFreq [2] [1] = groupFreq [3] [1] = 0;
	groupFreq [3] [2] += groupFreq [1] [2];
	groupFreq [2] [3] += groupFreq [1] [3];
	groupFreq [1] [2] = groupFreq [1] [3] = 0;
	cnt += groupFreq [2] [3];

	printf ("%d\n", cnt);


	return 0;
}

// @END_OF_SOURCE_CODE

Judge Response

USER: Shadow King [tausiq11]
TASK: sort3
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3048 KB]
   Test 2: TEST OK [0.000 secs, 3048 KB]
   Test 3: TEST OK [0.000 secs, 3048 KB]
   Test 4: TEST OK [0.000 secs, 3048 KB]
   Test 5: TEST OK [0.000 secs, 3048 KB]
   Test 6: TEST OK [0.000 secs, 3048 KB]
   Test 7: TEST OK [0.000 secs, 3048 KB]
   Test 8: TEST OK [0.000 secs, 3048 KB]

All tests OK.
Your program ('sort3') produced all correct answers!  This is your
submission #4 for this problem.  Congratulations!
Advertisements

USACO : Ordered Fractions



/*
ID: tausiq11
PROG: frac1
LANG: C++
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 100000
#define LL long long

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Pr(x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++) cout << *it << " "; cout << endl;
#define Set(a, s) memset(a, s, sizeof (a))
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

using namespace std;

struct node {
	int numerator;
	int demonimator;
	int val;
};

node a [N];
int len;
int n;

int gcd (int p, int q)
{
	if ( q == 0 ) return p;
	return gcd (q, p % q);
}

bool cmp (node p, node q)
{
	if ( p.val < q.val ) return true;
	return false;
}

int main ()
{
	Rd ("frac1.in");
	Wt ("frac1.out");

	scanf ("%d", &n);

	a [0].numerator = 0;
	a [0].demonimator = 1;
	a [0].val = 0;

	a [1].numerator = 1;
	a [1].demonimator = 1;
	a [1].val = 100000000;

	len = 2;

	for ( int i = 1; i < n; i++ ) {
		for ( int j = i + 1; j <= n; j++ ) {
			if ( gcd (i, j) == 1 ) {
				a [len].numerator = i;
				a [len].demonimator = j;
				a [len].val = (int) (((double)i / (double)j) * 100000000.0);
				len++;
			}
		}
	}

	sort (a, a + len, cmp);

	for ( int i = 0; i < len; i++ ) {
		printf ("%d/%d\n", a [i].numerator, a [i].demonimator);
	}

	return 0;
}

// @END_OF_SOURCE_CODE

Judge Response

USER: [tausiq11]
TASK: frac1
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 4224 KB]
   Test 2: TEST OK [0.000 secs, 4224 KB]
   Test 3: TEST OK [0.000 secs, 4224 KB]
   Test 4: TEST OK [0.000 secs, 4224 KB]
   Test 5: TEST OK [0.000 secs, 4224 KB]
   Test 6: TEST OK [0.000 secs, 4224 KB]
   Test 7: TEST OK [0.000 secs, 4224 KB]
   Test 8: TEST OK [0.000 secs, 4224 KB]
   Test 9: TEST OK [0.000 secs, 4224 KB]
   Test 10: TEST OK [0.000 secs, 4224 KB]
   Test 11: TEST OK [0.011 secs, 4224 KB]

All tests OK.
YOUR PROGRAM ('frac1') WORKED FIRST TIME!  That's fantastic
-- and a rare thing.  Please accept these special automated
congratulations.

USACO : The Castle



/*
ID: tausiq11
PROG: castle
LANG: C++
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 50
#define LL long long

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Pr(x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++) cout << *it << " "; cout << endl;
#define Set(a, s) memset(a, s, sizeof (a))
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

using namespace std;

enum direction { West = 1, North = 2, East = 4, South = 8 };

int width, height;

int maze [N + 2] [N + 2];
vector <int> matrix [N * N + 5];
bool vis [N * N + 5];
int numberOfComponent;
int component [N * N + 5];
int componentFrequency [N * N + 5];
int dr [] = {-1, 0, 1, 0};
int dc [] = {0, 1, 0, -1};
int maxSizedRoom;
int resW, resH;
char resDir;

void reset ()
{
	int cnt = 1;

	for ( int i = 0; i < height; i++ ) {
		for ( int j = 0; j < width; j++ ) maze [i] [j] = cnt++;
	}

	Set (vis, false);
	numberOfComponent = 0;
	Set (componentFrequency, 0);
	maxSizedRoom = -1;
}

void checkByRemove (int p, int q)
{
	int freq = -1;

	// printf ("%d\n", maze [p] [q]);

	if ( p != 0 && component [maze [p] [q]] != component [maze [p - 1] [q]] ) {
		freq = componentFrequency [component [maze [p] [q]]] + componentFrequency [component [maze [p - 1] [q]]];
		if ( freq > maxSizedRoom ) {
			maxSizedRoom = freq;
			resW = q; resH = p; resDir = 'N';
		}
	}
	if ( q != width - 1 && component [maze [p] [q]] != component [maze [p] [q + 1]] ) {
		freq = componentFrequency [component [maze [p] [q]]] + componentFrequency [component [maze [p] [q + 1]]];
		if ( freq > maxSizedRoom ) {
			maxSizedRoom = freq;
			resW = q; resH = p; resDir = 'E';
		}
	}
}

void dfs (int node, int c)
{
	if ( vis [node] ) return;
	vis [node] = true;
	component [node] = c;

	for ( size_t i = 0; i < matrix [node].size (); i++ ) {
		dfs (matrix [node] [i], c);
	}
}

void print ()
{
	for ( int i = 1; i <= 28; i++ ) {
		printf ("%d -> ", i);
		for ( size_t j = 0; j < matrix [i].size(); j++ ) {
			printf ("%d ", matrix [i] [j]);
		}
		printf ("\n");
	}
}

void print2 ()
{
	for ( int i = 1; i <= 28; i++ ) {
		printf ("%d -> %d\n", i, component [i]);
	}
}

int main ()
{
	freopen("castle.in", "r", stdin);
	freopen("castle.out", "w", stdout);

	scanf ("%d %d", &width, &height);
	int inp;

	reset ();

	bool dir [4];

	for ( int i = 0; i < height; i++ ) {
		for ( int j = 0; j < width; j++ ) {
			scanf ("%d", &inp);
			dir [0] = dir [1] = dir [2] = dir [3] = true;
			for ( int k = 8; k >= 1; k /= 2 ) {
				if ( inp >= k ) {
					switch (k) {
					case 8: dir [0] = false; break;
					case 4: dir [1] = false; break;
					case 2: dir [2] = false; break;
					case 1: dir [3] = false; break;
					}
					inp -= k;
				}
			}

			if ( dir [0] ) matrix [maze [i] [j]].push_back(maze [i + 1] [j]);
			if ( dir [1] ) matrix [maze [i] [j]].push_back(maze [i] [j + 1]);
			if ( dir [2] ) matrix [maze [i] [j]].push_back(maze [i - 1] [j]);
			if ( dir [3] ) matrix [maze [i] [j]].push_back(maze [i] [j - 1]);
		}
	}

	// print ();

	for ( int i = 0; i < height; i++ ) {
		for ( int j = 0; j < width; j++ ) {
			if ( !vis [maze [i] [j]] ) {
				dfs (maze [i] [j], ++numberOfComponent);
			}
		}
	}

	// print2 ();


	printf ("%d\n", numberOfComponent); // number of room

	for ( int i = 0; i < N * N + 2; i++ ) {
		componentFrequency [component [i]]++;
	}

	int largestComponent = -1;

	for ( int i = 1; i <= numberOfComponent; i++ ) {
		largestComponent = max (largestComponent, componentFrequency [i]);
	}

	printf ("%d\n", largestComponent);	// largest room

	for ( int j = 0; j < width; j++ ) {
		for ( int i = height - 1; i >= 0; i-- ) {
			checkByRemove (i, j);
		}
	}

	printf ("%d\n%d %d %c\n", maxSizedRoom, resH + 1, resW + 1, resDir);

	return 0;
}

// @END_OF_SOURCE_CODE

Judge Response

USER: [tausiq11]
TASK: castle
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3244 KB]
   Test 2: TEST OK [0.000 secs, 3112 KB]
   Test 3: TEST OK [0.000 secs, 3244 KB]
   Test 4: TEST OK [0.000 secs, 3244 KB]
   Test 5: TEST OK [0.000 secs, 3244 KB]
   Test 6: TEST OK [0.000 secs, 3244 KB]
   Test 7: TEST OK [0.000 secs, 3112 KB]
   Test 8: TEST OK [0.000 secs, 3244 KB]

All tests OK.
YOUR PROGRAM ('castle') WORKED FIRST TIME!  That's fantastic
-- and a rare thing.  Please accept these special automated
congratulations.

USACO : Checker Challenge



/*
ID: tausiq11
PROG: checker
LANG: C++
*/

/* 
 * File:   main.cpp
 * Author: shahab
 *
 * Created on March 5, 2011, 1:34 AM
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for ( int i = (a); i < (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))

using namespace std;

int n;
bool col_avail [13 + 3];
bool right_diag [30];
bool left_diag [30];
int col_pos [13 + 3];
int print;
int cnt;

void printArray ()
{
    printf ("%d", col_pos [0] + 1);

    for ( int i = 1; i < n; i++ ) printf (" %d", col_pos [i] + 1);
    printf ("\n");

    print++;
}

void bktk (int at_row)
{
    if ( at_row == n ) {
        if ( print < 3 ) printArray ();
        cnt++; return;
    }

    for ( int i = 0; i < n; i++ ) {
        if ( col_avail [i] && right_diag [i - at_row + 13] && left_diag [i + at_row]) {
            col_avail [i] = right_diag [i - at_row + 13] = left_diag [i + at_row] = false;
            col_pos [at_row] = i;
            bktk (at_row + 1);
            col_avail [i] = right_diag [i - at_row + 13] = left_diag [i + at_row] = true;
        }
    }
}

int main(int argc, char** argv)
{
    freopen("checker.in", "r", stdin);
    freopen("checker.out", "w", stdout);

    scanf ("%d", &n);
    print = cnt = 0;

    Set (col_avail, true);
    Set (right_diag, true);
    Set (left_diag, true);

    bktk (0);

    printf ("%d\n", cnt);


    return 0;
}

// @END_OF_SOURCE_CODE

USACO: SuperPrime Rib


1. There are only 83 super primes up to 8 digits

2. 1st digit of any super primes must be 2, 3, 5 or 7

3. rest of the digits must be odd numbers 1, 3, 5, 7, 9

4. all 1 digit super primes are: 2, 3, 5, 7
to get all super primes of digits 2, i appended all odd numbers after 1 digit super primes
Here’s the list:
21
23
25
27
29
31
33
35
37
39
51
53
55
57
59
71
73
75
77
79

among these numbers, we will pick only prime numbers
23
29
31
37
53
59
71
73
79

5. to get 3 digits super primes, we append odd numbers after 2 digits super prime
231
233
235
237
239
291
293
295
297
299
311
313
315
317
319
371
373
375
377
379
531
533
535
537
539
591
593
595
597
599
711
713
715
717
719
731
733
735
737
739
791
793
795
797
799
now pick only the prime numbers to get 3 digit super primes

/*
ID: tausiq11
PROG: sprime
LANG: C++
*/

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

vector <int> primeRib;
int startIndex;
int endIndex;

bool isPrime (int p)
{
	if ( p % 2 == 0 || p < 1 ) return false;

	int len = sqrt (p * 1.0);

	for ( int i = 3; i <= len; i += 2 ) if ( p % i == 0 ) return false;
	return true;
}

void oneDigit ()
{
	primeRib.push_back (2);
	primeRib.push_back (3);
	primeRib.push_back (5);
	primeRib.push_back (7);

	startIndex = 0;
	endIndex = primeRib.size ();
}

void twoDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();

}

void threeDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();
}

void fourDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();
}

void fiveDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();
}

void sixDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();
}

void sevenDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();
}

void eightDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();
}

void generatePrimeRib ()
{
	oneDigit ();
	twoDigit ();
	threeDigit ();
	fourDigit ();
	fiveDigit ();
	sixDigit ();
	sevenDigit ();
	eightDigit ();
}

int power (int b, int p)
{
	int ret = 1;

	for ( int i = 1; i <= p; i++ ) 
		ret *= b;

	return ret;
}

int main ()
{
	generatePrimeRib ();

	freopen ("sprime.in", "r", stdin);
	freopen ("sprime.out", "w", stdout);
	//printf ("%d\n", primeRib.size ());

	int digit;
	scanf ("%d", &digit);
	
	for ( size_t i = 0; i < primeRib.size (); i++ ) {
		if ( primeRib [i] >= power (10, digit - 1) && primeRib [i] <= power (10, digit) ) { printf ("%d\n", primeRib [i]); }
	}
	
	return 0;
}

// @END_OF_SOURCE_CODE

USACO : Prime Palindromes


its silly to write such a huge code
my approach was pretty simple
i’ve got the idea from given hints
my code generates all the palindrome numbers from digit 1 to 8
better to say odd_palindrome numbers
because, if the last digit is even then it’s not prime, except 2
/*
ID: tausiq11
PROG: pprime
LANG: C++
*/

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

vector <int> oddPalindromeList;

void oneDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) oddPalindromeList.push_back (i);
}

void twoDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) oddPalindromeList.push_back (i * 10 + i);
}

void threeDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) {
		for ( int j = 0; j <= 9; j++ ) 
			oddPalindromeList.push_back (100 * i + 10 * j + i);
	}
}

void fourDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) {
		for ( int j = 0; j <= 9; j++ ) 
			oddPalindromeList.push_back (1000 * i + 100 * j + 10 * j + i);
	}
}

void fiveDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) {
		for ( int j = 0; j <= 9; j++ ) {
			for ( int k = 0; k <= 9; k++ )
				oddPalindromeList.push_back (10000 * i + 1000 * j + 100 * k + 10 * j + i);
		}
	}
}

void sixDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) {
		for ( int j = 0; j <= 9; j++ ) {
			for ( int k = 0; k <= 9; k++ )
				oddPalindromeList.push_back (100000 * i + 10000 * j + 1000 * k + 100 * k + 10 * j + i);
		}
	}
}

void sevenDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) {
		for ( int j = 0; j <= 9; j++ ) {
			for ( int k = 0; k <= 9; k++ ) {
				for ( int l = 0; l <= 9; l++ ) 
					oddPalindromeList.push_back (1000000 * i + 100000 * j + 10000 * k + 1000 * l + 100 * k + 10 * j + i);
			}
		}
	}
}

void eightDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) {
		for ( int j = 0; j <= 9; j++ ) {
			for ( int k = 0; k <= 9; k++ ) {
				for ( int l = 0; l <= 9; l++ ) 
					oddPalindromeList.push_back (10000000 * i + 1000000 * j + 100000 * k + 10000 * l + 1000 * l + 100 * k + 10 * j + i);
			}
		}
	}
}

void generatePalinDrome ()
{
	oneDigit ();
	twoDigit ();
	threeDigit ();
	fourDigit ();
	fiveDigit ();
	sixDigit ();
	sevenDigit ();
	eightDigit ();
}

bool isPrime (int p)
{
	if ( p % 2 == 0 || p < 1 ) return false;

	int len = sqrt (p * 1.0);

	for ( int i = 3; i <= len; i += 2 ) if ( p % i == 0 ) return false;
	return true;
}

int main ()
{
	generatePalinDrome ();

	freopen ("pprime.in", "r", stdin);
	freopen ("pprime.out", "w", stdout);

	int a, b;
	scanf ("%d %d", &a, &b);

	for ( size_t i = 0; i < oddPalindromeList.size (); i++ ) {
		if ( oddPalindromeList [i] >= a && oddPalindromeList [i] <= b ) {
			if ( isPrime (oddPalindromeList [i]) ) printf ("%d\n", oddPalindromeList [i]);
		}
	}

	return 0;
}

// @END_OF_SOURCE_CODE

USACO : Number Triangles


/*
ID: tausiq11
PROG: numtri
LANG: C++
*/

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

int input [1000 + 3] [1000 + 3];

int main ()
{
    freopen ("numtri.in", "r", stdin);
    freopen ("numtri.out", "w", stdout);

    int r;
    scanf ("%d", &r);

    for ( int i = 0; i < r; i++ )
        for ( int j = 0; j <= i; j++ ) scanf ("%d", &input [i] [j]);

    for ( int i = r - 1; i >= 1; i-- )
        for ( int j = 0; j < i; j++ )
            input [i - 1] [j] += max (input [i] [j], input [i] [j + 1]);

    printf ("%d\n", input [0] [0]);

	return 0;
}

// @END_OF_SOURCE_CODE