ACM 2003 
Problem B. Advanced ASCII Cubes 
Author: A. Klenin

Input file: input.txt 
Output file: output.txt 
Time limit: 3(sec) 

Statement

The table surface is divided into N by M square cells. Some cubes are stacked one upon another over the cells, forming towers. For each cell the number of cubes stacked over it is given in the matrix A.

Your program must output the view of the table in ASCII graphics, where each cube is represented as shown below:

  +---+
 /   /|      
+---+ |      
|   | + 
|   |/ 
+---+

 (here the characters used are '+', '-', '/', '|', their ASCII codes are ASCII 43, 45, 47, 124) 


The dot (ASCII 46) must be used as a background. 

Constraints
1 ? N, M, Aij ? 50 

Input file format
Input file contains integers N M, followed by matrix A, row-by-row. The first row describes the cube tower furthest from the viewer, left to right, and the last row -- nearest to the viewer. 

Output file format
Output file must contain a string representation of the table view, with minimal number of lines required to show all cubes. Each line must contain a string of equal length, which is the minimal width required to show all cubes. 

Sample input #1
3 4
1 1 1 1
1 2 1 1
1 1 1 1
Sample output #1
       
........+---+..........
......+/   /|-+---+---+
...../+---+ |/   /   /|
....+-|   | +---+---+ |
.../  |   |/   /   /| +
..+---+---+---+---+ |/.
./   /   /   /   /| +..
+---+---+---+---+ |/...
|   |   |   |   | +....
|   |   |   |   |/.....
+---+---+---+---+......
  
Sample input #2
3 5
2 2 1 2 2
2 2 1 1 2
3 2 1 2 2

Sample output #2

......+---+---+...+---+---+
..+---+  /   /|../   /   /|
./   /|-+---+ |.+---+---+ |
+---+ |/   /| +-|  /   /| +
|   | +---+ |/+---+---+ |/|
|   |/   /| +/   /   /| + |
+---+---+ |/+---+---+ |/| +
|   |   | +-|   |   | + |/.
|   |   |/  |   |   |/| +..
+---+---+---+---+---+ |/...
|   |   |   |   |   | +....
|   |   |   |   |   |/.....
+---+---+---+---+---+......
  

--------------------------------------------------------------------------------

ACM 2003 
Problem C. Water pipe 
Author: A. Klenin

Input file: input.txt 
Output file: output.txt 
Time limit: 2(sec) 

Statement
The Eastowner city is perpetually haunted with water supply shortages, so in order to remedy this problem a new water-pipe has been built. Builders started the pipe from both ends simultaneously, and after some hard work both halves were connected. Well, almost. First half of pipe ended at a point (x1, y1), and the second half -- at (x2, y2). Unfortunately only few pipe segments of different length were left. Moreover, due to the peculiarities of local technology the pipes can only be put in either north-south or east-west direction, and be connected to form a straight line or 90 degree turn. You program must, given L1, L2, … Lk -- lengths of pipe segments available and C1, C2, … Ck -- number of segments of each length, construct a water pipe connecting given points, or declare that it is impossible. Program must output the minimum required number of segments.  

Constraints
1 ? k ? 4, 1 ? xi, yi, Li ? 1000, 1 ? Ci ? 10 

Input file format
Input file contains integers x1 y1 x2 y2 k followed by 2k integers L1 L2 … Lk C1 C2 … Ck 

Output file format
Output file must contain a single integer -- the number of required segments, or ?1 if the connection is impossible. 

Sample input #1
20 10 60 50 2 70 30 2 2
Sample output #1
4
  
Sample input #2
5 5 5 6 1
2 10
Sample output #2
-1

--------------------------------------------------------------------------------

CATS, 01-11-2003 14:10  
ACM 2003 
Problem E. Beach cut 
Author: B. Vasilyev, A. Klenin

Input file: input.txt 
Output file: output.txt 
Time limit: 4(sec) 

Statement

The seashore is represented by a polyline without self-intersections, described by a sequence of vertices (x1, y1), … (xN, yN). It also has a property that xi < xi + 1. The sea is above the line, and the beach -- below.

Your program must connect two vertices with a straight line not longer than L chosen so as to maximize the beach area enclosed between that line and the shore. The line must not intersect with the sea and may only touch, not intersect, the shore polyline.

 

Constraints
3 ? N ? 5000, 0 ? xi, yi, L ? 1000000 

Input file format
Input file contains integer numbers N L, followed by N pairs of integers x1 y1 … xN yN. 

Output file format
Output file must contain a single floating point value -- the maximum area that can be cut (it may be zero). The area must be output exactly, i.e. without any rounding at all. 

Sample input #1
5 4
0 0  1 3  2 0  3 3  4 0
Sample output #1
6
Sample input #2
3 10
100 100  101 0  102 100
Sample output #2
0

--------------------------------------------------------------------------------

CATS, 01-11-2003 14:10  
ACM 2003 
Problem D. One is good, but two is better 
Author: A. Klenin

Input file: input.txt 
Output file: output.txt 
Time limit: 2(sec) 

Statement
Given the N by M matrix with elements equal either 0, 1 or 2, There is at least one element equal to 2. Your program must find such two (perhaps overlapping or even identical) rectangles, that they would contain all the 2s which are in matrix, but none of the 1s. If several solutions exist, the program must find a solution with minimal area of joined rectangles. For example, in the matrix 

 1 2 1 0
 2 0 2 2
 1 2 1 0
 
these rectangles are (2,1)-(2,3) and (1,2)-(4,2), with the combined area of 6. 

Constraints
1 ? N, M ? 50 

Input file format
Input file contains integers N and M followed by N * M matrix elements. 

Output file format
Output file must contain a single integer -- the minimal area, or -1 if no solution exists 

Sample input #1
3 4
1 2 1 0
2 0 2 2
1 2 1 0
Sample output #1
6

--------------------------------------------------------------------------------

CATS, 01-11-2003 14:11  




