ACM 1225. Flags / Флаги

Let us keep an array of pairs A where A[i].first will show the number of flags that end with a red stripe and A[i].second will show the number of flags that end with a white stripe. We don't need to keep another one for the "blue" case because basically no flag ends with a stripe "blue". So, suppose we have calculated the asnwer up to A[N-1] so what will it be for A[N], if the flags of length N-1 ended with a red stripe then there will be that much flags of length N ending with a white stripe (we can add white to red) and also if N-2 th stripe was red then the N-1th one could have been blue and we could have add another white stripe to those ones. So the final answer will be A[N](white)=A[N-1](red)+a[N-2](red). and A[N](red)=A[N-1](white)+A[N-2](white). The total answer is the sum of those 2.

       FULL SOURCE CODE