The Addition Pyramid
National Olympiad — National round (2016 season)
Submission name: puzzle.cpp
Problem summary
The first row contains N consecutive numbers starting with K. Each next row consists of the sums of adjacent pairs in the preceding row, until one number remains. Find that final number.
Input
N K.
Output
The last remaining number.
Constraints
2 ≤ N ≤ 50; 0 ≤ K ≤ 200.
Worked example
An independently prepared example for this explanation.
Input
3 1
Output
8
Solution analysis
- Store the first row K, K + 1, …, K + N − 1 in a vector. Each new row has one fewer element.
- For a current row of length length, replace a[i] by a[i] + a[i + 1] for i from left to right, stopping before length − 1. This is safe in place because the right neighbor has not yet been overwritten.
- With N = 3 and K = 1 the rows are [1, 2, 3], then [3, 5], then [8]. A 64-bit integer is necessary: repeated additions can create much larger values than the inputs.
Why it works
Initially the vector contains the correct first row. During a left-to-right update, both a[i] and a[i + 1] still hold the old values needed for that adjacent sum. Thus the updated prefix is the correct next row. Induction through all row lengths yields the correct final value.
Watch out. Update from left to right; right-to-left overwrites a neighbor that is still needed. Use long long.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> row(n);
for (int i = 0; i < n; ++i) {
row[i] = k + i;
}
for (int length = n; length > 1; --length) {
for (int i = 0; i + 1 < length; ++i) {
// Left-to-right keeps the old right neighbor available.
row[i] += row[i + 1];
}
}
cout << row[0] << '\n';
return 0;
}