Задача A. Робот, налево! ≡

Условие

В Центре робототехники изобрели робота, который ходит только налево. На вопрос "зачем?" он затрудняется ответить.

Робот занимает одну клеточку и действует по следующему алгоритму.

1. Развернуться влево.
2. Если следующая клеточка не была посещена ранее, то пойти прямо (1). Иначе развернуться вправо и пойти прямо (2).

За шаг вида (1) робот получает 1 очко, за шаг вида (2) — 0 очков. Сколько очков получит робот, сделав N шагов?

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

Входной файл содержит целое число N.

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

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

Ограничения

1 ≤ N ≤ 10⁹

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

1

1

3

3

15

7

Задача B. Робот и асфальт ≡

Условие

Накануне Восточного экономического форума рабочие стали чинить асфальт недалеко от Русского моста. Из асфальта вырезали несколько прямоугольников.

В это время по дороге прогуливался новый робот. Его заинтересовали прямоугольники, и он решил их проанализировать. Робот ввёл на плоскости систему координат так, что стороны всех вырезанных прямоугольников параллельны осям координат, и выделил большой прямоугольник, в который поместились все вырезанные прямоугольники. Затем робот продолжил стороны всех прямоугольников до пересечения со сторонами большого. Сколько всего точек пересечения на сторонах большого прямоугольника?

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

Входной файл содержит целое число N, за которым следуют N+1 четвёрок целых чисел x_{1 i} y_{1 i} x_{2 i} y_{2 i} — координаты левого нижнего и правого верхнего углов i-го прямоугольника соответственно. Прямоугольник с индексом 0 — это большой прямоугольник.

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

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

Ограничения

1 ≤ N ≤ 10

0 ≤ x₁ ≤ x_{1 i} < x_{2 i} ≤ x₂ ≤ 100

0 ≤ y₁ ≤ y_{1 i} < y_{2 i} ≤ y₂ ≤ 100

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

2
0 0  10 6

0 1  4 3
6 2  9 6

15

Задача C. Кальмары ≡

Условие

В море плавают N голодных кальмаров, которые постепенно поедают друг друга. Кальмар считается сытым, если он съел K других кальмаров (сытых или голодных). Какое наибольшее число кальмаров может насытиться?

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

Входной файл содержит целые числа N K.

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

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

Ограничения

1 ≤ N, K ≤ 100

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

30 3

9

Задача D. Моряк и рыбачка ≡

Условие

В песне Олега Газманова "рыбачка и моряк не встретятся никак", а всё из-за того, что они не согласовали своё расписание.

В момент времени t = 0 моряк и рыбачка находятся на берегу моря на острове Русском и прощаются. Потом рыбачка будет перемещаться от берега до дома и обратно, а моряк будет ходить по морю от берега о. Русского до Японии и обратно.

Таким образом, в момент времени t рыбачка находится на расстоянии R(1 − cos pt) от берега, а моряк — на расстоянии M(1 − cos qt) от берега. Через какое время они встретятся?

Считаем, что p, q — рациональные числа, p = a/b, q = c/d (но это не обязательно несократимые дроби).

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

Входной файл содержит натуральные числа a b c d.

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

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

Ограничения

1 ≤ a, b, c, d ≤ 10000

Задача E. Муравейники ≡

Условие

Как-то раз Марфа Геннадьевна пошла в лес по грибы с подружками. Грибники внимательно смотрели под ноги, чтобы не упустить ни одного хорошего гриба. Наклонившись за очередной сыроежкой, Марфа Геннадьевна заметила, что рядом был расположен целый муравьиный город — сеть муравейников, соединённых дорогами.

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

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

Грибники нарисовали схему муравейника и просят вас помочь обработать данные. Напишите программу для ответа на вопрос: какое количество продуктов может находиться в каждом муравейнике, чтобы выполнялись упомянутые закономерности? Количество продуктов в муравейнике с наименьшим количеством продуктов принять равным 1.

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

Входной файл содержит целые числа N M — количество муравейников и количество дорог. Далее следуют M пар целых чисел a_i b_i — номера муравейников, соединённых i-й дорогой. Дороги в этом списке не повторяются, и если в списке есть дорога a_i b_i, то нет дороги b_i a_i.

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

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

Требуется вывести в выходной файл N вещественных чисел p_i — количества продуктов для каждого муравейника с точностью не менее 6 знаков после десятичной точки. Если решений несколько, выведите любое из них.

Ограничения

2 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁵

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

4 5
1 2
2 3
3 1
3 4
2 4

1 1.5 1.5 1

Задача F. Новая формула ≡

Условие

Король Лёха Флатландский ввел в своем королевстве новаторскую форму налогообложения. Он установил дату уплаты налога и постановил, что в течение 14 дней должна быть уплачена вся сумма. А если уплатишь позже, то на налоговый счет будет перечислена только часть этой суммы.

Если платишь на t дней позже установленной даты, то расчетный коэффициент будет равен

G(t) = 1t∫t0g(τ) dτ,

где g(t) = max{AA + max{t − 14, 0}, g_min} — коэффициент, который использовал прежний король, A — период полураспада, g_min — минимальный порог.

Требуется по данным числам A g_min t найти расчетный коэффициент.

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

Входной файл содержит числа A g_min t, здесь A, t — целые числа, g_min — вещественное число.

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

Выходной файл должен содержать расчетный коэффициент с точностью не менее 3 знаков после десятичной точки.

Ограничения

1 ≤ A ≤ 20, 0.1 ≤ g_min ≤ 1, 1 ≤ t ≤ 100

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

7 0.3 14

1

14 0.25 16

0.99183996

14 0.25 31

0.810613

Задача G. Просто посчитать ≡

Условие

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

 — Ты играешь в шашки? У нас есть задача про шашки от авторов "Ханойских башен".

 — Нет, только езжу на них.

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

 — Покажешь дорогу обратно — расскажу, как решить задачу.

По дороге монах выучил наизусть золотые хиты радио "Шансон".

 — Приехали, с тебя 500 рублей.

 — Но у меня нет рублей.

 — Тогда столько же юаней.

 — А как задачу решать?

 — Ну как, берёшь и считаешь...

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

Входной файл содержит целые числа N M и число c, означающее цвет левой верхней клетки. 0 — черная, 1 — белая.

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

Выходной файл должен содержать, сколько раз такой шаблон встречается на шахматной доске.

Ограничения

1 ≤ N, M ≤ 1000

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

8 8 1

14

Задача H. Геннадий Васильевич собирает стол ≡

Условие

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

Всего N видов шурупов x_i, и они характеризуются K признаками. k-й признак i-го шурупа обозначаем через x(k)i.

Задача — выбрать минимальное число M признаков из K так, чтобы, зная значения только M признаков, мы могли назвать i — порядковый номер шурупа.

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

Входной файл содержит целые числа N K, за которыми следуют N последовательностей из K целых чисел x(k)i.

Нет двух одинаковых последовательностей.

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

Выходной файл должен содержать число M — минимальное количество признаков, за которым должно следовать M различных целых чисел от 1 до K в порядке возрастания.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N, K ≤ 10

1 ≤ x(k)i ≤ 10

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

3 2
1 1
1 2
2 3

1
2