Задача A. В ожидании Нового года

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

Условие

31 декабря. Марфа Геннадьевна и Глафира Сергеевна уже приготовили новогодний ужин, и теперь они с нетерпением ждут Нового года.

Каждые 5-10 минут они смотрят на часы и вычисляют, сколько часов и минут осталось до Нового года. При этом на вычисление у них уходит много времени.

Поэтому им хотелось бы иметь компьютерную программу, принимающую на вход текущее время (часы и минуты) и вычисляющую, сколько времени осталось до Нового года.

Число секунд в текущем времени принять равным 0.

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

Входной файл содержит текущее время — часы и минуты.

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

Требуется вывести в выходной файл, сколько времени осталось до Нового года — часы и минуты.

Ограничения

Часы от 0 до 23. Минуты от 0 до 59.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
12 0
12 0
2
23 59
0 1
3
22 25
1 35

Задача B. Новогодний пузырь

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

Условие

Новогодняя вечеринка проходит в плоском прямоугольном зале с координатами левого нижнего угла (0, 0), а правого верхнего — (1000, 1000). С потолка зала свешивается мишура в виде N прямых тонких вертикальных лент с координатами нижних концов (xi, yi). Один из гостей запустил мыльный пузырь радиуса R. Первоначально центр пузыря находился в точке (x, R). Пузырь полетел вертикально вверх до столкновения с лентой мишуры или потолком, после чего лопнул. Требуется определить, с чем именно он столкнулся.

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

В первой строке входного файла содержатся числа N R x, в следующих N строках содержатся вещественные числа xi yi. Числа в строке разделены пробелами. Значения всех xi во входном файле различны.

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

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

Ограничения

0 ≤ N ≤ 100, 0 < R ≤ 50, R ≤ x < 1000 − R

0 < xi < 1000, 0 < yi < 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 20.0 50
30 70
50 81.5
70 79
2

Задача C. Новогодняя ёлка-1

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

Условие

В детском саду города N для празднования Нового Года установили ёлку и для её украшения закупили K разноцветных шаров.

Шары характеризуются своей массой. Елка характеризуется максимальным весом, который она может выдержать, при этом не упав. Красота елки равна количеству висящих на ней шаров. Так как дети хотят удивить Деда мороза, они хотят как можно красивее украсить ёлку, при этом она не должна упасть.

Вас просят написать программу, которая по заданным параметрам игрушек и ёлки определит максимально возможную красоту наряженной ёлки.

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

Во входном файле содержатся числа M и K — соответственно максимальный вес ёлки и количество купленных шаров. За ними следуют K чисел vi — вес i-того шара.

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

В выходном файле должно содержаться единственное число — максимально возможная красота наряженной ёлки.

Ограничения

1 ≤ M ≤ 10001 ≤ K ≤ 100000 1 ≤ vi ≤ 1000

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

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

Задача D. Воздушный замок

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

Условие

Накануне нового года Дед Мороз занимается свим привычным делом: он строит воздушные замки. Пространство в котором Дед Мороз строит замки - это куб, который состоит из NxNxN маленьких кубиков. Каждый маленький кубик может быть занят облаком или не занят. Воздушный замок Деда Мороза - это прямоугольный паралеллепипед с целочисленными координатами, стороны которого параллельны осям координат. Кроме того, в пространсте есть M облаков. Дед Мороз не хочет, чтобы его замок задевал облака. Замок задевает облако, если они имеют общую клетку.

Помогите Деду Морозу постоить наибольший по объему замок.

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

Во входном файле содержатся числа N и M. За ними следуют M троек чисел - координаты облаков. Все координаты находятся в пределах между 1 и N включительно. Облака могут занимать одну и ту же клетку.

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

В выходном файле должно содержаться единственное число - объем самого просторного замка.

Ограничения

1 ≤ N ≤ 80 0 ≤ M ≤ 200000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 1
1 1 2
4
2
3 0
27

Задача E. Новогодняя ёлка-2

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

Условие

В детском саду города N для празднования Нового Года установили ёлку и для её украшения закупили K елочных игрушек.

