//Dennis Matveyev for SER 2013 //The Days of Christmas /* Idea: Notice the pattern 1, 4, 10 ... dealing with sums ... looks familiar. Pascal's Triangle or N choose K notation Solution: populate array with values = 1 2 3 4 5 6 7 8 9 10 do the summation of current + previous values: 1 3 6 10 15 21 28 36 45 55 repeat: 1 4 10 20 35 56 84 120 165 220 Output appropriate step. */ #include #include using namespace std; int main() { int n; vector v(1000001); v[1] = 1; for (int i = 2; i <= 1000000; i++) v[i] = i; for (int i = 2; i <= 1000000; i++) v[i] += v[i - 1]; for (int i = 2; i <= 1000000; i++) v[i] += v[i - 1]; while (cin >> n && n > 0) cout << v[n] << endl; return 0; }