Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Olymp8

.pdf
Скачиваний:
35
Добавлен:
21.03.2016
Размер:
1.65 Mб
Скачать

Кружок «Олимпиадное программирование» 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

 

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]