Елочные игрушки характеризуются двумя параметрами — массой и красотой. Елка также характеризуется двумя параметрами — максимальной массой игрушек, которую она может выдержать и красотой. Красота елки равна сумме красот всех висящих на ней игрушек. Так как дети хотят удивить Деда мороза, они хотят как можно красивее украсить ёлку, при этом она не должна упасть.

Вас просят написать программу, которая по заданным параметрам игрушек и ёлки определит максимально возможную красоту наряженной ёлки.

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

Во входном файле содержатся числа M и K — соответственно максимальная масса игрушек на ёлке и количество купленных игрушек. За ними следуют K пар чисел vi ki соответственно вес и красота i-той игрушки.

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

В выходном файле должно содержаться единственное число - максимально возможная красота наряженной ёлки.

Ограничения

1 ≤ K, M ≤ 100 1 ≤ vi, ki ≤ 100

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

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

Задача F. Новогодняя ёлка-3

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

Условие

В детском саду города N для празднования Нового Года установили ёлку и для её украшения закупили K елочных игрушек.

Елочные игрушки характеризуются двумя параметрами — массой и красотой. Елка характеризуется тремя параметрами — максимальной массой игрушек, которую она может выдержать, красотой, а также максимальной перегрузкой в одну из сторон (максимальная разница между суммарной массой игрушек на левой и на правой стороне). Красота елки равна сумме красот всех висящих на ней игрушек. Так как дети хотят удивить Деда мороза, они хотят как можно красивее украсить ёлку, при этом она не должна упасть.

Вас просят написать программу, которая по заданным параметрам игрушек и ёлки определит максимально возможную красоту наряженной ёлки.

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

Во входном файле содержатся числа M K Δ — соответственно максимальная масса игрушек на ёлке, количество купленных игрушек и максимальное отклонение. За ними следуют K пар чисел vi ki соответственно вес и красота i-той игрушки.

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

В выходном файле должно содержаться единственное число - максимально возможная красота наряженной ёлки.

Ограничения

1 ≤ К, M ≤ 100 1 ≤ vi, ki ≤ 100 0 ≤ Δ ≤ 20

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

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

Problem G. Ball of fir

Author:G. Grenkin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Mathematicians from the Institute of New Year Research developed a mathematical model of the New Year fir-tree. In this model the fir is supposed to be a sphere with a radius of 1 meter. Modeling of a fir garland is, however, more complicated.

A fir garland is modeled with a curve located on the sphere. The curve begins at the topmost point of the sphere, ends at the bottommost point of the sphere, and makes exactly N turns around it.

Consider spherical coordinates φ (longitude) and θ (latitude). The initial value of longitude equals 0, longitude makes exactly N turns and the final value equals 0 again. The initial value of latitude equals 90°, the final value equals  − 90°. The increment of latitude is proportional to the increment of longitude.

Your program must, for a given value of N, calculate the length of the curve which models a fir garland.

Input file format

Input file contains a single integer N.

Output file format

Output file must contain a single real number — the length of the curve (in meters) with at least 3 correct digits after decimal point.

Constraints

1 ≤ N ≤ 100

Sample tests

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

Задача H. В лесу родилась ёлочка

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

Условие

Скоро Новый год, и Марфа Геннадьевна послала своих сыновей срубить несколько ёлок на продажу.

Хорошие, толстые, густые ёлки стоят на рынке 5000 руб., а ёлки похуже, тонкие, менее густые стоят 2000 руб.

На всё про всё у ребят есть ровно T минут. Хорошие ёлки растут подальше, и рубить их дольше. Ёлки похуже растут поближе, и рубить их быстрее. На то, чтобы дойти до i-й ёлки, срубить её и вернуться домой, нужно затратить ti минут.

У ребят есть электронная карта участка леса, на которой отмечены ёлки. Сейчас им ой как нужна программа, вычисляющая максимально возможную выручку.

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

Входной файл содержит целое число T. Далее идёт целое число N — количество хороших ёлок, за которым следуют N целых чисел ti.

Далее следует число M — количество ёлок похуже. За ним следуют M целых чисел ti.

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

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

Ограничения

1 ≤ N, M ≤ 1000

1 ≤ T ≤ 10000

1 ≤ ti ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
250
1
240
2
120 100
5000
2
250
1
240
3
60 80 70
6000

0.503s 0.013s 31