Задача A. Мы делили... ≡

Условие

На день рождения пришли N гостей. Праздничный торт разделили между всеми гостями поровну. После этого неожиданно явились ещё K гостей.

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

Ответ вывести в виде несократимой обыкновенной дроби A / B.

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

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

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

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

Ограничения

1 ≤ N, K ≤ 10⁴

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

1 3

3 4

3 9

1 4

Задача B. Минимальный лабиринт ≡

Условие

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

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

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

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

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

Первая строка входного файла содержит два целых числа — N M.

Далее идут N строк по M символов, описывающие лабиринт:

• # (ASCII 35) — обозначает блок
• . (ASCII 46) — обозначает пустое место

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

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

Ограничения

1 ≤ N, M ≤ 100

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

3 7
......#
.#..#.#
....#..

......#
.#..#.#
....#..

3 8
##.#..##
##.#.###
...#.##.

.#.#..#.
##.#.#.#
...#.##.

Задача C. Марсианский заголовок ≡

Условие

Марсианский журнал решил опубликовать статью о жизни на других планетах. Статья представляет собой строку из заглавных и строчных латинских букв. Пробелы и знаки препинания на Марсе не используют.

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

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

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

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

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

Первая строка входного файла содержит целое число M.

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

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

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

Ограничения

1 ≤ M ≤ 99

Длина текста составляет от 2 до 5000 символов.

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

50
aAb

aA

30
xxxxXXxxX

xxxxXXx

99
ab

a

Задача D. Марсианский монитор ≡

Условие

Марсианский институт разработал новую модель черно-белого компьютерного монитора с разрешением W пикселей по горизонтали и H пикселей по вертикали.

Новый монитор очень дёшев в производстве, но имеет один конструктивный недостаток — если какой-либо из пикселей стал белым, то все пиксели, находящиеся на расстоянии, меньшем или равном L, белыми стать уже не могут. (Расстояние между пикселями c координатами (x₁, y₁) и (x₂, y₂) считается по обычной формуле — √(x₁ − x₂)² + (y₁ − y₂)²).

На монитор, первоначально полностью чёрный, последовательно выводится N белых пикселей. Определите, какие из этих пикселей фактически станут белыми.

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

Входной файла целые числа N W H L.

Далее идут N пар целых чисел X_i Y_i — координаты i-го выводимого пикселя.

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

Выходной файл должен содержать целое число M — количество отображённых пикселей. Далее должны идти M целых чисел a_j — порядковые номера отображённых пикселей, в возрастающем порядке. Пиксели нумеруются с единицы.

Ограничения

1 ≤ N ≤ 5 × 10⁴

1 ≤ X_i ≤ W ≤ 2560

1 ≤ Y_i ≤ H ≤ 2048

0 ≤ L ≤ 25

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

3 10 10 2
1 1  1 3  3 2

2
1 3

8 13 9 3
1 1  2 1  3 3  3 6  7 3  6 3  7 7  7 6

4
1 4 5 7

Задача E. Марсианский тир ≡

Условие

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

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

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

Входной файл содержит целое число N, за которым идут N блоков, описывающих серии выстрелов. Серия номер i задаётся числом K_i — количеством закрашиваемых отрезков, за которым следуют K_i пар чисел L_{i, j} R_{i, j}, задающих левую и правую границу очередного отрезка; затем S_i — количество выстрелов в i-ой серии, и наконец S_i чисел P_{i, j}, задающих координаты попаданий.

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

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

Ограничения

1 ≤ N ≤ 100

0 ≤ K_i ≤ 1000

0 ≤ S_i ≤ 10⁴

0 ≤ L_{i, j} ≤ R_{i, j} ≤ 10⁷

0 ≤ P_{i, j} ≤ 10⁷

Все числа во входном файле целые

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

1
4   9 14  4 5  1 2  6 6
5   1 6 3 17 12

3

2
3   10 20  75 100  15 25
4   4 2 16 9
1   23  78
2   13 77

3

Задача F. Марсианская эскадра ≡

Условие

Рядом с Марсом расположена группировка космических кораблей Марсианской школы естественных наук.

