ECOO '13 R2 P4 - Breaking Rocks

View as PDF

Submit solution


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

Problem type

Farmer Jane needs to be able to measure out corn to feed her cows, but all she has to help her is a primitive balance scale and a ~6~ kilogram rock. With this rock she could use the balance scale to measure out ~6~ kg of corn, but she often needs to measure out smaller quantities. She figures out that if she breaks the rock into three pieces, where two of them are ~1~ kg and the third is ~4~ kg, then she can measure out all integer quantities of corn from ~1~ to ~6~, as shown below.

Farmer Jane is happy now, but the situation gets her thinking. She knows she could have broken the rock into ~1~, ~2~, and ~3~ kg pieces and this would also have worked. But things are not so simple for other numbers. For example, there are ~15~ ways to break a ~12~ kg rock into ~4~ integer pieces but only ~9~ of them let you measure all integer weights from ~1~ to ~12~. She wonders if there could be some kind of algorithm to determine how many combinations work for a given size of rock and a given number of pieces…

The input contains ~10~ test cases.

Each test case consists of two integers (~P~ and ~R~) on a single line separated by a space. The integer ~P~ gives the number of pieces to break the rock into and the integer ~R~ gives the original size of the rock. For all test cases, ~1 \le R \le 100~.

For the first ~5~ test cases ~3 \le P \le 5~ and for the next ~5~ test cases ~6 \le P \le 10~.

Your job is to output a single line for each test case indicating the number of ways you can break up the rock into ~P~ integer-sized pieces so that all possible integer weights from ~1~ to ~R~ can be measured on a balance scale.

Sample Input

3 6
4 12
4 30
5 40
5 5
6 25
7 55
8 65
9 75
10 85

Sample Output

2
9
5
137
1
154
5749
28051
121108
474402

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.