CEOI 2010 - A Huge Tower
Authors: Óscar Garries, Evan Zhao
Explanation
First, let's define some variables. Let be the block sizes, sorted from least to greatest. Let be the number of indicies such that and . Let be the answer if the tower consisted of only the blocks . Of course, this means that will be the final answer.
For any tower consisting of the first blocks, there will always be number of ways to insert the block of size into the tower. To understand why, consider where the block of size can be inserted. The block of size can always be inserted at the bottom of the tower, because there is no block larger than in the tower. The block with size can be inserted at the top of some block with size if and only if .
Thus, we see that , because there are valid ways to insert block into any of the valid towers.
C++
Implementation
This solution uses 2-pointers instead of creating the arrays and .
#include <bits/stdc++.h>using namespace std;const int MOD = 1e9 + 9;int main() {int n, d;cin >> n >> d;vector<int> ar(n);
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!