#1789

Зоопарк

Темы: [Динамическое программирование]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2006, Задача J ]

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

Например, если в зоопарке два медведя, тигр, лев и пингвин, то есть семь способов выбрать трех животных:

1) первый медведь, тигр и лев;

2) первый медведь, тигр и пингвин;

3) первый медведь, лев и пингвин;

4) второй медведь, тигр и лев;

5) второй медведь, тигр и пингвин;

6) второй медведь, лев и пингвин;

7) тигр, лев и пингвин.

Входные данные

В первой строке входного файла содержится натуральное число \(n\) – количество видов животных в городском зоопарке (1 ≤ \(n\) ≤ \(10^5\)).

В каждой из следующих \(n\) строк содержится одно натуральное число – количество животных соответствующего вида. Общее число животных в зоопарке не превышает \(10^5\).

Выходные данные

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

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные

27000000000000

#1849

Плитки

Темы: [Динамическое программирование по профилю] ["Длинная" арифметика]

Источники: [ Командные олимпиады, ВКОШП, 1999, Задача D ]

У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1×1. Он выбирает ровно N плиток и выкладывает их в полоску. Например, при N = 10 она может выглядеть следующим образом:

К

С

З

К

З

К

С

(Буквой К обозначена красная плитка, С – синяя, З – зеленая)

После этого Петя заполняет следующую таблицу:

	красный	синий	зеленый
красный	Y	Y	Y
синий	Y	N	Y
зеленый	Y	Y	N

В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает "Y", если в его полоске найдется место, где рядом лежат плитки цветов А и Б и "N" в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали – если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски.

Так, данная таблица представляет собой диаграмму смежности приведенной выше полоски.

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

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

С

К

З

К

З

С

К

не совпадает с полоской, приведенной в начале условия.)

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

Первая строка входного файла содержит число N. (1  N  100). Следующие три строки входного файла, содержащие по три символа из набора {"Y", "N"}, соответствуют трем строкам диаграммы смежности. Других символов, включая пробелы, во входном файле не содержится. Входные данные корректны, т.е. диаграмма смежности симметрична.

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

Выведите в выходной файл количество полосок длины N, имеющих приведенную во входном файле диаграмму смежности.

Примеры

Входные данные

Выходные данные

10

YYY

YNY

YYN

4596

3

YYY

0

#2512

Поедание сыра

Темы: [Потоки]

Источники: [ Командные олимпиады, ВКОШП, 2009, Задача A ]

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

Всего на заводе живет \(m\) мышей. Для \(i\)-й мыши известна ее скорость поедания сыра \(s_i\), мышь может съесть \(s_i\) грамм сыра в час.

Недавно мышам стал известен план работы завода на ближайшее время. Планируется изготовить \(n\) головок сыра. Про каждую головку известны \(r_i\) к началу какого часа она будет изготовлена, \(d_i\) в начале какого часа она начнет портиться, и \(p_i\) вес головки сыра в граммах.

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

Мыши не любят есть сыр после того как он начал портиться. Но оставлять сыр недоеденным мыши не могут. Они решили организовать поедание сыра таким образом, чтобы величина \(t\), такая что какую-либо головку все еще продолжают есть через \(t\) часов после того как она начала портиться, была минимальна. Помогите мышам выяснить, как это сделать.

Входные данные

Первая строка входного файла содержит два целых числа \(n\) и \(m\) (\(1 \le n \le 30\), \(1 \le m \le 30\)). Следующие \(n\) строк содержит по три целых числа: \(p_i\), \(r_i\) и \(d_i\) (\(1 \le p_i \le 10^5\), \(0 \le r_i \lt d_i \le 10^7\)). Далее следуют \(m\) строк, каждая из которых содержит по одному целому числу \(s_j\) (\(1 \le s_j \le 10^5\)).

Выходные данные

Выведите одно вещественное число — искомое минимальное \(t\). Ваш ответ должен отличаться от правильного не больше чем на \(10^{-4}\).

Комментарий к примеру тестов

В первом примере мышам следует организовать поедание сыра следующим образом. Сначала первая мышь начинает есть первую головку сыра. Когда появляется вторая головка, она перестает есть первую и начинает есть вторую (в этот момент от первой осталось 9 граммов). Вторая мышь принимается есть первую головку сыра. Через 2.5 часа первая мышь доедает вторую головку сыра (на 0.5 часа позже чем она начала портиться) и снова начинает есть первую (вторая мышь за это время съела еще 5 граммов от первой головки и от нее осталось 4 грамма). Таким образом еще за час первая мышь доедает первую головку, также на 0.5 часа позже чем она начала портиться.

Во втором примере мышь успевает съесть сыр до того как он начинает портиться

Примеры

Входные данные

