Летний самосбор 2019 в Сыктывкаре

Дипломы и сертификаты XX Открытого чемпионата СГУ по программированию

Готовы  сертификаты участников и дипломы победителей и призеров чемпионата по программированию
https://drive.google.com/drive/folders/1XWZ-H1Ka90WlKVRQpHi-H7IvNhJS9wHG?usp=sharing

Папка будет доступна в течение 1 месяца. Скачивайте, распечатывайте, для портфолио пригодятся. 

Итоговые результаты чемпионата Урала

Чемпионат Урала завершился без неожиданностей. Победила команда ИТМО с 10 решенными задачами. Вполне возможно, что это будущие чемпионы мира.

1

ITMO University: Eat Less, Drink More (Дмитрий, Будин, Кириллов)

+ 0:02

+ 2:48

–5 4:57

+6 4:32

+ 0:09

+1 1:15

+ 0:54

+ 0:11

+4 4:47

+ 0:30

+1 0:41

10

1189

Затем две команды УрФУ (будущие участники? призеры? победители ЧМ?)

2

Ural FU: Беспруфные Кукареки (Абалымов, Усманов, Зуев)

+ 0:03

+7 4:58

–1 3:47

+ 0:37

+ 1:16

+ 1:20

+ 0:12

+2 2:21

+ 0:06

+1 0:32

9

885

3

Ural FU: Можно (Муллабаев, Ханова, Трифочкин)

+ 0:26

+ 4:50

+1 4:14

+1 0:16

+2 2:43

+ 1:29

+ 1:34

+ 0:10

+ 1:06

9

1088

Наши ребята в столь сильной компании квалифицировались с двумя решенными задачами. Молодцы!

35

Syktyvkar SU: nonameteam (Гладких, Голенев, Ладанов)

–2 3:33

+ 1:09

+ 0:23

2

92

Полностью итоговые результаты здесь https://timus.online/monitor.aspx?id=729 

Чемпионат Урала начался!

Начался основной тур XXIII Открытого чемпионата Урала по спортивному программированию. Он проходит  в Уфе в здании Конгресс-холла с 10:00 до 15:00 (время по часовому поясу Уфы (UTC+5)). Участникам предложено 12 задач. На момент публикации было

Syktyvkar SU: nonameteam (Гладких, Голенев, Ладанов)

+ 0:23

1

23

Сейчас уже лучше

Syktyvkar SU: nonameteam (Гладких, Голенев, Ладанов)

+ 1:09

+ 0:23

2

92

Поболеть можно здесь https://timus.online/monitor.aspx?id=729

Поселение участников в отеле Hilton Garden Inn Ufa Riverside, который располагается в историческом центре Уфы, на берегу реки Белой, в 500 метрах до Конгресс холла. Это фото сделал Илья Голенев

Разбор задач ХХ чемпионата

Задачи XX открытого чемпионата СГУ по программированию

На чемпионате были предложены задачи, придуманные Езовских В.Е. для самых первых чемпионатов. Условия задач были на английском языке. Разбор задач от Котелиной Н.О.

Задача A. Bobby The Judge

Once Bobby heard that the lawyers' wages are enormous. So he decided to become a judge. The only problem is to pass an exam. The task at the examination is as follows. One has to sentence N (2≤ N≤32) criminals. The criminal number i (1≤ i≤ N) may be jailed for the period just from Si to Ei years (1≤ Si≤ Ei ≤ 1024). Is it possible to sentence each criminal so, that he will rest in the jail for Pi years under the condition – all Pi differ? Help Bobby, please! All numbers are integers.

Разбор

Дан набор из N отрезков на прямой. Требуется выяснить, можно ли выбрать N различных точек, чтобы в каждый отрезок попала хотя бы одна. 

Можно использовать следующий жадный алгоритм. Отсортируем отрезки в лексикографическом порядке.  Переберем отрезки. Будем для каждого отрезка выбирать наименьшую точку, лежащую на этом отрезке, которая еще не выбрана для предыдущих отрезков (для первого - это начало отрезка). Если такой точки для некоторого отрезка нет, ответ IMPOSSIBLE.

Если для всех отрезков точки найдутся, ответ POSSIBLE.

Задача B. The Puzzle for Aliens

