Николай Киров
Студентски състезания по програмиране

Задачи, задачи ...

Решения изпращайте на познатия адрес :)


1. Homer Simpson

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


2. Transformations

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.


3. Intersection

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