Задача A. Шарики

Входной файл: INPUT. TXT Ограничение времени на один тест: 1 секунда

Выходной файл: OUTPUT. TXT Ограничение памяти на один тест: 64 Мбайт

Недавно на уроке физики Ваня изучал законы упругости. Учитель демонстрировал законы с помощью специальной системы: по одной прямой линии с двух сторон навстречу друг другу выкатывались два шарика с одинаковыми скоростями и массами. Поскольку система специальная, то при столкновении шариков трения не происходило, после одного столкновения шарики продолжали свое движение в противоположные стороны с теми же скоростями по той же прямой. Для следующего эксперимента учитель запустил с одной стороны прямой 2 шарика равных масс с равным скоростями на некотором расстоянии друг от друга, а навстречу им с другой стороны 3 шарики с такими же массами, скоростями и таким же расстоянием между соседними. Ученики должны были посчитать, сколько всего столкновений произойдет в такой системе, и конечно же, только Ваня смог правильно сосчитать 6 столкновений.

Ване стало так интересно, что он задумался о том, сколько же столкновений произойдет, если по одной прямой будут двигаться N шаров, между которыми одинаковые промежутки, с одной и той же скоростью в одном и том же направлении, а навстречу им по той же прямой с той же скоростью будут двигаться M таких же шаров с такими же промежутками между ними. Будем считать, что прямая, по которой движутся шары, бесконечна и не ограничена ни с одной, ни с другой стороны.

Формат входных данных:

В единственной строке входного файла записаны два целых числа N и M (0£N,M£105), разделенные пробелом.

Формат выходных данных:

В выходной файл выведите единственное целое число – количество столкновений.

Задача B. День рождения

Входной файл: INPUT. TXT Ограничение времени на один тест: 1 секунда

Выходной файл: OUTPUT. TXT Ограничение памяти на один тест: 64 Мбайт

Мальчик Ваня очень любит праздновать дни рождения, как свои, так и дни рождения своих друзей. Но он считает, что праздник бывает вдвойне веселее, если в один и тот же день двое человек празднуют свои дни рождения.

В этом году Ваня с родителями переехал, и ему придется идти в новую школу. Ваня точно знает, что все ученики его нового класса родились в 2002 году, и он, конечно же, мечтает о том, чтобы в его классе нашлись хотя бы двое учеников, дни рождения которых полностью совпадают. Недавно Ваня начал изучать теорию вероятности и с удивлением узнал, что если в классе 23 человека, то вероятность того, что среди учеников этого класса есть хотя бы двое с совпавшими днями рождения, составляет более ½, то есть такая пара учеников скорее найдется, чем нет. И тогда его заинтересовал вопрос о том, сколько же учеников класса достаточно, чтобы вероятность появления среди них пары с совпавшими днями рождения была больше заданной дроби M/K?

Помогите Ване ответить на этот вопрос. Напишите программу, которая определяет при каком минимальном N, в классе из N учеников вероятность наличия хотя бы двух учеников, которые празднуют свои дни рождения в один и тот же день, больше значения дроби M/K?

Формат входных данных:

В первой строке входного файла записаны два целых числа M, K (0<M<K£ 105), разделенных пробелами.

Формат выходных данных:

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

Названия чисел

Входной файл: INPUT. TXT Ограничение времени на один тест: 1 секунда

Выходной файл: OUTPUT. TXT Ограничение памяти на один тест: 64 Мбайт

Мальчику Ване поручили научить группу школьников младших классов правильно писать числительные. Он решил сделать для своих учеников наглядный материал – карточки с русскими буквами, на каждой карточке записана одна русская буква (неважно заглавная или прописная). С помощью этих карточек школьники должны будут выложить названия всех числительных от A до B включительно. Например, для того, чтобы выложить все числительные от 100 до 102 требуется 16 карточек:

Ваня понимает, что некоторые буквы ему придется написать по несколько раз, а некоторые буквы ему вообще не нужны (например, буква «Г» не встречается ни в одном числительном). Помогите Ване посчитать, сколько всего карточек с буквами ему нужно изготовить.

Напишите программу, которая вычисляет количество карточек с буквами, необходимых для выкладывания одновременно названий всех числительных от A до B включительно.

Формат входных данных:

В первой строке содержатся два целых числа A и B (0<A£B< 106), разделенные пробелом.

Формат выходных данных:

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

Задача D. Сеть

