ECOO '18 R3 P1 - Balanced

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 13.0s
Memory limit: 64M

Problem type

Ms. Daisy teaches a class of B boys and G girls that need to line up every morning to take attendance. Ms. Daisy thinks that a line is "balanced" if at least one of the boys is equidistant from two of the girls in the line. For example, a girl-boy-boy-girl line is not balanced because both boys are closer to one of the girls, but a girl-girl-boy-boy-girl line is balanced because the first boy is equidistant from the first and last girls.

Ms. Daisy likes it when the students form a balanced line. Can you help her figure out the number of balanced lines that the students can form? Two lines are considered distinct if at least one student has a different position in each line.

Input Specification

The standard input contains 10 datasets. Each dataset contains two integers B, G (1 \le B,G \le 10^6).

For the first four datasets, B+G \le 20.

Output Specification

For each data set, output the number of balanced lines that can be formed, modulo 1\,000\,000\,007.

Note: A modulo B is the remainder of A \div B.

Sample Input (Three Datasets Shown)

1 2
2 2
3 2

Sample Output

2
8
48

Explanation of Sample Output

In the first case, a balanced line must have a girl, then the boy, and then the other girl. Either girl can come first, which gives us two balanced lines. In the second case, a balanced line has either a boy-girl-boy-girl pattern or a girl-boy-girl-boy pattern. In the third case, an example balanced line would have a girl-boy-boy-boy-girl pattern (the boy in the middle is equidistant from the two girls).

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments

There are no comments at the moment.