Problem A. 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

Problem B. Integer approximation ≡

Author:Far-Eastern Subregional
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:8 Mb

Statement

The FORTH programming language does not support floating-point arithmetic at all. Its author, Chuck Moore, maintains that floating-point calculations are too slow and most of the time can be emulated by integers with proper scaling. For example, to calculate the area of the circle with the radius R he suggests to use formula like R * R * 355 / 113, which is in fact surprisingly accurate. The value of 355 / 113 = 3.14159... is approximating the value of π with the absolute error of only about 10-7. You are to find the best integer approximation of a given floating-point number A within a given integer limit L. That is, to find such two integers N and D (1 ≤ N, D ≤ L) that the value of absolute error |A - N / D| is minimal.

Input file format

The first line of input file contains a floating-point number A with the precision of up to 15 decimal digits. The second line contains the integer limit L.

Output file format

Output file must contain two integers, N and D, separated by space.

Constraints

0.1 ≤ A < 10, 1 ≤ L ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
3.14159265358979
10000

355 113

Problem C. Sudoku Checker ≡

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

Statement

The puzzle game of Sudoku is played on a board of N2 × N2 cells. The cells are grouped in N × N squares of N × N cells each. Each cell is either empty or contains a number between 1 and N2.

The sudoku position is correct when numbers in each row, each column and each square are different. The goal of the game is, starting from some correct position, fill all empty cells so that the final position is still correct.

This game is fairly popular in the Internet, and there are many sites which allow visitors to solve puzzles online. Such sites always have a subroutine to determine a correctness of a given position.

You are to write such a routine.

Input file format

Input file contains integer N, followed by N4 integers — sudoku position. Empty cells are denoted by zeroes.

Output file format

Output file must contain a single string 'CORRECT' or 'INCORRECT'.

Constraints

1 ≤ N ≤ 10.

Sample tests

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

CORRECT
2 
2
2 1 3 0
3 2 4 0
1 3 2 4
0 0 0 1

INCORRECT
0.033s 0.004s 11