Входной файл: INPUT. TXT Ограничение времени на один тест: 1 секунда

Выходной файл: OUTPUT. TXT Ограничение памяти на один тест: 64 Мбайт

В закрытой организации «Рожки и копыжки» наконец смонтировали компьютерную сеть. Хакер О’Бендер, внедрившийся в компанию в качестве сотрудника, хочет взломать ее сервер и украсть секрет производства стульев с интегрированными сейфами. Для этой цели ему нужно заполучить пароль администратора сервера Кисы.

Известно, что сеть состоит из 1 <= N <= 106 сетевых устройств, которые делятся на три класса:

1.  компьютеры;

2.  коммутаторы;

3.  концентраторы.

За компьютерами, как правило, сидят пользователи. Некоторые компьютеры могут содержать данные и приложения, необходимые для работы нескольким пользователям. В этом случае они являются серверами, и доступ к ним осуществляется по сети с других компьютеров, хотя он также может осуществляться локально. Компьютеры обмениваются данными между собой посредством передачи пакетов.

Каждый компьютер имеет ровно один сетевой порт и, следовательно, может быть подключен ровно к одному другому сетевому устройству.

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

Коммутатор работает по следующему принципу – при получении пакета на одном из его сетевых портов, он пересылает его ровно на один другой порт, ближайший к компьютеру получателя.

Концентратор же при получении пакета, пересылает его на все свои порты, кроме того, откуда пришел пакет.

Каждая сетевая связь соединяет ровно два устройства и обеспечивает передачу пакетов в обе стороны.

Известно, что сеть построена правильно. Выполняются следующие условия:

1.  Отсутствуют параллельные связи между любыми двумя устройствами. Нет такого, чтобы два коммутатора или концентратора были связаны между собой более чем одной связью.

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

3.  Между любыми двумя сетевыми устройствами существует ровно один однозначный и одновременно кратчайший путь передачи пакетов.

4.  Каждое сетевое устройство имеет номер из диапазона от 1 до N.

5.  Пакет передается по сети всегда наикратчайшим путем.

О’Бендеру стало известно, что администратор Киса работает за компьютером c номером 1 <= A <= N, а взлавымаевый сервер имеет номер 1 <= B <= N. Гарантируется, что A и B являются номерами компьютеров. Каждый раз в начале сессии доступа к серверу Киса вводит пароль, который в открытой форме в виде пакета отправляется по сети на сервер.

Напишите программу, которая подсчитывает количество компьютеров, на которых О’Бендер может установить сниффер (специальную программу для перехвата пакетов), чтобы перехватить пакет с паролем.

Формат входных данных:

В первой строке входного файла через пробел указываются: N ­­– число сетевых устройств, M ­– число сетевых связей между ними, A – номер компьютера Кисы, B – номер сервера, хранящего секрет производства стульев с интегрированными сейфами.

Во второй строке приводится N символов, i-й символ (1 <= i <= N) описывает класс сетевого устройства с номером i: ‘c’ – компьютер, ‘s’ – коммутатор, ‘h’ – концентратор.

В последующих M строках задаются пары целых чисел uj и vj (1 <= j <= M), представляющих собой номера сетевых устройств, соединяемых соответствующей сетевой связью.

Формат выходных данных:

В единственной строке содержится(выведите) целое число – количество компьютеров, на которые О’Бендер может установить сниффер для перехвата пакета с паролем.

Задача E. Военная стратегия

Входной файл: INPUT. TXT Ограничение времени на один тест: 1 секунда

Выходной файл: OUTPUT. TXT Ограничение памяти на один тест: 64 Мбайт

В 2100 году земляне изобрели сверхсветовой космический двигатель, работающий на основе пупкинского бредонаноидального принципа. За пять последующих столетий они покорили весь Млечный путь, колонизировав каждую пригодную для жизни планету.

Также на удивительно плоском астероиде P-caps была размещена научно-исследовательская база, занимающаяся изучением его необычного минерального состава. В 2666 году вражеский десант представителей злобной внеземной расы полностью захватил базу, пленив всех работавших на ней землян.

Вы – капитан огромного космического крейсера Атлантида, отправившегося освободить P-caps. Собранные данные разведки показали, что база имеет плоскую форму окружности(круга) с центром (a, b) и радиусом R, корабль захватчиков представляет собой плоский треугольник с вершинами, имеющими координаты (x1, y1), (x2, y2) и (x3, y3). Инопланетяне не могут выйти из корабля и удерживают людей силовым полем. Внутри корабля инопланетяне расположились в тех точках треугольника, которые находятся на территории базы землян.

