Страница: << 34 35 36 37 38 39 40 >> Отображать по:

#112698

Соцопрос

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2014, Лига Б, Задача C ]

Мэр уездного города $\text{[math]}$ заботится о жителях и прислушивается к их мнению, поэтому он ежегодно даёт поручение социологической комиссии провести опрос общественного мнения. Участникам опроса предлагается M вопросов, i -й из которых содержит целое положительное количество вариантов ответа a _i . Жители города крайне серьёзно относятся к данному опросу, поэтому заполняют анкету добросовестно: каждый участник опроса выбирает ровно один вариант ответа в каждом вопросе.

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

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

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

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

В первой строке находится одно целое число K ( 1 ≤ K ≤ 100 ) "— количество чисел, записанных Жанной на полях тетради, совпадающее с суммарным количеством вариантов ответа на все вопросы.

Во второй строке записаны K неотрицательных целых чисел от 0 до 100, разделённых пробелами, каждое из которых обозначает процент жителей, проголосовавших за какой-то вариант ответа на какой-то вопрос.

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

Выведите единственное число M "— количество вопросов в социологическом опросе. Гарантируется, что существует ответ, удовлетворяющий записям из тетради Жанны. Если определить количество вопросов однозначно не удаётся, выведите любое подходящее значение.

Примечание

В приведённом примере существует единственный способ получить подходящее разбиение: первое и третье число представляют ответы на один вопрос, а второе и четвёртое "— на другой.

Примеры

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

4
25 50 75 50

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

#112699

Маленькое новоселье

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2014, Лига Б, Задача D ]

Ситуация с землёй в столице одной малоизвестной страны приближается к катастрофической. Уже практически невозможно найти даже небольшой клочок земли для постройки своего жилища.

Тем не менее Фёдору повезло: после прохождения многочисленных инстанций он всё-таки нашел место для нового дома. Более того, щедрое правительство даже подарило ему невероятно красивую крышу для постройки.

Важным обстоятельством является то, что Федя — совершенно плоский, как и весь мир, который его окружает. В этом плоском мире введена стандартная декартова система координат: ось $O_x$ совпадает с землёй, а ось $O_y$ направлена от земли вверх. Крыша представляет собой два отрезка, исходящих из одной точки (вершины крыши) вниз в разные стороны, причём оба отрезка составляют угол 45 градусов с осью $O_x$:.

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

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

В первой строке содержатся два целых числа $x_c$ и $y_c$ — координаты вершины крыши (|$x_c$| <= $10^4$, 1 <= $y_c$ <= $10^4$).

Во второй строке содержатся два целых числа $x_1$ и $y_1$ — координаты одного из концов крыши (|$x_1$| <= $10^4$, $x_1$ ̸= $x_c$, 0 <= $y_1$ < $y_c$). В следующей строке в таком же формате заданы координаты $x_2$ и $y_2$ другого конца крыши.

Гарантируется, что отрезки, образующие крышу, направлены в разные стороны относительно верхней точки крыши, т. е. либо $x_1$ < $x_c$ < $x_2$, либо $x_2$ < $x_c$ < $x_1$, оба отрезка имеют одинаковую длину и составляют угол 45 градусов с осью $O_x$.

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

Выведите единственное число — искомую максимальную площадь дома. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10^-6

А именно, пусть ваш ответ равен $A$, а ответ жюри — $B$. Проверяющая программа будет считать ваш ответ правильным, если |$A$-$B$| / max($1$; $B$) <= 10^-6.

Примеры

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

10 10
5 5
15 5

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

50.0

#112700

Здоровый сон

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2014, Лига Б, Задача E ]

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

Старые электронные часы в комнате Глеба показывают количество часов от 0 до 11 и количество минут от 0 до 59, а индикатор, отвечающий за время суток, давно сломался. Глеб помнит, что перед тем, как он в прошлый раз заснул, часы показывали ровно t _start часов (то есть t _start часов 0 минут). Когда же он проснулся, на часах было ровно t _finish часов. Глеб абсолютно уверен, что спал не менее одного часа, но хотел бы знать точнее. Помогите ему определить минимальное количество часов, которое он мог проспать.

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