Many years ago there were N (3≤ N≤ 1024) villages on the Earth surface. Aliens had defined geographical coordinates (the latitude T_i and the longitude G_i) of each village. The devices of aliens were rather poor and the coordinates were measured with the accuracy equal to a degree. So, T_i is an integer (0≤ T_i≤ 90) and G_i is an integer (0≤ G_i≤ 180). The numerical values are followed by the letters S (southern latitude), N (northern latitude), W (western longitude), E (eastern longitude). Aliens had to define the shortest distance between villages (the distance is measured on the Earth surface). They were solving this problem for a long time, but – no success! So they spat a little and had flied to their native planet. Are you able to solve this problem? You may suppose that the Earth has the form of the sphere with the radius 6366 kilometers, the answer should be rounded to a kilometer.

Разбор

В задаче надо было найти минимальную длину дуги между парами точек на сфере. Чтобы решить задачу B, можно было перевести координаты из широты и долготы в декартовы, а затем вычислить углы между получившимися радиус-векторами точек, например при помощи скалярного произведения. Длина дуги соответствующей данному углу alpha тогда равна alpha*r.

Задача C.    The Gadfly and The Windows

Bobby had installed the so-called "ОКНА СОК" and just as a result his beloved gadfly OVOD has some problems. Every time OVOD goes inside by the shortest way. But those multi-layer windows! Each window consists of N (2≤ N ≤ 16) layers at the fixed distance (an inch). Each layer is just a checked square (four times four, side of the check is equal to an inch) and only one of the checks is the layer pane (OVOD may bypass the layer only through the pane). Look at the picture just below – this is an example of the layer

OVOD may penetrate only through the green square. Such a layer may be defined by a single integer (the left-upper corner – zero, the green square above – just six). For a better understanding the picture just below demonstrates OVOD flight through two-layer window

The OVOD's way is marked with red and its length is equal to . You are to find the length of OVOD's flight inside the window with the accuracy two digits after the decimal point.

Разбор

Надо найти длину пути овода. Задачу можно решить методом динамического программирования: на каждом слое длина кратчайшего пути каждой из вершин квадрата форточки получается как минимум из длин кратчайшего пути для предыдущего слоя для четырех вершин квадрата форточки плюс расстояние между соответствующими точками. В конце нужно взять минимум из 4 значений кратчайшего пути для вершин квадрата n-ой форточки. 

Задача D. The Two's Powers

Just as everybody knows, Bobby likes the powers of two. So once he calculated all powers of two up to N (2≤ N ≤ 20) and has tried to settle those numbers in such an order that the total result of concatenation would be maximal. For example, if one takes N=5, then powers of two will be 1, 2, 4, 8, 16, 32 and the result will be 84322161. Are you able to gain the result for a given number?

Разбор
Здесь надо было вычислить все степени двойки до N и написать их в таком порядке чтобы получившееся число было максимальным. Чтобы решить эту задачу, можно было отсортировать массив строк, соответствующих степеням 2, используя тот факт что строка a должна предшествовать строке b в массиве если строка a + b лексикографически больше чем строка b + a. Затем вывести получившиеся строки

Задача E. The Frequencies

Once Bobby read that the irrational numbers, such as  are the perfect mixture of digits. So one can find any decimal digit as many times as he wants. Bobby likes the powers of two, so he decided to find the minimal power of two in which the predefined decimal digit from 0 to 9 encounters some times (from 1 to 9). For example, minimal power of two where six encounters twice is sixteen (216=65536). Help Bobby, please!

Разбор
Нужно вычислять степени двойки до тех пор пока число вхождений заданной цифры не будет больше или равно заданного количества. 

Задача F. The Digits on The Clock

The digital clock is on the Bobby's TV set. It shows hours, minutes and seconds, so during a day it runs from 00:00:00 to 23:59:59. Bobby tried to calculate the sum of those numbers (omitted colons) but failed. Are you able to define this sum?

Разбор

В этой задаче надо просуммировать все числа от 0 до 235959, которые получаются удалением двоеточий из времен, заданных в формате hh:mm:ss 

int main(){

long long x = 0;
//
long long sh = 0;
long long sm = 0;
long long ss = 0;
for (int h=0; h <=23; h++){
for (int m =0; <=59; m++){
for (int s = 0; <=59; s++){
x +=h*10000+m*100+s;
}
}
}
cout << x; 
}

Итоги командного тура XX открытого чемпионата СГУ 2019

В 1999 году команда студентов кафедры прикладной математики в составе Зелянина Романа, Подорова Максима, Чупрова Владимира заняла 9 место в четвертьфинале (г. Екатеринбург) и стала участницей полуфинала командного чемпионата мира по программированию (г. Санкт-Петербург), где вошла в число квалифицированных команд, заняв 38 место из 88 команд. Этот год мы считаем началом Открытого чемпионата СГУ по программированию.