В Вашем распоряжении имеется оружие NidleStorm, входящее в штатное вооружение Атлантиды. Оно способно осуществить массовый синхронный запуск любого числа ракет, каждая из которых может поразить точку только с целочисленными координатами астероида.

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

Необходимо определить число ракет K, которым ударит NidleStorm.

Формат входных данных:

В первой строке входного файла через пробел записано 9 целых чисел ­– a, b, R, x1, y1, x2, y2, x3, y3. Все числа по модулю не превышают 104.

Формат выходных данных:

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

что делать с точками, лежащими на пересечении

Задача F. Раздельный старт

Входной файл: INPUT. TXT Ограничение времени на один тест: 1 секунды

Выходной файл: OUTPUT. TXT Ограничение памяти на один тест: 64 Мбайт

Во время велосипедной гонки с раздельным стартом N велосипедистов стартуют по очереди c точки старта с интервалом в 1 минуту. По дистанции длиной L км каждый велосипедист двигается с постоянной скоростью: i велосипедист проезжает 1 километр за wi мин. Если i гонщик стартовал позже j-го, но на финиш приехал раньше него, то где-то на дистанции произошел обгон. Напишите программу для подсчета суммарного числа обгонов во время гонки.

Формат входных данных:

Первая строка входного файла содержит два целых числа N и L (1<=N<= 1<=L<=109). Во второй строке входного файла через пробел расположены N целых чисел wi (1<= wi <=109).

Формат выходных данных:

Единственная строка выходного файла содержит целое число – суммарное число обгонов во время гонки.

Задача G. Ремонт

Входной файл: INPUT. TXT Ограничение времени на один тест: 1 секунды

Выходной файл: OUTPUT. TXT Ограничение памяти на один тест: 64 Мбайт

Вася Пупкин решил постелить новый ламинат во всех комнатах своей трехкомнатной квартиры. Он измерил длину и ширину каждой комнаты в метрах, но полученные шесть чисел записал на листочек бумаги в произвольном(перепутанном) порядке и не может (теперь) сказать, какой комнате какое измерение соответствует. В магазине Вася хочет купить минимальное количество ламината, но чтобы его при этом гарантированно хватило для покрытия полов во всех комнатах квартиры. Напишите программу для определения этого количества.

Формат входных данных:

Единственная строка входного файла содержит через пробел шесть целых чисел – размеры комнат в квартире, измеренные в метрах. Каждое число находится в диапазоне от 1 до 1000.

Формат выходных данных:

Единственная строка выходного файла содержит минимальное количество квадратных метров ламината, которого гарантированно хватит для покрытия полов во всех комнатах квартиры.

Задача H. Треугольность текста

Входной файл: INPUT. TXT Ограничение времени на один тест: 1 секунда

Выходной файл: OUTPUT. TXT Ограничение памяти на один тест: 64 Мбайт

На уроке русского языка Ваня изучал методы анализа текстов. Учитель долго рассказывал про морфологический, морфемный, синтаксический и семантический анализ. Но поскольку любимый предмет Вани – математика, то он решил изучать дома самостоятельно числовые характеристики текста, в частности, его треугольность. Для проведения своего анализа Ваня взял сборник стихотворений на английском языке.

Треугольность стихотворения определим так. Сначала разделим текст на слова, словом будем считать последовательность латинских букв, не содержащую других символов. Затем для каждого слова посчитаем сумму номеров букв, из которого оно состоит, в алфавите (регистр букв значения не имеет). Например, для слова 'little' это будет 12 + 9+ 20 + 20 + 12 + 5 = 78. Тогда, если полученная сумма - треугольна, то есть представима в виде , где m - натурально, то и слово треугольно. Например, 78 представимо как , поэтому слово 'little' – треугольное. Треугольность текста – это сумма номеров строк, умноженных на количество треугольных слов в них.

Напишите программу, которая определяет треугольность заданного фрагмента текста на английском языке.

Формат входных данных:

В первой строке входного файла записано N (0<N£ 104)– количество строк заданного фрагмента. Далее следует N непустых строк текста, каждая строка имеет длину не более 255 символов, и состоит из латинских букв, пробелов, знаков препинания (точка, запятая, двоеточие, тире, точка с запятой, вопросительный и восклицательный знаки).

Формат выходных данных:

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