Olymp8
.pdfКружок «Олимпиадное программирование» 10 декабря
Григорьева Анастасия Викторовна
nastya001@mail.ru
Мат-мех
2015
Что будет сегодня?
Районный тур ВОШ-2015
Разбор ДЗ
Игры и стратегии
Задачи про игры
Мат-мех 2015 |
2 |
Районный тур ВОШ
|
|
|
|
Мат-мех 2015 |
3 |
Районный тур ВОШ
Олимпиада по информатике будет проходить 14.12 в ФМЛ 30 по адресу 7-я
линия ВО, д.52
Начало регистрации в 12.00 в 12.30 начало олимпиады
Мат-мех 2015 |
4 |
Разбор ДЗ
Сверим часы
Реклама Заполни массив 1, 2
Псевдопростые числа
Степень
Мат-мех 2015 |
5 |
Сверим часы
(На перебор)
Ограничение по времени, сек 3 Ограничение по памяти, мегабайт 64
В компании MacroHard в последнее время резко участились опоздания сотрудников. Проанализировав ситуацию, руководство решило, что это вызвано большим разбросом в показаниях наручных часов сотрудников. После дополнительного совещания руководящего состава было постановлено, что все сотрудники должны перевести часы на одно и то же время (не важно какое).
6
Сверим часы
Все сотрудники компании носят исключительно электронные часы одного образца. Время на них отображается в формате HH:MM:SS (где HH — часы, MM — минуты, SS
— секунды, всегда отображаются в виде двух цифр, 00≤HH≤23, 00≤MM≤59, 00≤SS≤59). Перевод часов осуществляется с помощью двух кнопок. Первая кнопка меняет поле редактирования следующим образом: после первого нажатия часы переходят из режима отображения времени в режим редактирования поля HH, после второго — в режим редактирования поля MM, после третьего — в режим редактирования поля SS, а после четвертого возвращаются в режим отображения времени и т.д. по циклу. При переполнении секунд поле SS обнуляется, а MM увеличивается на единицу, при переполнении минут поле MM обнуляется, а HH увеличивается на единицу, а при переполнении часов просто обнуляется поле HH.
И все бы хорошо, но, в силу своей природной лени, сотрудники хотят минимизировать суммарное число нажатий кнопок при переводе часов. При этом после перевода часов все часы должны оказаться в режиме отображения времени, в начале все часы также находятся в этом режиме.
Напишите программу, определяющую минимальное суммарное количество нажатий кнопок, достаточное для перевода часов всеми сотрудниками к одному времени.
входные данные
2
08:01:01
07:59:00
Мат-мех 2015 |
выходные данные |
7 |
|
7 |
|
Решение
86 400 сек в сутках
=> 86 400 вариантов правильного ответа
Переберем все и найдем тот, для которого общее кол-во нажатий наименьшее
Функция, возвращающая кол-во нажатий чтобы
h1:m1:s1 => h2:m2:s2
Если равно, то 0
Иначе 4 раза нажать первую (перевести в режим редактирования ч,м,с, вернуться)
А на вторую?
s1-s, если s1>= s, или s1-s+60 иначе (m++ не забыть тогда)
Аналогично с мин и часами
Теперь осталось считать данные и для каждого возможного времени на дисплее часов посчитать количесто операций, необходимых для того чтобы установить это время на всех часах. Среди всех полученных значений выбрать наименьшее
Мат-мех 2015 |
8 |
Реклама
(На сортировку)
Ограничение по времени, сек 1 Ограничение по памяти, мегабайт 64
В супермаркете решили время от времени транслировать рекламу новых товаров. Для того, чтобы составить оптимальное расписание трансляции рекламы, руководство супермаркета провело следующее исследование: в течение дня для каждого покупателя, посетившего супермаркет, было зафиксировано время, когда он пришел в супермаркет, и когда он из него ушел.
Менеджер по рекламе предположил, что такое расписание прихода-ухода покупателей сохранится и в последующие дни. Он хочет составить расписание трансляции рекламных роликов, чтобы каждый покупатель услышал не меньше двух рекламных объявлений. В тоже время он выдвинул условие, чтобы два рекламных объявления не транслировались одновременно и, поскольку продавцам все время приходится выслушивать эту рекламу, общее число рекламных объявлений за день было
минимальным. |
Мат-мех 2015 |
9 |
Реклама
Напишите программу, которая составит такое расписание трансляции рекламных роликов. Рекламные объявления можно начинать транслировать только в целые моменты времени. Считается, что каждое рекламное объявление заканчивается до наступления следующего целого момента времени. Если рекламное объявление транслируется в тот момент времени, когда покупатель входит в супермаркет или уходит из него, покупатель это объявление услышать успевает.
Входные данные
Во входном файле записано сначала число N — количество покупателей, посетивших супермаркет за день(1<=N<=3000). Затем идет N пар натуральных чисел Ai, Bi, задающих соответственно время прихода и время ухода покупателей из супермаркета (0
Выходные данные В выходной файл выведите сначала количество
рекламных объявлений, которое будет протранслировано за день. Затем выведите в возрастающем порядке моменты времени, в которые нужно транслировать рекламные объявления.
Если решений несколько, выведите любое из них.
Мат-мех 2015
входные данные |
|
5 |
|
1 10 |
|
10 12 |
|
1 10 |
|
1 10 |
|
23 24 |
|
выходные данные |
|
5 |
|
5 10 12 23 24 |
10 |
|