Problem A. Nearest number - 2 ≡

 Author: A. Klenin Input file: input.txt Time limit: 5 sec Output file: output.txt Memory limit: 200 Mb

Statement

Input is the matrix A of N by N non-negative integers.

A distance between two elements Ai j and Ap q is defined as |ip| + |jq|.

Your program must replace each zero element in the matrix with the nearest non-zero one. If there are two or more nearest non-zeroes, the zero must be left in place.

Input file format

Input file contains the number N followed by N2 integers, representing the matrix row-by-row.

Output file format

Output file must contain N2 integers, representing the modified matrix row-by-row.

Constraints

1 ≤ N ≤ 200, 0 ≤ Ai ≤ 1000000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
0 0 0
1 0 2
0 3 0
1 0 2
1 0 2
0 3 0

Problem B. Advanced ASCII Cubes ≡

 Author: A. Klenin Input file: input.txt Time limit: 3 sec Output file: output.txt Memory limit: 200 Mb

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.

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.

Constraints

1 ≤ N, M, Aij ≤ 50

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 4
1 1 1 1
1 2 1 1
1 1 1 1
........+---+..........
......+/   /|-+---+---+
...../+---+ |/   /   /|
....+-|   | +---+---+ |
.../  |   |/   /   /| +
..+---+---+---+---+ |/.
./   /   /   /   /| +..
+---+---+---+---+ |/...
|   |   |   |   | +....
|   |   |   |   |/.....
+---+---+---+---+......
2
3 5
2 2 1 2 2
2 2 1 1 2
3 2 1 2 2

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

Problem C. Water pipe ≡

 Author: A. Klenin Input file: input.txt Time limit: 2 sec Output file: output.txt Memory limit: 200 Mb

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.

Input file format

Input file contains integers x1 y1 x2 y2 k followed by 2k integers L1 L2Lk C1 C2Ck

Output file format

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

Constraints

1 ≤ k ≤ 4, 1 ≤ xi, yi, Li ≤ 1000, 1 ≤ Ci ≤ 10

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
20 10 60 50 2 70 30 2 2
4

2
5 5 5 6 1
2 10
-1

Problem D. One is good, but two is better ≡

 Author: A. Klenin Input file: input.txt Time limit: 2 sec Output file: output.txt Memory limit: 200 Mb

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.

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

1 ≤ N, M ≤ 50

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 4
1 2 1 0
2 0 2 2
1 2 1 0
6

Problem E. Beach cut ≡

 Author: B. Vasilyev, A. Klenin Input file: input.txt Time limit: 4 sec Output file: output.txt Memory limit: 200 Mb

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.

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.

Constraints

3 ≤ N ≤ 5000, 0 ≤ xi, yi, L ≤ 1000000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4
0 0  1 3  2 0  3 3  4 0
6
2
3 10
100 100  101 0  102 100
0

Problem F. Simple prefix compression ≡

 Author: A. Klenin Input file: input.txt Time limit: 2 sec Output file: output.txt Memory limit: 200 Mb

Statement

Many databases store the data in the character fields (and especially indices) using prefix compression. This technique compresses a sequence of strings A1, ..., AN by the following method: if there are strings Ai = ai,1ai,2...ai,p and Ai + 1 = ai+1,1ai+1,2...ai+1,q

such that for some j ≤ min(p, q) ai,1 = ai+1,1, ai,2 = ai+1,2, ... ai,j = ai+1,j, then the second string is stored as [j]ai+1,j+1ai+1,j+2... ai+1,q, where [j] is a single character with code j.

If j = 0, that is, strings do not have any common prefix, then the second string is prefixed with zero byte, and so the total length actually increases.

Input file format

First line of input file contains integer number N, with following N lines containing strings A1 ... AN

Output file format

Output file must contain a single integer — minimal total length of compressed strings.

Constraints

1 ≤ N ≤ 10000, 1 ≤ length(Ai) ≤ 255.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
abc
atest
atext

11
2
2
test
notest

11

0.062s 0.004s 21