#P8644. Robot Cheerleader Tower
Robot Cheerleader Tower
Robot Cheerleader Tower
On planet X, the robot cheerleaders have two costumes, (A) and (B). They construct a tower in the shape of a pyramid. For example, one such tower is illustrated below:
[ \begin{array}{cccccc} & & & & A & \ & & & B & & B \ & & A & & B & & A \ & A & & A & & B & & B \ B & & B & & B & A & & B \ A & & A & & B & & B & & A \end{array} ]
The rules for constructing the tower are as follows:
- A robot wearing costume (A) can only stand on the shoulders of two robots that are both wearing (A) or both wearing (B).
- A robot wearing costume (B) can only stand on the shoulders of one robot in costume (A) and one in costume (B) (in either order).
More precisely, the tower is built as a pyramid. If the bottom row contains (n) robots then the row above has (n-1) robots, the next one has (n-2), and so on, until the top row has a single robot. A robot (other than those in the bottom row) stands on the shoulders of two adjacent robots in the row immediately below. Thus the costume of a robot in an upper row is determined by the costumes of the two robots immediately below it: if the two adjacent robots wear the same costume then the robot above must wear (A); if they wear different costumes then it must wear (B).
Given (A_{\text{total}}) and (B_{\text{total}}), the total numbers of robots available in costumes (A) and (B) respectively, note that a complete pyramid of (n) rows uses (\frac{n(n+1)}{2}) robots. Therefore we must have
[ \frac{n(n+1)}{2} = A_{\text{total}} + B_{\text{total}}. ]
Your task is to determine the number of distinct towers (that is, the number of valid configurations for the bottom row) such that when the tower is completely built following the above rules the total number of (A)’s and (B)’s in the entire tower equals (A_{\text{total}}) and (B_{\text{total}}) respectively. If there is no positive integer (n) satisfying (\frac{n(n+1)}{2} = A_{\text{total}} + B_{\text{total}}), then the answer is 0.
Note: In our formulation, we encode costume (A) as 0 and costume (B) as 1. The tower is constructed from the bottom row upward. In the construction, if two adjacent robots in the current row have the same costume their "shoulder" carries an (A) (0) in the next row; if they are different, it carries a (B) (1). The entire tower’s count of (B)’s is the sum (in the usual integer sense) over all rows.
inputFormat
Two integers (A_{\text{total}}) and (B_{\text{total}}), separated by space, where (A_{\text{total}} + B_{\text{total}} = \frac{n(n+1)}{2}) for some positive integer (n).
outputFormat
Output a single integer representing the number of valid towers.
sample
3 0
1
</p>