Problemele 4-6 pentru pregatirea LOT-ului
4.Cow Yahtzee
In their usual clumsy way, the cows are play a version of Yahtzee,
the dice-rolling game. They roll N (1 <= N <= 20) dice, each having
S (1 <= S <= 8) sides. They are curious as to the number of ways
a dice roll can meet a particular criterion (like "contains three
2's" or "contains one 2 and two 3's").
Help them learn about probability. Write a program that reads not
only N and S but also some expressions that describe their criteria.
Count the number ways the expression can be satisfied over the
entire set of all possible dice rolls (the entire set of rolls for
three two-sided dice is: {1,1,1; 1,1,2; 1,2,1; 1,2,2; 2,1,1; 2,1,2;
2,2,1; 2,2,2};
Expressions comprise combinations of a basic form that expresses
the thought "want at least W copies of result R". It looks like this:
WxR
where (0 <= W <= N and 1 <= R <= S). Each test run will supply E
expressions (1 <= E <= 20), each of which contains a number 1..10
of the basic forms separated by a '+', which means 'and' (see below).
The set of lines expresses the thought that is the 'inclusive or'
of each of the lines individually. Thus the pair of expressions
shown below means "at least three rolls of five OR both at least
one roll of 3 and also at least two rolls of 4":
3×5
1×3+2×4
Here are some of the combinations of four five-sided dice that
satisfy the above expression: 5,5,5,1; 4,5,5,5; 3,4,4,2; 3,4,4,3;
3,4,4,5; 4,4,5,3.
Programming note: Be sure to verify that you can read in two integers
from one line and a string from the next line. In some languages'
I/O schema, this is harder than it looks!
Also note that the total number of dice combinations will never
exceed 1,512,768 in the supplied test data.
PROBLEM NAME: cowyotz
INPUT FORMAT:
- Line 1: Three space-separated integers: N, S, and E
- Lines 2..E+1: Line i+1 describes expression i as above.
SAMPLE INPUT (file cowyotz.in):
4 5 2
3×5
1×3+2×4
INPUT DETAILS:
This is the encoding of the expression used as an example in the task text.
OUTPUT FORMAT:
- Line 1: A single integer that is the number of ways the
expression(s) can be satisfied by rolling the dice in all
combinations.
SAMPLE OUTPUT (file cowyotz.out):
63
OUTPUT DETAILS:
63 rolls satisfy the expression.
5.Making Change
Poor Bessie has taken a job in the convenience store located just
over the border in Slobbovia. Slobbovians use different coinages
than the USA; their coin values change day-by-day!
Help Bessie make optimal change for Slobbovian shoppers. You will
need to create C (1 <= C <= 1000) cents of change using N (1 <= N
<= 10) coins of various values. All test cases will be solvable
using the supplied coins.
If 5 coins of values 50, 25, 10, 5, and 1 were available, Bessie
would make optimum change (minimal coins) of 93 cents by using 1 x
50, 1 × 25, 1 × 10, 1 × 5, and 3 × 1 coins (a total of 7 coins).
How hard could it be? The final two test cases will be challenging.
PROBLEM NAME: change
INPUT FORMAT:
- Line 1: Two space-separate integers: C and N
- Lines 2..N+1: Each line contains a single unique integer that is a
coin value that can be used to create change
SAMPLE INPUT (file change.in):
93 5
25
50
10
1
5
OUTPUT FORMAT:
- Line 1: A single integer that is the minimum number of coins to
create C cents
SAMPLE OUTPUT (file change.out):
7
6.The Bale Tower
Always bored with cud-chewing, the cows have invented a new game.
One cow retrieves a set of N (3 <= N <= 20) hay bales from the shed
each of which is one unit high. Each bale also has some unique width
and unique breadth.
A second cow tries to choose a set of bales to make the tallest
stack of bales in which each bale can be placed only on a bale whose
own width and breadth are smaller than the width and breadth of the
bale below. Bales can not be rotated to interchange the width and
breadth.
Help the cows determine the highest achievable tower that can be
legally built form a set of bales.
PROBLEM NAME: btwr
INPUT FORMAT:
- Line 1: A single integer, N
- Lines 2..N+1: Each line describes a bale with two space-separated
integers,respectively the width and breadth
SAMPLE INPUT (file btwr.in):
6
6 9
10 12
9 11
8 10
7 8
5 3
INPUT DETAILS:
Six bales of various widths and breadths
OUTPUT FORMAT:
- Line 1: The height of the tallest possible tower that can legally be
built from the bales.
SAMPLE OUTPUT (file btwr.out):
5
OUTPUT DETAILS:
These bales can be stacked for a total height of 5:
10 12
9 11
8 10
6 9
5 3
[another stacking exists, too]
