Homer Simpson, a very smart guy, likes eating Krusty-burgers. It takes Homer m minutes to eat a Krusty- burger. However, there’s a new type of burger in Apu’s Kwik-e-Mart. Homer likes those too. It takes him n minutes to eat one of these burgers. Given t minutes, you have to find out the maximum number of burgers Homer can eat without wasting any time. If he must waste time, he can have beer.
Input
Input consists of several test cases. Each test case consists of three
integers m, n, t (0 < m,n,t < 10000).
Input is terminated by EOF.
Output
For each test case, print in a single line the maximum number of burgers
Homer can eat without having beer. If homer must have beer, then also print
the time he gets for drinking, separated by a single space. It is preferable
that Homer doesn’t drink beer.
Sample Input
3 5 54
3 5 55
Sample Output
18
17
A square pattern of light and dark cells is shown in its original state and a transformed state. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations:
90 Degree Rotation:
The pattern was rotated to the right 90 degrees.
180 Degree Rotation:
The pattern was rotated to the right 180 degrees.
270 Degree Rotation:
The pattern was rotated to the right 270 degrees.
Vertical Reflection:
The pattern was reflected through a horizontal mirror
positioned above the pattern.
Combination:
The pattern was subjected to a vertical reflection
followed by one of the rotations.
Preservation:
The original pattern was preserved (the new pattern
is identical to the original).
Improper:
The new pattern was not obtained via any of these
treansformations.
Input
The input file will consist of an unknown number of pattern datasets
on the standard input. Each pattern dataset will consist of an integer
on a line by itself, which gives the dimensions of the square containing
the pattern (the
size will range from 1 to 10). The following lines will contain each
line of the original and new (transformed) patterns in a side-by-side format,
separated by a space. Light squares will be indicated by a dot (period),
while dark squares will be represented with an X.
Output
The output from your program will be a sentence describing the relationship
that the new pattern bears to the original. Each sentence will begin with
a pattern ID number (starting with 1) and end stating the relatinship representing
the minimal amount of work necessary to derive the new pattern from the
original. For the purpose of evaluating the amount of work needed, rotations
are considered less work than reflections, and smaller rotations are less
work than larger ones. Of course, "preservation'' involves no work at all.
Note that only the above possibilities should be considered -- there is no such thing as a "360 degree rotation'' for this problem (such a transformation would "preserve'' the pattern), nor is there a "`horizontal reflection''. Also, remember that when a single rotation or reflection is not sufficient, your program should next consider rotated versions after a vertical reflection. Although a combination transformation might yield the same new pattern as one of the single transformations alone, the single transformation is the one you should output (the minimal transformation). Your output should be a complete sentence, ending with a period.
Look at the sample output below for the exact format.
Sample Input
5
X...X ....X
.X... ...X.
...X. .X...
..X.X ..X..
....X XX..X
6
....XX X....X
...X.. X.X...
XX..X. .X..X.
..X... ...X.X
...X.. ..X...
..X..X ..X...
2
X. X.
.X .X
4
..X. ...X
XX.. ....
.... XX..
...X ..X.
5
X.... .X...
.X... ..X..
.X... ..X..
...X. ....X
....X X....
4
.X.. ..X.
.X.X X...
.... ..XX
..X. ....
2
.. XX
XX ..
Sample Output
Pattern 1 was rotated 90 degrees.
Pattern 2 was rotated 270 degrees.
Pattern 3 was preserved.
Pattern 4 was reflected vertically.
Pattern 5 was improperly transformed.
Pattern 6 was reflected vertically and rotated 270 degrees.
Pattern 7 was rotated 180 degrees.
You are to write a program that has to decide whether a given line segment intersects a given rectangle. The line is said to intersect the rectangle if the line and the rectangle have at least one point in common. The rectangle consists of four straight lines and the area in between. Although all input values are integer numbers, valid intersection points do not have to lay on the integer grid.
Input
The input consists of n test cases. The first line of the input file
contains the number n. Each following line contains one test case of the
format:
xstart ystart xend yend xleft ytop xright ybottom
where (xstart, ystart) is the start and (xend, yend) the end point of the line and (xleft, ytop) the top left and (xright, ybottom) the bottom right corner of the rectangle. The eight numbers are separated by a blank. The terms top left and bottom right do not imply any ordering of coordinates.
Output
For each test case in the input file, the output file should contain
a line consisting either of the letter "T" if the line
segment intersects the rectangle or the letter "F" if the
line segment does not intersect the rectangle.
Sample Input
1
4 9 11 2 1 5 7 1
Sample Output
F
4. Light Bulbs
Hollywood’s newest theater, the Atheneum of Culture and Movies, has
a huge computer-operated marquee composed of thousands of light bulbs.
Each row of bulbs is operated by a set of switches that are electronically
controlled by a computer program. Unfortunately, the electrician installed
the wrong kind of switches, and tonight is the ACM’s opening night. You
must write a program to make the switches perform correctly.
A row of the marquee contains n light bulbs controlled by n switches.
Bulbs and switches are numbered from 1 to n, left to right. Each bulb can
either be ON or OFF. Each input case will contain the initial state and
the desired final state for a single row of bulbs. The original lighting
plan was to have each switch control a single bulb. However the electrician’s
error caused each switch to control two or three consecutive bulbs, as
shown in Figure 1. The leftmost switch (i = 1) toggles the states of the
two leftmost bulbs (1 and 2); the rightmost switch (i = n) toggles the
states of the two rightmost bulbs (n – 1 and n). Each remaining switch
(1 < i < n) toggles the states of the three bulbs with indices i
– 1, i, and i + 1. (In the special case where there is a single bulb and
a single switch, the switch simply toggles the state of that bulb.) Thus,
if bulb 1 is ON and bulb 2 is OFF, flipping switch 1 will turn bulb 1 OFF
and bulb 2 ON. The minimum cost of changing a row of bulbs from an initial
configuration to a final configuration is the minimum number of switches
that must be flipped to achieve the change.
You can represent the state of a row of bulbs in binary, where 0 means
the bulb is OFF and 1 means the bulb is ON. For instance, 01100 represents
a row of five bulbs in which the second and third bulbs are both ON. You
could transform this state into 10000 by flipping switches 1, 4, and 5,
but it would be less costly to simply flip switch 2.
You must write a program that determines the switches that must be
flipped to change a row of light bulbs from its initial state to its desired
final state with minimal cost. Some combinations of initial and final states
may not be feasible. For compactness of representation, decimal integers
are used instead of binary for the bulb configurations. Thus, 01100 and
10000 are represented by the decimal integers 12 and 16.
Input
The input file contains several test cases. Each test case consists
of one line. The line contains two non-negative decimal integers, at least
one of which is positive and each of which contains at most 6 digits. The
first integer represents the initial state of the row of bulbs and the
second integer represents the final state of the row. The binary equivalent
of these integers represents the initial and final states of the bulbs,
where 1 means ON and 0 means OFF.
To avoid problems with leading zeros, assume that the first bulb in
either the initial or the final configuration (or both) is ON. There are
no leading or trailing blanks in the input lines, no leading zeros in the
two decimal integers, and the initial and final states are separated by
a single blank.
The last test case is followed by a line containing two zeros.
Output
For each test case, print a line containing the case number and a decimal
integer representing a minimum-cost set of switches that need to be flipped
to convert the row of bulbs from initial state to final state. In the binary
equivalent of this integer, the rightmost (least significant) bit represents
the nth switch, 1 indicates that a switch has been flipped, and 0 indicates
that the switch has not been flipped. If there is no solution, print “impossible”.
If there is more than one solution, print the one with the smallest decimal
equivalent.
Print a blank line between cases. Use the output format shown in the
example.
Sample Input
12 16
1 1
3 0
30 5
0 0
Output for the Sample Input
Case Number 1: 8
Case Number 2: 0
Case Number 3: 1
Case Number 4: 10