Выходные данные

0.5

Входные данные

1 1
1 0 1
1

Выходные данные

0.0

#2513

Соревнования по программированию

Темы: [Алгоритмы на строках]

Источники: [ Командные олимпиады, ВКОШП, 2009, Задача B ]

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

Пара файлов называется тестом, если они находятся в одном каталоге и имеют полные имена вида «XY» и «XY.a», где «XY» — номер теста (дополненный ведущим нулем, если он меньше десяти). В первом из указанных файлов хранятся входные данные, а во втором — эталонный ответ.

Каталог называется каталогом с тестами, если в нем есть тесты со всеми номерами от \(1\) до \(N\), где \(1 \le N \le 99\), а других файлов нет (но могут быть подкаталоги).

Каталог называется задачей, если в нем есть файл с именем «check» и любым (возможно пустым) расширением и подкаталог «tests», который является каталогом с тестами. В каталоге-задаче помимо этого могут быть другие файлы и подкаталоги.

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

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

Входные данные

Первая строка входного файла содержит \(n\) — число файлов (\(1 \le n \le 1000\)). Каждая из последующих \(n\) строк содержит полный путь к файлу. Каждая из этих строк содержит от одного до 200 символов.

Элементы пути разделены символами «\». В начале элемента пути идет буква диска (от «A» до «Z»), затем следует двоеточие, затем «\». Имена каталогов в пути и имена файлов состоят из символов с кодами от 33 до 126, за исключением символа «\». Последний элемент пути является полным именем файла. Полное имя файла содержит не более одной точки, при этом до и после точки идет хотя бы один символ. Если имя файла содержит точку, то часть имени после точки называется расширением, а часть до точки — именем файла. Иначе считается, что файл имеет пустое расширение, а имя файла совпадает с его полным именем.

Строчные и заглавные буквы в путях не различаются. Ни в каком каталоге нет файла и подкаталога, имеющих одинаковые имена.

Выходные данные

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

Примеры

Входные данные

22
C:\olymp\roi2005\aplusb\tests\01
C:\olymp\roi2005\aplusb\tests\01.a
C:\olymp\roi2005\aplusb\tests\02
C:\olymp\roi2005\aplusb\tests\02.a
C:\olymp\roi2005\aplusb\check.exe
C:\olymp\roi2005\gcd\tests\01
C:\olymp\roi2005\gcd\tests\01.a
C:\olymp\roi2005\gcd\tests\02
C:\olymp\roi2005\gcd\tests\02.a
C:\olymp\roi2005\gcd\check.cpp
C:\olymp\roi2005\gcd\solution.exe
C:\olymp\roi2006\aplusb\tests\01
C:\olymp\roi2006\aplusb\tests\01.a
C:\olymp\roi2006\aplusb\tests\03
C:\olymp\roi2006\aplusb\tests\03.a
C:\olymp\roi2006\aplusb\check.exe
C:\olymp\roi2006\gcd\tests\01
C:\olymp\roi2006\gcd\tests\01.a
C:\olymp\roi2006\gcd\tests\03
C:\olymp\roi2006\gcd\tests\02.a
C:\olymp\roi2006\gcd\check.cpp
C:\olymp\roi2006\gcd\solution.exe

Выходные данные

#2514

Адронные коллайдеры

Темы: [Вычислительная геометрия]

Источники: [ Командные олимпиады, ВКОШП, 2009, Задача E ]

Две страны Байтландия и Флатландия решили объединить свои усилия в исследованиях в области физики высоких энергий и построили \(n\) адронных коллайдеров. Каждый коллайдер имеет форму кольца и находится под землей. При этом можно считать, что толщина каждого из коллайдеров пренебрежимо мала — их можно считать окружностями.

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

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

Входные данные

Первая строка входного файла содержит целое число \(n\) (\(1 \le n \le 3\)). Каждая из последующих \(n\) строк содержит описание одного из коллайдеров. Описание коллайдера состоит из трех целых чисел: \(x\), \(y\), \(r\) — координат центра коллайдера и его радиуса (\(|x|\), \(|y|\) \(\le 1000\), \(1\) \(\le r\) \(\le 1000\)). Коллайдеры не имеют общих точек, не лежат один внутри другого, а их центры (если \(n = 3\)) не находятся на одной прямой.

Выходные данные

В первой строке выходного файла описание искомой границы: координаты центра окружности и радиус. Выводите как можно больше знаков после десятичной точки. При проверке правильности ответа, погрешности, не превышающие \(10^{-5}\), будут игнорироваться.

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

Примеры

Входные данные

2
2 0 1
-2 0 1

Выходные данные

0.0 0.0 2.23606797749979

Входные данные

Выходные данные

5.4 4.85 7.52877812131557