Problem H
Restaurant Ratings
The restaurants in each city are ranked as follows. First, sum up the ratings given by all the critics for a restaurant. A restaurant with a higher total sum is always better than one with a lower total sum. For restaurants with the same total sum, we rank them based on the ratings given by critic 1. If there is a tie, then we break ties by the ratings by critic 2, etc.
A restaurant owner received the ratings for his restaurant, and is curious about how it ranks in the city. He does not know the ratings of all the other restaurants in the city, so he would estimate this by computing the maximum number of different ratings that is no better than the one received by the restaurant. You are asked to write a program to answer his question.
Input
The input consists of a number of cases, at most $500$. Each case is specified on one line. On each line, the first integer is $n$, followed by $n$ integers containing the ratings given by the $n$ critics (in order). You may assume that the total sum of ratings for each restaurant is at most 30. The input is terminated by a line containing $n = 0$.
Output
For each input, print the number of different ratings that is no better than the given rating. You may assume that the output fits in a 64-bit signed integer.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 3 2 4 3 5 4 3 2 1 4 0 |
4 33 10810 |