20 лет нашему чемпионату!

Поздравить участников с юбилеем пришли и.о. ректора Сотникова Ольга Александровна, депутат Государственного Совета Артеев Сергей Вячеславович, директор ИТНИТ Миронов Владимир Валерьевич.

На пустом экране мог бы быть логотип чемпионата. Предлагайте!

В командном туре участвовало 24 команды: школьники, студенты и профессионалы. На контест было предложено 9 задач. Их автором является Езовских Владимир Евгеньевич. 13 лет назад эти задачи впервые были использованы на контесте.  Конечно, как справедливо заметил участник командного тура Олег Виноградов, они очень сильно контрастируют с современными контестами в том плане, как жюри оценивает точность ответов участников. Это доставило некоторые неудобства участникам.

Протокол уже опубликован https://nkpopova.blogspot.com/2019/04/xix-201.html. Немного статистики.

• Школьных команд - 9
• Студенческих команд - 13 (из них 1 курс - 2 команды)

22 команды квалифицировались, решив хотя бы по одной задаче.

Фотоальбом здесь: 

https://photos.app.goo.gl/rPcorDm1KhxmWfpZ9

Команда SuperTeam2008 участвует в чемпионате уже в 11 раз. Иногда, в зависимости от состава, она называет себя Old School. Уже состоявшиеся программисты порадовали и себя и нас. Первыми решили задачи E и F. Третье место в общем рейтинге, вне конкурса.

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

Волк-одиночка Олег Виноградов, студент ВШЭ, г. Москва, показал лучший результат, решив 6 задач из 9. Первым решил задачи B, D, G. Выступал вне конкурса. Возможно, Олег найдет время и порадует нас разбором задач этого контеста.

Здесь Олег еще школьник, ученик КРФМЛИ

Отмечу еще команду ThL_3 (Хилько Павел, Андрюков Арсений, Агарков Вадим). У команды высокий потенциал. Они первыми решили задачу A, которую решили только 6 команд. И не решили F, что-то помешало им правильно посчитать.

Все команды-участники получат сертификаты, а первые пять команд - дипломы победителей и призеров. На их изготовление потребуется какое-то время. Три лучшие команды уже получили призы - ручки "Паркер". Традицию награждать программистов ручками ввел Никитенков Владимир Леонидович, сделавший очень много для организации чемпионата.

Второе место в общем рейтинге, 5 решенных задач, команда Собака да лисица. 

Собака да лисица (Чекменёв Владимир, Алексеев Валерий, Шеремет Иван)

Четвертое место, 4 решенные задачи, команда ThL_1 

ThL_1 (Кудинов Александр, Векшин Владислав, Бочкина Елизавета)

Пятое место, 3 решенные задачи, команда ЛНД 

ЛНД (Нестеров Дан, Можегова Екатерина, Турубанова Светлана)

Чемпионат Урала по программированию

Лучшим командам университета предлагается поучаствовать в Чемпионате Урала по программированию. Он пройдет в Уфе, 2-3 мая http://acm.urfu.ru/chu/2019/index.html

Это команды:

  6. Brothers (Ищук Виталий, Дуркин Анатолий, Ванюта Егор)
10. Blizzplsnerfdruid (Голенев Илья, Поляков Артем, Гладких Марина)

Шарики

И в заключение благодарю ООО «Пиротехника Коми» в лице ее директора Макарова Андрея, организовавшие нам праздничную атмосферу. Макаров Андрей наш  выпускник и много раз принимал участие в чемпионате. Он лучше всех знает, как организовать праздник! Спасибо!

Протокол командного тура XIX открытого чемпионата СГУ 201

Протокол командного тура XX Открытого Чемпионата СГУ им. Питирима Сорокина

https://official.contest.yandex.ru/contest/12451/standings/

Дата проведения : 13 апр 2019
начало: 13:15:00
конец: 17:15:00
длительность:  04:00:00
Последний правильный ответ:E,Ya dumau (Ладанов Николай, Непеин Андрей, Колов Даниил),03:23
Последнее отправленное решение:G,BUGs Bunny (Фокин Кирилл, Смирнов Александр, Уварков Сергей),03:59

№	Участник	A	B	C	D	E	F	G	H	I	Очки	Штраф
		6/63	1/4	0/23	6/34	12/25	19/111	2/24	0/12	0/2
