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. Countryside Highway

Author:unknown
Input file:input.txt   Time limit:15 sec
Output file:output.txt   Memory limit:200 Mb

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. Возведение в степень

Автор:А. Кленин
Входной файл:input.txt   Ограничение времени:3 сек
Выходной файл:output.txt   Ограничение памяти:4 Мб

Условие

Требуется по данным целым положительным числам a и b вычислить значение ab.

Формат входного файла

Числа a b.

Формат выходного файла

Единственное число, равное ab.

Ограничения

1 ≤ a, b ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 5
243
2
10 20
100000000000000000000

Задача D. Молекулы

Автор:Всесебирская олимпиада 2004
Входной файл:input.txt   Ограничение времени:6 сек
Выходной файл:output.txt   Ограничение памяти:16 Мб

Условие

Органические вещества отличаются потрясающим разнообразием. Они различаются по химическому составу (по пропорциям составляющих вещество элементов), по химической формуле молекул (по порядку расположения и химическим связям атомов) и по пространственной форме молекул. Проблема восстановления по химическому составу органического вещества его химической формулы и проблема пространственного конфигурирования молекул по их химическим формулам - чрезвычайно актуальные задачи биоинформатики. К сожалению, они отличаются высокой вычислительной сложностью.

Рассмотрим проблему химической формулы и пространственной конфигурации органических молекул при следующих упрощающих предположениях:

  1. вещество состоит только из атомов водорода H (валентность 1), кислорода O (валентность 2), азота N (валентность 3) и углерода C (валентность 4);
  2. молекула или группа молекул вещества представляет собой плоскую прямоугольную решётку из m строк и n столбцов, в узлах которой могут находиться или атомы перечисленных элементов, или "дырки" - пустоты, не занятые никаким атомом;
  3. каждый атом в решётке может быть связан с атомами, своими соседями по решётке, но с каждым соседом он связан не более чем одной связью, а общее число его связей совпадает с его валентностью.
Ваша задача - написать программу, которая для данной прямоугольной решётки, в узлах которой могут находиться элементы 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. Умножение неотрицательных длинных чисел

Автор:А. Кленин
Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:4 Мб

Условие

Требуется по данным целым неотрицательным числам a и b вычислить значение a * b.

Формат входного файла

В первой строке число a. Во второй строке число b.

Формат выходного файла

Единственное число, равное a * b.

Ограничения

0 ≤ a, b ≤ 103000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5
15
2
100000000000000000000
29
2900000000000000000000

0.078s 0.006s 15