Задачи |
A - Спички |
B - Привет, Пирог! |
C - Так Вы хотите стать 2^n-эром? |
D - Игра в дурака |
E - Юстас-Алексу |
F - Маршрутное такси |
G - Удаление дорог |
H - Частые значения |
I - Это убийство! |
J - Степени двойки |
A - Спички
Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости n квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами – сами спички.
Напишите программу, которая по количеству квадратов n, которое необходимо составить, находит минимальное необходимое для этого количество спичек.
Входные данные
Одно целое число n (1 ≤ n ≤ 109).
Выходные данные
Вывести минимальное количество спичек, требуемых для составления n квадратов.
Пример входных данных
4
Пример выходных данных
12
B - Привет, Пирог!
Пиццерия Pizazz гордится тем, что она доставляет пиццу своим покупателям как можно быстрее. К несчастью, для доставки может быть нанят только один водитель. Перед развозкой он ждет, пока не поступит определенное количество заказов (от 1 до 20). Водитель предпочитает выбрать для развозки всех заказов самый быстрый путь, даже если придется проезжать несколько раз одно и то же место, включая пиццерию. В конце развозки водитель обязан вернуться в исходное место, то есть в пиццерию. Вам необходимо написать программу, которая выберет такой маршрут.
Входные данные
В первой строке находится количество заказов n (1 ≤ n ≤ 20). Далее следует n + 1 строка, каждая из которых содержит n + 1 целое число. Эти числа указывают на время проезда между пиццерией (ее номер 0) и n местами, где находятся заказы (они пронумерованы числами от 1 до n). j-ое значение i-ой строки указывает на время, за которое можно проехать напрямую из места i в место j, не посещая по пути никаких других мест. Заметим, что проезд между i и j может быть быстрее не напрямую, а через другие места из-за пробок на дорогах и присутствия светофоров. Время проезда не симметрично. То есть время, за которое можно напрямую проехать из i в j, не всегда совпадает с временем проезда напрямую из j в i.
Выходные данные
Вывести одно число – наименьшее время, за которое можно развести пиццу всем заказчикам и вернуться обратно в пиццерию.
Пример входных данных
3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
Пример выходных данных
8
C - Так Вы хотите стать 2^n-эром?
У игрока имеется $1, и ему предстоит последовательно ответить на n вопросов. Перед каждым вопросом он может:
· остановить игру и забрать имеющиеся у него деньги.
· ответить на вопрос. Если ответ неправильный, он покидает игру ни с чем. Если ответ правильный, то денежная сумма удваивается, и игра переходит к следующему вопросу.
Ответив на последний вопрос, игрок забирает деньги. Игрок желает максимизировать ожидаемую сумму выигрыша.
На каждый заданный вопрос игрок может ответить правильно с вероятностью p. Считайте, что вероятность p равномерно распределена на отрезке t .. 1.
Входные данные
Каждая строка является отдельным тестом и содержит два числа: целое значение n (1 ≤ n ≤ 30) и действительное t (0 ≤ t ≤ 1). Последняя строка содержит 0 0 и не обрабатывается.
Выходные данные
Для каждой пары чисел n и t вывести в отдельной строке максимальную ожидаемую сумму выигрыша, если известно, что игрок придерживается наилучшей стратегии. Результат следует выводить с тремя десятичными знаками.
Пример входных данных
1 0.5
1 0.3
2 0.6
24 0.25
0 0
Пример выходных данных
1.500
1.357
2.560
230.138
D - Игра в дурака
Проказница мартышка, осел, козел и косолапый мишка затеяли сыграть в дурака. Как известно, в первой партии начинает ходить тот, у кого козырь самого маленького достоинства. Поэтому после раздачи карт все четверо одновременно называют достоинство наименьшего козыря, который у них оказался, а именно каждый говорит вслух число от 6 до 14 или 0 (числа больше 10 соответствуют картинкам: валету, даме, королю и тузу, ноль - отсутствию козырей).
Вам известно, какие числа были произнесены. Определите количество гарантированно совравших в этой компании.
В игре используется колода из 36 карт - по 9 карт каждой из 4 мастей. Каждому игроку раздаётся по 6 карт, следующая карта из колоды открывается, и её масть устанавливает козырь для данной игры.
Входные данные
Четыре целых числа, которые назвали игроки. Числа разделены пробелами. Каждое из чисел - это либо 0, либо число от 6 до 14.
Выходные данные
Выведите минимальное количество совравших игроков.
Пример входных данных1
10 7 11 0
Пример выходных данных1
0
Пример входных данных2
6 10 10 11
Пример выходных данных2
1
E - Юстас-Алексу
После блестяще проведенной операции Штирлиц смог определить численность фашистской армии. Естественно такую информацию уже четыре года как ждут в штабе советской армии. Чтобы общаться со штабом Штирлиц использует n радистов. Каждый из радистов должен передать сообщение от Штирлица в штаб. Штирлиц, как хитрый разведчик, зашифровал свое послание таким образом: каждому из радистов он дал одно и то же число - численность армии, но в своей системе счисления, да еще так, что все основания систем счисления у радистов попарно взаимно простые. После передачи радиограммы ищейки Мюллера смогли определить последний символ каждого из сообщений. Вы работаете штатным программистом и должны определить, какое минимальное число мог послать Штирлиц в своем сообщении. Мюллер в отличие от вас не очень любит бинарный код, поэтому он хочет, чтобы искомое число вы вывели в десятичной системе.
Входные данные
В первой строке задается число n - количество радистов у Штирлица. В следующей строке находятся n чисел ai - основания систем счисления, в которых Штирлиц давал сообщения радистам (2 ≤ ai ≤ 36 ). В третьей строке через пробел записано n символов ci - последние буквы каждого из сообщений (0 ≤ ci < ai; ci - либо цифра от 0 до 9, либо буква от A до Z).
Выходные данные
Вывести минимальное число, которое мог передать Штирлиц в десятичной системе счисления.
Пример входных данных
2
6 13
1 B
Пример выходных данных
37
F - Маршрутное такси
В час пик на остановку одновременно подъехали три маршрутных такси, следующие по одному маршруту, в которые тут же набились пассажиры. Водители обнаружили, что количество людей в разных маршрутках разное, и решили пересадить часть пассажиров так, чтобы в каждой маршрутке было поровну пассажиров. Требуется определить, какое наименьшее количество пассажиров придется при этом пересадить.
Входные данные
Три натуральных числа, не превосходящих 100 - количества пассажиров в первой, второй и третьей маршрутках соответственно.
Выходные данные
Выведите наименьшее количество пассажиров, которое требуется пересадить. Если это невозможно, выведите слово "IMPOSSIBLE".
Пример входных данных1
1 2 3
Пример выходных данных1
1
Пример входных данных2
99 100 100
Пример выходных данных2
IMPOSSIBLE
G - Удаление дорог
Имеется сеть из n городов и m двунаправленных дорог, соединяющих эти города. Первые k городов считаются важными. Вам необходимо так удалить наименьшее количество дорог, чтобы в оставшейся сети не было циклов, проходящих через важные города. Цикл представляет собой последовательность по крайней мере трех таких разных городов, что каждая пара соседних городов связана между собой дорогой, а первый и последний город также соединены дорогой.
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 20). Каждый тест начинается строкой, содержащей три целых числа n, m и k (1 ≤ n ≤ 10000, 1 ≤ m ≤ 50000, 1 ≤ k ≤ n) - количество городов, дорог и важных городов соответственно. Города пронумерованы числами от 0 до n - 1, а важные города пронумерованы числами от 0 до k - 1. Каждая из следующих m строк содержит два целых числа ai и bi, 0 ≤ i < m, описывающих номера разных городов, соединенных дорогой.
Известно, что 0 ≤ ai, bi < n и ai ≠ bi. Между двумя городами существует не более одной дороги.
Выходные данные
Для каждого теста, пронумерованного числами от 1 до t, вывести строку "Case #i: ", за которой следует целое число - наименьшее количество дорог, подлежащих удалению таким образом, чтобы не осталось ни одного цикла, в который входил хотя бы один важный город.
Пример
В первом примере имеется n = 5 городов и m = 7 дорог, города 0 и 1 являются важными. Можно удалить дороги (0, 1) и (1, 2), после чего оставшаяся сеть не будет содержать циклов, содержащих важные города. Отметим, что в оставшейся сети присутствует цикл, проходящий через неважные города. Для выполнения требования задачи существует несколько способов удаления двух ребер. Удалением одного ребра нельзя уничтожить все циклы, проходящие через важные города.
Пример входных данных
2
5 7 2
0 1
1 2
1 4
0 2
2 4
2 3
3 4
8 12 2
0 2
0 4
0 5
2 3
2 7
3 1
3 4
4 6
5 6
5 7
6 1
7 1
Пример выходных данных
Case #1: 2
Case #2: 4
H - Частые значения
Задана последовательность n целых чисел a1 , a2 , ... , an в неубывающем порядке. Вам также заданы несколько запросов, состоящих из индексов i и j (1 ≤ i ≤ j ≤ n). Для каждого запроса определите число, которое чаще всего встречается среди ai, ... , aj.
Входные данные
Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два целых числа n и q (1 ≤ n, q ≤ 100000). Следующая строка содержит n целых чисел a1 , ... , an (-100000 ≤ ai ≤ 100000, для каждого i ∈ {1, ..., n}), разделенных пробелом. Считайте, что для каждого i ∈ {1, ..., n - 1}: ai ≤ ai + 1. Каждая из следующих q строк содержит один запрос, состоящий из двух целых значений i и j (1 ≤ i ≤ j ≤ n) - границы индексов запроса.
За последним тестом следует строка, содержащая один 0.
Выходные данные
Для каждого запроса выведите одно целое число: количество вхождений чаще всего встречаемого числа в заданном интервале.
Пример входных данных
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
Пример выходных данных
1
4
3
I - Это убийство!
Однажды детектив Сайкат расследовал дело об убийстве. На месте преступления он обнаружил лестницу, на каждой ступеньке которой было написано одно число. Он нашел это подозрительным и решил запоминать все пройденные числа. Помня пройденные числа, он обнаружил в них закономерность. Детектив решил для каждого числа на лестнице записать сумму всех чисел, которые он ранее наблюдал на лестнице, и которые меньше записанного на текущей ступеньке. Найти сумму всех чисел, записанных в дневнике детектива.
Входные данные
Первая строка содержит количество тестов t (t ≤ 10). Далее следуют 2t строк. Первая строка задает количество ступенек n (1 ≤ n ≤ 105). Следующая строка содержит n чисел, записанных на ступеньках. Все записанные числа изменяются от 0 до 106.
Выходные данные
Для каждого теста вывести в отдельной строке итоговую сумму.
Пример входных данных
1
5
1 5 3 6 4
Пример выходных данных
15
J - Степени двойки
Ни для кого не секрет, что число 2n при любом целом неотрицательном n в двоичной системе счисления имеет очень простой вид - в старшем разряде стоит единица, а затем следует n нулей. В десятичной системе счисления эти числа не столь однообразны, однако и среди них встречаются те, которые начинаются с единицы.
Вычислите, сколько таких чисел в заданном диапазоне.
Входные данные
Два целых числа n1 и n2 (0 ≤ n1 < n2 ≤ 109), разделенные пробелом.
Выходные данные
Вывести количество чисел, являющихся степенями двойки и принадлежащих отрезку [2n1; 2n2], у которых в десятичной системе счисления в старшем разряде стоит единица.
Пример входных данных
0 10
Пример выходных данных
4