В первой строке содержится целое число t _start ( 0 ≤ t _start ≤ 11 ) "— время на часах, когда Глеб лёг спать. Во второй строке содержится целое число t _finish ( 0 ≤ t _finish ≤ 11 ) "— время на часах, когда Глеб проснулся.

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

В единственной строке выведите одно целое число — минимальное количество часов, которое мог проспать Глеб.

Примеры

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

7
11

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

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

10
1

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

#112701

Средиземье в опасности

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2014, Лига Б, Задача F ]

Тёмные силы под руководством Саурона заполонили Средиземье, и только Арагорн, сын Араторна, наследник Исилдура и истинный правитель Гондора может найти силы противостоять Тёмному владыке Мордора. Впрочем, мы поможем ему в этом в другой раз, сейчас же давайте оценим, как далеко может зайти Тёмный Властелин.

Карта Средиземья представляет собой клетчатый прямоугольник из N строк по M клеток, каждая из которых может либо полностью принадлежать Саурону, либо полностью не принадлежать. Если в каком-либо квадрате размером 2 × 2 три клетки уже захвачены тёмными силами, то они способны захватить и четвёртую клетку.

Изначально полчищам Саурона уже подвластны некоторые клетки на карте Средиземья. Оцените, сколько клеток может оказаться под его контролем в худшем случае.

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

Первая строка входного файла содержит два целых числа N и M ( 1 ≤ N , M ≤ 40 ) — количество строк и столбцов на карте Средиземья. Следующие N строк по M символов описывают игровое поле в порядке следования сверху вниз, слева направо. Символ ‘ . ’ соответствует клетке карты, свободной от власти Саурона, а ‘ # ’ — клетке, захваченной Сауроном. Строки нумеруются от 1 до N , столбцы — от 1 до M .

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

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

Примеры

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

2 2
##
#.

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

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

3 4
#...
#...
###.

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

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

3 5
...##
#....
#.#..

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

#112702

Турбулентность

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2014, Лига Б, Задача G ]

Миша решил развлечься в свободное от решения задач время и сейчас проходит квест «Турбулентность». Задание квеста заключается в том, что Мише нужно добыть статуэтку золотого кота. Миша уже добрался до сейфа, в котором предположительно находится статуэтка, и ему осталось лишь подобрать код от замка.

Сообщник Миши оставил ему послание со словом, состоящим из строчных букв латинского алфавита. По опыту предыдущих квестов Миша догадался, что код — это слово минимальной длины, которое не является подстрокой переданного сообщником слова и состоит только из строчных букв латинского алфавита.

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

Напомним, что подстрокой называется некоторая непрерывная часть строки. К примеру, подстроками строки abacaba являются aba, bacab, a и многие другие

Напомним также, что лексикографическое сравнение строк соответствует упорядочиванию слов в словаре, а именно, сначала идут все слова, начинающиеся на букву a, затем слова, начинающиеся на букву b, и так до конца алфавита. Если у каких-то двух слов первые буквы совпадают, то они сравниваются по второй букве. В случае повторного равенства следует сравнить третью букву и так далее. К примеру, слово game лексикографически меньше слова gate, так как первые две буквы у них совпадают, а третья идет по алфавиту раньше.

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

В первой строке содержится единственное целое число $N$ — длина переданного сообщником слова (1 <= N <= 100).

Во второй строке содержится переданное сообщником слово.

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

Выведите строку, которую Миша хочет попробовать в качестве кода от сейфа

Примеры

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

9
pascalabc

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

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

28
aabcdefghijklmnopqrstuvwxyzz

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

ac

Страница: << 34 35 36 37 38 39 40 >> Отображать по:

Выбрано

Отменить

Добавить в контест