This page is still under construction.

Parts of this page are still being built. What you see may change.

Old Fishing Hole

Time limit1sMemory limit128 MB

Summary
Given three point values and a cap, enumerate every catch with at least one fish whose total points stay within the limit, in a specified order.
Level

Easy2 of 10

Topics
Brute force, Simulation, Implementation
Solved
No attempts yet

Problem

Fishing habitats and fish species are resources that must be carefully managed so they remain for the future. To that end, catch limits are set for a particular river based on each species' population. Each fish is worth a certain number of points, and the total points of the fish you catch must not exceed the points allowed for that river.

For example, suppose each brown trout is worth 2 points, each northern pike is worth 5 points, and each yellow pickerel is worth 2 points, and the total points allowed is at most 12. One acceptable catch is 3 brown trout and 1 northern pike (3×2+1×5=113 \times 2 + 1 \times 5 = 11 points), but many other combinations are allowed as well.

Write a program that, given the points allowed for a river, determines how many different catches an angler who catches at least one fish can make without exceeding the limit, and lists each of them.

Input

Four integers are given, one per line, in this order: the points for a brown trout, the points for a northern pike, the points for a yellow pickerel, and the total points allowed for the river.

Each integer is greater than 0 and at most 100.

Output

List every distinct catch that includes at least one fish and whose total points do not exceed the allowed limit. Print one catch per line in the form:

<a> Brown Trout, <b> Northern Pike, <c> Yellow Pickerel

where <a>, <b>, and <c> are the numbers of brown trout, northern pike, and yellow pickerel in that catch.

Order the catches by the number of yellow pickerel in ascending order; break ties by the number of northern pike in ascending order; then by the number of brown trout in ascending order.

After all catches, print a final line:

Number of ways to catch fish: <n>

where <n> is the total number of distinct valid catches. If no catch is possible, print only this final line with <n> equal to 0.

Examples2

  1. Example 1

    Input
    1
2
3
2
    Expected output
    1 Brown Trout, 0 Northern Pike, 0 Yellow Pickerel
2 Brown Trout, 0 Northern Pike, 0 Yellow Pickerel
0 Brown Trout, 1 Northern Pike, 0 Yellow Pickerel
Number of ways to catch fish: 3

  2. Example 2

    Input
    2
5
2
12
    Expected output
    1 Brown Trout, 0 Northern Pike, 0 Yellow Pickerel
2 Brown Trout, 0 Northern Pike, 0 Yellow Pickerel
3 Brown Trout, 0 Northern Pike, 0 Yellow Pickerel
4 Brown Trout, 0 Northern Pike, 0 Yellow Pickerel
5 Brown Trout, 0 Northern Pike, 0 Yellow Pickerel
6 Brown Trout, 0 Northern Pike, 0 Yellow Pickerel
0 Brown Trout, 1 Northern Pike, 0 Yellow Pickerel
1 Brown Trout, 1 Northern Pike, 0 Yellow Pickerel
2 Brown Trout, 1 Northern Pike, 0 Yellow Pickerel
3 Brown Trout, 1 Northern Pike, 0 Yellow Pickerel
0 Brown Trout, 2 Northern Pike, 0 Yellow Pickerel
1 Brown Trout, 2 Northern Pike, 0 Yellow Pickerel
0 Brown Trout, 0 Northern Pike, 1 Yellow Pickerel
1 Brown Trout, 0 Northern Pike, 1 Yellow Pickerel
2 Brown Trout, 0 Northern Pike, 1 Yellow Pickerel
3 Brown Trout, 0 Northern Pike, 1 Yellow Pickerel
4 Brown Trout, 0 Northern Pike, 1 Yellow Pickerel
5 Brown Trout, 0 Northern Pike, 1 Yellow Pickerel
0 Brown Trout, 1 Northern Pike, 1 Yellow Pickerel
1 Brown Trout, 1 Northern Pike, 1 Yellow Pickerel
2 Brown Trout, 1 Northern Pike, 1 Yellow Pickerel
0 Brown Trout, 2 Northern Pike, 1 Yellow Pickerel
0 Brown Trout, 0 Northern Pike, 2 Yellow Pickerel
1 Brown Trout, 0 Northern Pike, 2 Yellow Pickerel
2 Brown Trout, 0 Northern Pike, 2 Yellow Pickerel
3 Brown Trout, 0 Northern Pike, 2 Yellow Pickerel
4 Brown Trout, 0 Northern Pike, 2 Yellow Pickerel
0 Brown Trout, 1 Northern Pike, 2 Yellow Pickerel
1 Brown Trout, 1 Northern Pike, 2 Yellow Pickerel
0 Brown Trout, 0 Northern Pike, 3 Yellow Pickerel
1 Brown Trout, 0 Northern Pike, 3 Yellow Pickerel
2 Brown Trout, 0 Northern Pike, 3 Yellow Pickerel
3 Brown Trout, 0 Northern Pike, 3 Yellow Pickerel
0 Brown Trout, 1 Northern Pike, 3 Yellow Pickerel
0 Brown Trout, 0 Northern Pike, 4 Yellow Pickerel
1 Brown Trout, 0 Northern Pike, 4 Yellow Pickerel
2 Brown Trout, 0 Northern Pike, 4 Yellow Pickerel
0 Brown Trout, 0 Northern Pike, 5 Yellow Pickerel
1 Brown Trout, 0 Northern Pike, 5 Yellow Pickerel
0 Brown Trout, 0 Northern Pike, 6 Yellow Pickerel
Number of ways to catch fish: 40