Задача A. Длинный спуск (45 баллов) ≡

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

Условие

Рельеф горного массива представлен матрицей размером NxN, с элементами, задающими высоту участков местности. Лыжник желает найти самый длинный спуск, т.е. такую строго убывающую последовательность соседних по вертикали или горизонтали элементов ai1,j1 > ai1,j1 > … > aiL,jL, что значение L (длина последовательности)  — максимально возможное.

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

Входной файл содержит число N, за которыми следует N2 чисел a1,1 a1,2 … a1,N a2,1 a2,2 … a2,N … aN,N. Все числа — целые.

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

Выходной файл должен содержать искомую максимальную последовательность элементов. Если существует несколько максимальных последовательностей, следует вывести любую из них.

Ограничения

1 ≤ N ≤ 1000, 0 ≤ ai,j ≤ 106.

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
4
1 1 1 1
1 1 1 1
1 3 7 1
9 1 8 1

8 7 3 1

Задача B. Sandcraft (45 баллов) ≡

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

Условие

Имеется N песчаных карьеров, песок с которых доставляют на склад при помощи K одинаковых грузовиков. Грузовики движутся с постоянной скоростью, которая позволяет им преодолеть расстояние до i-го карьера за di часов.

Для того, чтобы заполнить грузовик песком, требуется ровно W часов. Одновременно на одном карьере может загружаться только один грузовик. Разгрузка любого колиества грузовиков на складе происходит моментально.

Требуется определить максимальный объём песка (измеренный в грузовиках), который можно доставить на склад за T часов.

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

Входной файл содержит числа N K W T, за которыми следует N чисел d1 d2 … dN. Все числа — целые.

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

Выходной файл должен содержать единственное целое число (возможно, ноль) — максимальный объём песка.

Ограничения

1 ≤ N,K,W,di ≤ 100, 1 ≤ T ≤ 1000.

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
2 2 1 8
3 5

2
2 
2 2 3 15
5 6

2

Задача C. Табуретки-1 ≡

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

Условие

Для изготовления качественной табуретки необходимы 4 ножки одинаковой длины. На табуреткоизготовительную фабрику поступило N ножек, имеющих слегка различающиеся длины L1, L2, …, LN.

Требуется определить максимальное количество качественных табуреток, которые можно изготовить из данных ножек.

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

Входной файл содержит число N, за которым следуют N чисел Li — длины ножек. Все числа целые.

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

В выходной файл следует вывести единственное целое число — максимальное количество табуреток.

Ограничения

1 ≤ N ≤ 10000, 1 ≤ Li ≤ 100.

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
9
17 18 18 17 17 16 17 17 19
 
1

Задача D. Лягушка на деревьях (65 баллов) ≡

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

Условие

Вдоль лесной тропинки растёт N деревьев высотой h1, h2, …, hN метров соответственно. Расстояние между соседними деревьями равно 1 метру.

Лягушка сидит на дереве с номером A и хочет попасть на дерево с номером B. Поскольку лазить по деревьям она не может, ей остаётся только перепрыгивать с одной вершины дерева на другую. При этом лягушка может развивать начальную скорость от 0 до v м/с, и прыгать под углом от 0 до α градусов.

Требуется найти минимальное количество прыжков, которое потребуются лягушке, или определить, что достичь цели невозможно. Ускорение свободного падения g следует принять равным 10 м/с2.

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

Входной файл содержит числа N A B v α, за которыми следует N чисел h1 h2 … hN. Числа v и α — вещественные, остальные числа — целые.

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

Выходной файл должен содержать единственное целое число — необходимое количество прыжков, или −1, если решения не существует.

Ограничения

1 ≤ A, B ≤ N ≤ 100, 1 ≤ hi ≤ 1000, 0.01 ≤ v ≤ 1000, 0.01 ≤ α ≤ 90.

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
2 1 2 10 80 
5 6

1

Задача E. Табуретки-2 (30 баллов) ≡

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

Условие

Для изготовления качественной табуретки необходимы 4 ножки одинаковой длины. На табуреткоизготовительную фабрику поступило N ножек, имеющих слегка различающиеся длины L1, L2, … LN. Научно-исследовательский отдел фабрики обнаружил, что выпуск табуреток можно увеличить, если укорачивать некоторые ножки. При этом отпиленная часть выбрасывается.

Требуется определить минимальное количество распилов, необходимых для для изготовления N / 4 качественных табуреток.

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

Входной файл содержит число N, за которым следуют N чисел Li — длины ножек. Все числа целые.

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

В выходной файл следует вывести единственное целое число — минимальное количество распилов.

Ограничения

1 ≤ N ≤ 10000, N mod 4 = 0, 1 ≤ Li ≤ 100.

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
8
18 16 17 17 16 17 17 19
 
2

Задача F. Уравнение для 5 класса ≡

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

Условие

Уравнение для пятиклассников представляет собой строку длиной 5 символов. Второй символ строки является либо знаком '+' (плюс) либо '-' (минус), четвёртый символ — знак '=' (равно). Из первого, третьего и пятого символов ровно два являются цифрами из диапазона от 0 до 9, и один — буквой x, обозначающей неизвестное.

Требуется решить данное уравнение относительно x.

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

Входной файл содержит единственную строку — уравнение.

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

В выходной файл следует вывести единственное целое число — значение x.

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
x+5=7
 
2
2 
3-x=9
 
-6
0.691s 0.022s 25