Problem A. Simple prefix compression
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. Countryside Highway
Statement
Regional government wishes to build a new highway across the region, and it seems that the best route for the highway goes across the Kvadratnaya village.
The village consists of the N x N square estates.
All estates have a size of 100 by 100 meters.
Therefore, in the coordinate system tied to the village, the southwestern corner of the village has coordinates (0, 0), and northeastern corner - coordinates (N*100, N*100).
The highway will cross the village form the west to the east side, cutting through several estates. The government decided to compensate owners of those estates, and to estimate the necessary expenses one should calculate the number of estates crossed by the highway.
Given the village size N and the coordinates of the points where the highway crosses eastern and western borders of the village, you must find the number of estates.
You can assume, for the purpose of increasing the financial appeal of the highway project, that the highway is a straight line (i.e. has zero width).
If the highway just touches the edge of an estate, it is still considered a crossing.
The highway is a line between points (0, W) and (100*N, E).
Input file format
In the input file, there are three integers, N, W and E, separated by spaces.
Output file format
Output file must contain a single integer - the number of estates crossed by the highway.
Constraints
1 <= N <= 100
0 <= W, E <= 100*N
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
3 150 50
|
4
|
Задача C. Возведение в степень
Условие
Требуется по данным целым положительным числам
a и
b
вычислить значение
ab.
Формат входного файла
Числа
a b.
Формат выходного файла
Единственное число, равное
ab.
Ограничения
1 ≤
a,
b ≤ 1000
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3 5
|
243
|
| 2 |
10 20
|
100000000000000000000
|
Задача D. Молекулы
Условие
Органические вещества отличаются потрясающим разнообразием.
Они различаются по химическому составу (по пропорциям составляющих вещество элементов),
по химической формуле молекул (по порядку расположения и химическим связям атомов)
и по пространственной форме молекул.
Проблема восстановления по химическому составу органического вещества его химической формулы
и проблема пространственного конфигурирования молекул по их химическим формулам -
чрезвычайно актуальные задачи биоинформатики.
К сожалению, они отличаются высокой вычислительной сложностью.
Рассмотрим проблему химической формулы и пространственной конфигурации органических
молекул при следующих упрощающих предположениях:
- вещество состоит только из атомов водорода H (валентность 1),
кислорода O (валентность 2), азота N (валентность 3) и углерода C (валентность 4);
- молекула или группа молекул вещества представляет собой плоскую прямоугольную решётку
из m строк и n столбцов, в узлах которой могут находиться или атомы перечисленных элементов,
или "дырки" - пустоты, не занятые никаким атомом;
- каждый атом в решётке может быть связан с атомами, своими соседями по решётке,
но с каждым соседом он связан не более чем одной связью, а общее число его связей совпадает с его валентностью.
Ваша задача - написать программу, которая для данной прямоугольной решётки,
в узлах которой могут находиться элементы H, O, N, C или дырки ".", определит,
может ли она описывать структуру одной или нескольких молекул.
Формат входного файла
Входной файл для программы описывает одну решетку.
В его первую строку записаны через пробел два целых чисел M и N,
задающих число строк и число столбцов этой решётки.
Следующие M строк содержат ровно по N символов `H`, `O`, `N`, `C`, `.`,
представляющих элементы или "дырки" в порядке слева направо в соответствующей строке решётки.
Формат выходного файла
В выходной файл программы нужно вывести слово
Valid, если данная решетка может описывать
структуру одной или нескольких молекул, или
Invalid, в противном случае.
Ограничения
1 ≤ M, N ≤ 50
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3 4
HOH.
NCOH
OO..
|
Valid
|
Задача E. Умножение неотрицательных длинных чисел
Условие
Требуется по данным целым неотрицательным числам
a и
b
вычислить значение
a *
b.
Формат входного файла
В первой строке число
a. Во второй строке число
b.
Формат выходного файла
Единственное число, равное
a *
b.
Ограничения
0 ≤
a,
b ≤ 10
3000
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3
5
|
15
|
| 2 |
100000000000000000000
29
|
2900000000000000000000
|