1	Волк-одиночка (Виноградов Олег)	+ 02:24	+ 00:29	-5 03:12	+ 00:47	+ 01:25	+1 00:33	+ 01:37	-6 03:04	—	6	457
2	Собака да лисица (Чекменёв Владимир, Алексеев Валерий, Шеремет Иван)	+1 02:55	—	—	+1 01:56	+ 01:38	+2 00:39	+ 02:19	-1 00:26	—	5	650
3	SuperTeam2008 (Кораблев Анатолий, Кузнецов Константин, Потолицын Александр	+ 02:12	-2 03:39	—	+ 01:53	+ 00:54	+ 00:14	-3 03:14	—	-2 03:57	4	315
4	ThL_1 (Кудинов Александр, Векшин Владислав, Бочкина Елизавета)	+8 02:52	—	—	+7 01:55	+ 02:32	+6 02:23	-8 03:58	-1 03:27	—	4	1004
5	ЛНД (Нестеров Дан, Можегова Екатерина, Турубанова Светлана)	+1 01:00	—	-7 03:46	+ 01:40	—	+2 00:38	-5 02:12	—	—	3	259
6	Brothers (Ищук Виталий, Дуркин Анатолий, Ванюта Егор)	-7 01:15	—	-11 03:56	-3 02:38	+1 01:31	+1 00:34	—	—	—	2	165
7	LSGU #2 (Исаков Алексей, Бадьин Дмитрий, Размыслов Константин)	-9 02:15	—	—	-3 00:52	+ 01:44	+ 01:32	-1 03:03	—	—	2	197
8	ThL_3 (Хилько Павел, Андрюков Арсений, Агарков Вадим)	+1 00:55	—	—	-4 03:56	+1 02:02	-3 01:44	-1 03:14	-1 02:27	—	2	218
9	Авокадо (Захаров Иван Дмитриевич, Шучалина София Денисовна, Шевелёв Илья Андреевич)	-5 02:10	—	—	-3 01:47	+3 01:25	+2 01:00	—	—	—	2	246
10	Blizzplsnerfdruid (Голенев Илья, Поляков Артем, Гладких Марина)	-8 02:14	—	—	—	+ 02:10	+4 01:15	—	—	—	2	285
11	Ya dumau (Ладанов Николай, Непеин Андрей, Колов Даниил)	-2 02:01	-1 01:49	—	-1 03:52	+ 03:23	+1 02:19	—	—	—	2	363
12	Pixels (Сизов Николай, Янников Святослав, Поташев Александр)	—	—	—	—	+ 03:21	+6 02:39	—	—	—	2	480
13	ThL_2 (Федоров Павел, Макаров Леонид, Балыгин Егор)	-3 03:35	—	—	—	—	+ 00:44	-3 02:47	—	—	1	44
14	TS (Богдан Арсений, Сибилев Алексей, Кондаков Илья)	-2 00:26	—	—	+1 01:14	—	-8 03:22	—	—	—	1	94
15	BUGs Bunny (Фокин Кирилл, Смирнов Александр, Уварков Сергей)	—	—	—	—	+ 02:31	-2 01:17	-1 03:59	—	—	1	151
16	Timon & Pumbaa (Тимошенко Аксинья, Глебова Ирина)	—	—	—	—	—	+2 02:06	—	—	—	1	166
17	LSGU #1 (Воронов Иван, Изъюров Кирилл, Нестеров Ростислав)	—	—	—	—	-5 03:50	+3 02:19	—	—	—	1	199
18	Тути-Фрути 3D (Филиппов Денис, Стрекалов Ростислав, Арсеньев Виктор)	—	—	—	—	—	+5 02:07	—	—	—	1	227
19	JoJoKi (Морозов Николай, Торчагин Никита, Русинова Юлия)	—	—	—	—	—	+5 02:28	—	—	—	1	248
20	Nomads (Борисов Михаил, Яруков Дмитрий, Карманов Александр)	-1 01:17	—	—	—	—	+7 01:54	—	-3 02:39	—	1	254
21	Парусник (Некрасова Елена, Смоленцев Антон, Степанова Ольга)	-4 01:31	—	—	—	—	+6 02:58	—	—	—	1	298
22	Сыктывкар (Шадрин Лев, Попов Даниил, Григорьев Владимир)	—	—	—	-2 03:51	—	+9 02:25	—	—	—	1	325
23-24	Black Code (Камашев Артур, Матвийчук Богдан, Копосов Вячеслав)	-5 03:03	—	—	-3 03:04	—	-7 01:35	—	—	—	0	0
23-24	ПМо (Лапуньков Даниил, Ладанова Светлана)	—	—	—	—	-3 03:23	-10 02:47	—	—	—	0	0