Завершился 1 личный тур Открытого чемпионата СыктГУ по программированию.
Спасибо всем участникам чемпионата и тем, кто его делал и провел: Василию Болгар, Анатолию Кораблеву, а также сотрудникам лаборатории информатики №1, благодаря которым все работало!
Вот результаты:
Участникам было предложено 5 задач. Задачи предложил Кораблев Анатолий. Разбор задач представлен Анатолием здесь, на сайте посвященном спортивному программированию http://sportprog.ru/.
К сожалению по техническим причинам не удалось сделать полноценный фотоальбом.
Вот результаты:
Личный тур СГУ. 14 декабря
|
||||||||||
Турнир завершён!
|
||||||||||
R
|
Участник
|
+
|
T
|
|||||||
1
|
Мальцев Александр
|
КРФМЛИ
|
1
|
1
|
+
|
+
|
4
|
395
|
||
11
|
1:31
|
3:18
|
0:47
|
0:19
|
||||||
2
|
Елькин Максим
|
КРФМЛИ
|
10
|
2
|
+
|
-9
|
3
|
470
|
||
10
|
2:31
|
1:11
|
0:08
|
3:26
|
||||||
3
|
Зиновьева Анна
|
КРФМЛИ
|
-2
|
+
|
+
|
2
|
82
|
|||
11
|
3:25
|
1:01
|
0:21
|
|||||||
4
|
Рябинина Александра
|
КРФМЛИ
|
-8
|
1
|
+
|
2
|
106
|
|||
11
|
3:23
|
1:17
|
0:09
|
|||||||
5
|
Глазкова Екатерина
|
ЛНД
|
+
|
+
|
2
|
115
|
||||
10
|
1:28
|
0:27
|
||||||||
6
|
Дровнин Борис
|
СыктГУ
|
-3
|
1
|
+
|
2
|
145
|
|||
125
|
3:18
|
0:59
|
1:06
|
|||||||
7
|
Щедров Михаил
|
КРФМЛИ
|
-1
|
-1
|
2
|
+
|
2
|
207
|
||
10
|
3:26
|
2:49
|
1:20
|
1:27
|
||||||
8
|
Мишенёв Алексей
|
КРФМЛИ
|
-8
|
-7
|
6
|
+
|
2
|
210
|
||
11
|
3:26
|
1:44
|
1:17
|
0:13
|
||||||
9
|
Куликов Артем
|
ТхЛ
|
3
|
+
|
2
|
261
|
||||
11
|
2:48
|
0:33
|
||||||||
10
|
Виноградов Олег
|
КРФМЛИ
|
5
|
+
|
2
|
291
|
||||
8
|
2:49
|
0:22
|
||||||||
11
|
Юрковский Александр
|
КРФМЛИ
|
+
|
1
|
2
|
308
|
||||
11
|
2:18
|
2:30
|
||||||||
12
|
Лесков Дмитрий
|
СОШ
#25
|
-3
|
2
|
1
|
2
|
463
|
|||
10
|
3:27
|
3:26
|
3:17
|
|||||||
13
|
Галиев Айрат
|
ЛНД
|
-2
|
+
|
1
|
14
|
||||
10
|
2:41
|
0:14
|
||||||||
14
|
Морев Константин
|
ТхЛ
|
-2
|
+
|
1
|
19
|
||||
11
|
2:38
|
0:19
|
||||||||
15
|
Михневич Евгений
|
ЛНД
|
-9
|
+
|
1
|
31
|
||||
9
|
2:44
|
0:31
|
||||||||
16
|
Нафидин Александр
|
СыктГУ
|
+
|
1
|
37
|
|||||
115
|
0:37
|
|||||||||
16
|
КРФМЛИ
|
-1
|
1
|
1
|
37
|
|||||
9
|
1:38
|
0:17
|
||||||||
17
|
Попов Кирилл
|
ТхЛ
|
+
|
1
|
47
|
|||||
11
|
0:47
|
|||||||||
18
|
Коновалов Вадим
|
СыктГУ
|
2
|
1
|
79
|
|||||
149
|
0:39
|
|||||||||
19
|
Белых Евгений
|
СыктГУ
|
-3
|
5
|
1
|
118
|
||||
115
|
1:23
|
0:18
|
||||||||
20
|
Кущ Юрий
|
КЭПИ
|
2
|
1
|
122
|
|||||
26
|
1:22
|
|||||||||
21
|
Сандюк Вадим
|
КЭПИ
|
2
|
1
|
135
|
|||||
26
|
1:35
|
|||||||||
22
|
Мишарин Никита
|
КГПИ
|
-3
|
+
|
1
|
147
|
||||
1515
|
1:09
|
2:27
|
||||||||
23
|
Преловский Игорь
|
СыктГУ
|
-7
|
1
|
1
|
189
|
||||
125
|
3:29
|
2:49
|
||||||||
24
|
Габидуллин Артур
|
ТхЛ
|
3
|
1
|
210
|
|||||
10
|
2:30
|
|||||||||
Хвищук Елизавета
|
СыктГУ
|
-1
|
0
|
0
|
||||||
119
|
2:23
|
|||||||||
СыктГУ
|
-1
|
0
|
0
|
|||||||
119
|
2:38
|
|||||||||
Комаров Павел
|
СыктГУ
|
-1
|
0
|
0
|
||||||
119
|
1:00
|
|||||||||
Калкина Катерина
|
СыктГУ
|
-5
|
0
|
0
|
||||||
119
|
0:40
|
|||||||||
Маслов Мирон
|
КЭПИ
|
-6
|
0
|
0
|
||||||
26
|
3:27
|
|||||||||
Крючкова Марина
|
ТхЛ
|
-2
|
-6
|
0
|
0
|
|||||
10
|
1:34
|
0:59
|
||||||||
Попыток
|
43
|
25
|
44
|
62
|
9
|
|||||
Из них зачтено
|
2
|
1
|
12
|
25
|
0
|
|||||
Не зачтено
|
41
|
24
|
32
|
37
|
9
|
|||||
В протоколе не отражены участники, не сделавшие ни одной
попытки сдать решение.
Участникам было предложено 5 задач. Задачи предложил Кораблев Анатолий. Разбор задач представлен Анатолием здесь, на сайте посвященном спортивному программированию http://sportprog.ru/.
К сожалению по техническим причинам не удалось сделать полноценный фотоальбом.
Задачи чемпионата
А. Дураки и дороги
Ограничение по
памяти: 64М
Ограничение по
времени: выставить относительно авторского решения
В России, как известно, есть две вечных проблемы – дураки и
дороги. И если одну проблему можно устранить катками и асфальтоукладочными
машинам, то, что делать с дураками, никто не знает!
Во время эксплуатации на дорожном полотне образуются колеи и
ямы, и когда идёт дождь, огромное количество воды устремляется на асфальт и
мешает нормальному проезду автомобилей. Однажды проектировщики задумались, а
сколько воды может вместиться в профиль дорожного полотна длиной 1 единица?
Входные данные:
В первой строке входных данных содержится два числа – N и K. N – количество
профилей дорожного полотна, K
– ширина дорожного полотна. В следующих N строках содержится по K натуральных
чисел a(i) –описание каждого профиля
дороги (a(i) –высота асфальта на каждом
участке, отсчитываемая от нулевого уровня, 0<a(i)<=10000, 0<N<=1000, 0<K<=10000).
Выходные данные:
В N строках выведите количество воды, которые скопится в каждом
профиле дороги, если пойдёт дождь.
stdin
|
stdout
|
2 9
251234776
5 5 5 5 5 5 5 5 5
|
10
0
|
Пояснение примера:
В примере для первого случая изображение профиля будет
выглядеть так:
Очевидно, что объем накопленной воды будет равен 10.
Во втором случае профиль плоский и вода скапливаться не
будет, поэтому ответ 0.
B. Нереальный тендер
Ограничение по
памяти: 64М
Ограничение по
времени:1sec
Ямочный ремонт – любимый способ решения одной из самых
главных российских проблем. Чтобы тендер на ямочный ремонт дороги выиграла
«нужная» компания, порой устанавливаются совершенно нереальные требования к
поставляемым материалам.
В одном маленьком российском городе одна помешанная на
математике компания объявила тендер на поставку мешков с асфальтом со
следующими требованиями: вес мешка – некоторое число, состоящее из 2N цифр, при
этом оно должно делиться на число, составленное из первых N его цифр и на
число, составленное из последних N цифр.
Входные данные:
В единственной строке содержится
целое число N (1<N<10001 p="">
E. Автобусы
Выходные данные:
Выведите количество 2N-значных
чисел, которые удовлетворяют описанному выше правилу.
stdin
|
stdout
|
1
|
14
|
Подсказка:
11, 12, 15, 22, 24, 33, 36, 44,
48, 55, 66, 77, 88, 99.
C. Спиральная яма
Ограничение по
памяти: 64М
Ограничение по времени:1sec
С каждым годом количество дорог без крупных ям
увеличивается, как растёт и сумма денег, которую в каждый ремонтный сезон
закатывают в асфальт. При этом дороги в России одни из самых дорогих в мире. А
стоимость ремонта одного маленького кусочка растёт в арифметической прогрессии.
Компания, занимающаяся ремонтом квадратных ям, решила, что
самым оптимальным способом укладки асфальта будет спираль. Тогда каждый
следующий залатанный кусочек ямы можно делать чуть дороже, чем предыдущий… Для
этого нужно начать укладывать асфальт с верхнего левого угла ямы и двигаться
вдоль краёв ямы по спирали против часовой стрелки. Стоимость первого
отремонтированного кусочка будет стоить 1000 рублей. Каждый следующий кусочек
будет дороже ровно на 1000 рублей… Вот такой нехитрый бизнес.
Входные данные:
В первой строке входных данных содержится два числа – N и K – размеры квадратной ямы (0<N,K<=100).
Выходные данные:
Требуется вывести Nстрок по Kчисел
– карта стоимости ремонта квадратной ямы, измеренная в тысячах рублей.
stdin
|
stdout
|
4 5
|
1 14 13 12 11
2 15 20 19 10
3 16 17 18 9
4 5 6
7 8
|
D. Доходы
Ограничение по
памяти: 64М
Ограничение по
времени:1sec
Дорожный бизнес является исключительно прибыльным делом,
поэтому компании борются за каждого потенциального заказчика, чтобы по итогам
года обойти всех и стать самой прибыльной фирмой сезона. Каждая компания знает,
сколько заказов на строительство дорог было выполнено за сезон и какова
стоимость каждого заказа. Однако, проблемы с математикой у руководства дорожных
компаний очевидны, поэтому, порой они до последнего не могут правильно
определить, кто стал лучшим по итогам года…
Входные данные:
В первой строке входных данных содержится число N – количество заказов,
выполненных компанией за сезон. В следующих N строках содержится по два числа – количество километров дорог,
построенных в рамках заказа и стоимость одного километра дороги (все числа
натуральные, не превосходят 10). В последней строке содержится прибыль
компании-конкурента за текущий год (не превосходит 1000).
Выходные данные:
Выведите «YES»,
если первая компания оказалась лидером сезона по прибыли, выведите «NO», если лидером стала
компания-конкурент, выведите «EQUAL»,
если прибыли равны.
stdin
|
stdout
|
3
10 2
3 3
4 7
60
|
NO
|
Ограничение по памяти:
64М
Ограничение по
времени:1sec
Состояние дорожной сети
таково, что в идеале требуется регулярная ревизия общественного транспорта. В
результате на основе социологических опросов населения было составлено
идеальное ежедневное расписание движения междугородних автобусов, утвержденное
руководством всех автотранспортных предприятий.
Более того, было решено
заменить весь автобусный парк одинаковыми новыми, очень дорогими, но гораздо
более надежными, красивыми и удобными машинами.
Автобусная сеть охватывает N городов, занумерованных целыми
числами от 1 до N.
Идеальное расписание содержит
M ежедневных рейсов, i-й рейс начинается в городе Fi в момент времени Xi и заканчивается в некотором другом городе Gi в момент
времени Yi. Продолжительность
каждого рейса ненулевая и строго меньше 24 часов. Рейс i выполняется одним из автобусов, находящихся в момент
времени Xi в
городе Fi.
Новые автобусы не требуют
ремонта и могут работать круглосуточно, поэтому автобус, прибывший в некоторый
момент времени в некоторый город, всегда готов в тот же самый момент времени
или позже отправиться в путь для обслуживания любого другого рейса из данного
города. Автобус может выехать из города, только выполняя какой-либо рейс из
расписания.
Предполагается, что
расписание будет действовать неограниченное время, поэтому может оказаться так,
что его невозможно обслужить никаким конечным числом автобусов.
Определите наименьшее
количество новых автобусов, достаточное для обеспечения движения по расписанию
в течение неограниченного периода времени.
Входные данные:
В первой строке содержатся
целые числа N и М (1 ≤N, M ≤ 100000)— количество городов и рейсов автобусов
соответственно.
В каждой из следующих M строк содержится описание рейса
автобуса: номер города отправления Fi, время
отправления Xi, номер города
назначения Gi (Fi≠Gi), время
прибытия Yi, отделенные друг от
друга одним пробелом. Времена задаются в формате HH:MM, где HH — часы от
00 до 23, MM — минуты от 00 до 59.
Выходные данные:
Выведите одно число —
минимально необходимое количество автобусов. Если расписание невозможно
обслуживать в течение неограниченного периода времени конечным числом
автобусов, выведите число -1.
stdin
|
stdout
|
21
1 09:00 2 15:30
|
-1
|
5 5
1 09:00 2 14:30
3 23:45 1 06:50
2 14:30 3 20:50
4 09:00 5 21:00
5 10:00 4 20:00
|
3
|