Для связи между кораблями решено использовать широкополосную беспроводную сеть Wi-MARS. Чтобы сеть работала, нужно поставить центральный передатчик на один из кораблей. На каком именно корабле? Этот вопрос не так прост: не все корабли хорошо подходят на роль центрального. Марсианские учёные говорят, что радиосигнал затухает на расстоянии, причем это затухание пропорционально квадрату расстояния. А значит, нужно выбрать в некотором смысле геометрически центральный корабль.

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

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

Более формально, по данным координатам (x_i, y_i, z_i) всех N кораблей необходимо вычислить для каждого корабля i величину ∑_j((x_i − x_j)² + (y_i − y_j)² + (z_i − z_j)²).

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

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

В выходной файл следует вывести N чисел — значение штрафа для каждого корабля.

Ограничения

2 ≤ N ≤ 10⁵;

−10⁴ ≤ x_i, y_i, z_i ≤ 10⁴;

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

6
0 0 0
10 0 0 
0 10 0
0 0 10
3 3 3
3 3 3

354
634
634
634
228
228

Задача G. Марсианская простота ≡

Условие

Как известно, земные математики называют простым натуральное число, имеющее ровно два делителя — единицу и само число. Марсианские математики вместо этого используют понятие M-простого числа, которое имеет ровно M делителей. Например, число 6 является 4-простым, так как имеет делители 1, 2, 3, 6. Обыкновенные простые числа являются в этой терминологии 2-простыми.

Для данных N и M требуется определить количество M-простых чисел в диапазоне от 2 до N включительно.

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

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

Ограничения

2 ≤ N ≤ 5 × 10⁶, 2 ≤ M ≤ 10⁴

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

10 5

0

60 12

1

10000 12

1040

Задача H. Московский метрополитен ≡

Условие

Ровно 76 лет назад, 15 мая 1935 года, начал работу московский метрополитен. Первоначально он состоял из 13 станций.

Рассмотрим модель московского метрополитена, как набора из 13 станций, соединенных M туннелями. Никакой туннель не ведет из станции в нее же и никакая пара станций не может быть соединена более чем одним туннелем. Для каждого туннеля i известно t_i — время проезда по нему. Движение поездов в туннелях двустороннее.

Тов. Сидоров находится на станции с номером s. У него выдалось T свободных минут и он решил прокатиться по станциям метрополитена. При этом, он хочет потратить на все переезды ровно T минут и вернуться на станцию s.

Определите, возможно ли это. Если да, то найдите последовательность номеров станций, которые должен посетить тов. Сидоров. Первым и последним числом в последовательности должен быть номер s.

Временем переходов между станциями и ожидания поездов следует пренебречь.

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

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

В первую строку выходного файла выведите слово "YES", если требуемый маршрут существует, и "NO" в противном случае. Если ответ существует, то в следующей строке выведите искомый маршрут. Если ответов несколько, выведите любой из них.

Ограничения

1 ≤ s, u_i, v_i ≤ 13;

1 ≤ T, t_i ≤ 1000;

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

4 6 1
1 2 1
2 3 2
3 4 3
4 1 4

YES
1 2 3 2 1

Задача I. Минимальные затраты на телефон ≡

Условие

Школьник Вася, живущий в Новосибирске, много разговаривает по телефону и часто просит родителей пополнить его счёт. Родители, конечно, недовольны излишним расходом семейного бюджета. После долгого семейного совета был достигнут компромисс.

Васина семья составила список из N покупок, которые необходимо совершить в хронологическом порядке. Каждый день Васин папа может сделать от одной до K покупок — больше не вмещается в любимый семейный автомобиль "Лада Калина". Васин папа педантичен и всегда старается, чтобы на счету его банковской карты была сумма, кратная M. Поэтому каждый день после совершения покупок он перечисляет на баланс Васиного телефона минимальную сумму, необходимую, чтобы остаток на карте стал кратен M.

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

Во втором примере покупки лучше совершать следующим образом: в первый день — 2 покупки, во второй — 3, в третий — 3, в четвёртый — 2.

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

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

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

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

Ограничения

1 ≤ N ≤ 40000

1 ≤ K ≤ 2000

1 ≤ M ≤ 10⁴

1 ≤ C_i ≤ 10⁶

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

2 2 50
122 144

34

10 3 100
22 78 33 33 34 17 18 65 83 17

0