Many thanks to Clive Fraser aka CSFPython for this new "offering"!
William is the chief landscape designer for a substantial garden, employing a large team of gardeners.
Today he is considering the borders of flowering plants that separate the paths from the lawns.
These typically consist of a row of plants, often with several different varieties.
The border that William is currently contemplating has just two different plant varieties.
One of these has red flowers and the other has blue flowers. We will refer to these as R and B.
In this particular border the plants alternate so that the overall arrangement is (R B R B R B R B R...).
William remembers that another part of the garden has a very different arrangement where a group of blue
flowers has a group of red flowers both before and after it (R R R B B B B B B B R R R). Both of these
borders are highly symmetric and have clearly been designed that way. The same arrangements would be unlikely to
occur naturally.
William has access to a useful software package which provides a realistic picture of any planned arrangement
of plants so that the appearance of the arrangement within the garden can be assessed without the need to grow
the plants first. William is interested to see the results of introducing some element of randomness into the
design. He decides to begin with a border made up of red and blue flowers. Given the total number of plants in
the border, he wants to have some means of distinguishing between different arrangements. As the number of
different arrangements is likely to be very large, he decides to put the arrangements into different groups
where all arrangements within the same group have the same score. The score is intended to be one of a fairly
small number of values (roughly 100) which can be used as a convenient way of describing the arrangements in
the group. The magnitude of the score is not intended to be a measure of the aesthetic quality of the
arrangement. William decides that the score should be derived from two factors. The first will be based on the
way in which the number (N) of flowers in the border is split between red and blue. The second will be based
on the degree to which flowers of one colour are clustered (rather than spread out). A greater degree of
clustering should result in a larger score.
William spent some time deciding how to assign a score to a particular border arrangement. Given that the scores
are to be used for comparing arrangements containing the same total number of flowers (N), William decided
that the first contribution to the score could be easily dealt with by simply using the number of red flowers
in the arrangement. The clustering contribution to the score was more complicated. An arrangement consisting
of a single plant should have a score of 0 for the clustering contribution. An arrangement of 2 or more plants
should have a clustering score which is derived as follows. If the border contains an even number (2n) of
plants we take the first n plants as the first group and the second n plants as the second group.
If the border contains an odd number (2n+1) of plants we take the first n+1 plants as the first group and
the remaining n plants as the second group. We now have two separate groups of plants and apply the scoring
algorithm to both groups separately (using both contributions to the score in each case). We then take the
larger of these two scores and this becomes the clustering component of the score for the original arrangement.
Some examples should help to clarify the process.
An arrangement consisting of a single blue plant (B) contains no red plants so the first contribution to the
score is 0. It contains fewer than 2 plants so there is no clustering contribution to the score.
The overall score for (B) is 0.
An arrangement consisting of a single red plant (R) contains one red plant so the first contribution to the
score is 1. It contains fewer than 2 plants so there is no clustering contribution to the score.
The overall score for (R) is 1.
Next consider the group of two plants (B R). This group contains 1 red plant so its initial score is 1.
We then split the group into the two components (B) and (R). These have scores of 0 and 1 respectively.
The larger of these (and hence the cluster score) is 1, giving a total score of 2 for the arrangement (B R);
and clearly also for (R B).
Consider the group of 2 plants (R R). The initial score for 2 red plants is 2. The arrangement splits
into two halves each with a score of 1, so the clustering score is 1, giving a total score of 3 to (R R).
It is easy to see that any arrangement consisting entirely of blue plants must have a total score of 0,
since scores can only be added to by the presence of red plants.
Next consider the arrangement (R R B R). This contains 3 red plants so has an initial score of 3.
It splits into the groups (R R) and (B R). These have scores 3 and 2 respectively. The larger score
(cluster score) is 3 giving a total of 6 for (R R B R).
Finally consider the arrangement (R R B R B B B) with 3 red plants and an initial score of 3. The two
sub-arrangements are (R R B R) and (B B B) with scores of 6 and 0 respectively. This gives a cluster
score of 6 and a total score of 9 for the arrangement (R R B R B B B).
Now that William has a way of collecting potential arrangements together into groups with a common score he
wants to investigate the appearance of arrangements in different groups to assess the way in which the score
can be used to choose possible arrangements to plant in the garden. In particular he is interested in
determining how many different arrangements are associated with a particular score. Scores with a large number
of arrangements are more likely to represent natural randomness rather than a contrived design. We have just
looked at an arrangement of 7 plants where 3 of the plants are red. This arrangement is one of 5 ways in
which these plants can be arranged to give a score of 9. The 5 arrangements are:
(B B B B R R R)
(B R R R B B B)
(R B R R B B B)
(R R B R B B B)
(R R R B B B B)
This group of 7 plants can be arranged in 35 different ways. The 5 arrangements shown above (with a score
of 9) exhibit considerable clustering. The other arrangements have a smaller degree of clustering. There are
two different groups. You might like to verify that there are 10 arrangements with a score of 8 and 20
arrangements with a score of 7.
The problems which you are asked to solve specify the score for the arrangement (S), the total number of
plants in the arrangement (N) and the number of these plants which are red (R). You need to find the number
of different arrangements which meet this specification. All arrangements consist of a combination of red
plants and blue plants only. The total number of plants in the arrangement will always be less than 70. The
number of red plants in the arrangement will always be less than 36.
Input and Answer
The first line of the problem will be a single integer T denoting the number of test cases. Each of the
following T lines will hold 3 separate integer values. These are the target score S, the total number of
plants N and the number of red plants R. For each test case you must find the corresponding number of
arrangements. Give these answers, separated by spaces, as a single string.
Example:
input:
4
9 7 3
9 10 4
19 14 6
6 18 1
answer:
5 45 6 4