Результаты 1 личного тура чемпионата по программированию

Завершился 1 личный тур Открытого чемпионата СыктГУ по программированию.

Спасибо всем участникам чемпионата и тем, кто его делал и провел: Василию Болгар, Анатолию Кораблеву, а также сотрудникам лаборатории информатики №1, благодаря которым все работало!
Вот результаты:

		Личный тур СГУ. 14 декабря
		Турнир завершён!
R	Участник			A	B	C	D	E	+	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="">

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

Выведите количество 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

  E. Автобусы

Ограничение по памяти: 64М

Ограничение по времени:1sec

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

Более того, было решено заменить весь автобусный парк одинаковыми новыми, очень дорогими, но гораздо более надежными, красивыми и удобными машинами.

Автобусная сеть охватывает N городов, занумерованных целыми числами от 1 до N.

Идеальное расписание содержит M ежедневных рейсов, i-й рейс начинается в городе F_i в момент времени X_i и заканчивается в некотором другом городе G_i в момент времени Y_i. Продолжительность каждого рейса ненулевая и строго меньше 24 часов. Рейс i выполняется одним из автобусов, находящихся в момент времени X_i в городе F_i.

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

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

Определите наименьшее количество новых автобусов, достаточное для обеспечения движения по расписанию в течение неограниченного периода времени.

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

В первой строке содержатся целые числа N и М (1 ≤N, M ≤ 100000)— количество городов и рейсов автобусов соответственно.

В каждой из следующих M строк содержится описание рейса автобуса: номер города отправления F_i, время отправления X_i, номер города назначения G_i (F_i≠G_i), время прибытия Y_i, отделенные друг от друга одним пробелом. Времена задаются в формате 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