Международные сборы по программированию

Центр развития ИТ-образования МФТИ приглашает ваши команды принять участие в Международных сборах по программированию Moscow Pre-Finals Workshop, которые пройдут с 18 по 26 апреля при поддержке Университета ИТМО. В связи с эпидемиологической обстановкой в мире, этой весной мы вынуждены полностью отказаться от очного проведения сборов на площадке Физтеха. Moscow Pre-Finals Workshop пройдет с полным сохранением образовательной программы в онлайн-формате. Обучение будет проходить на английском языке в формате двух дивизионов: Дивизион А – для опытных команд с серьезным уровнем подготовки, которые участвуют в финале ICPC. Дивизион B – для тех, кто готовится к участию в следующем сезоне. В режиме онлайн команды получат полный доступ к учебной программе: доступ к контестам в течение трех месяцев с начала сборов (каждый контест открывается практически одновременно с началом контеста в МФТИ); видеотрансляции и текстовые материалы разборов контестов; видеотрансляции и текстовые материалы лекций (для дивизиона В); электронный сертификат о прохождении сборов. Расписание включает в себя RuCode Festival (в прошлом - MosCode), который пройдет 25 и 26 апреля в онлайн-формате. Цена удаленного участия —  51000 рублей на одну команду для участников из стран ЕАЭС. Для участников из остальных стран стоимость составит $690 на команду. Также мы ввели систему скидок, которая позволит многим командам поучаствовать в сборах с большой скидкой или бесплатно. Обратите внимание, если команда хочет претендовать на скидку за участие в контесте 4 апреля, ей необходимо зарегистрироваться на удаленное участие в сборах, тогда перед началом контеста ей будет выслан логин и пароль.  Дистанционный формат никак не повлияет на качество самих сборов. Наша команда и тренеры Moscow Workshops приложат все усилия, чтобы обеспечить командам полную информационную поддержку и комфортное обучение. Чтобы участвовать в сборах дистанционно, нужно пройти регистрацию: Регистрация для команд из стран ЕАЭС Регистрация для команд из остальных стран Если у вас остались вопросы, будем рады на них ответить!

Разбор задач

A.                  Ревизия

В пяти городах A, B, C, D и E требуется провести документальную ревизию. Для осуществления этой ревизии необходимо составить и издать приказ о ее проведении. Одним из пунктов в приказе является время командировки ревизора (лица, осуществляющего проверку в городах A, B, C, D, E).

Данная таблица содержит информацию о том, сколько времени занимает путешествие между каждым из городов.

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

Так, например, маршрут A-B-C-D-E-A удовлетворяет условиям поставленной перед ревизором задачей, а длительность командировки, при таком маршруте, равна 9+27+11+20+8 = 75. Маршрут A-B-C-D-E не является правильным, так как ревизор не вернулся в город A.

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

Ответ: 65

B.                  Головокружительные числа

Маша – большая поклонница всевозможных кругов, кружочков и окружностей. Она старается разглядеть их во всем, что ее окружает. А еще она очень любит гармонию и математику. Не обошла она своим вниманием и числа, решив для себя, что будет считать "округлым" лишь то число, которое содержит в своей записи столько кружков, из скольки цифр оно состоит. Например, число 678 – "округлое", а 12678 таковым не является. А если еще при этом в числе в первой и последней цифре количество кругов совпадает, то это вообще "головокружительное" число. Написать программу проверки числа на "округлость" и "головокружительность".

Разбор. Нужно было аккуратно посчитать кружочки в цифрах числа и количество цифр числа и обработать все случаи. Проблемы: возникли у участников, которые писали решение на Питоне, входную строку нужно было обработать при помощи int(input())  или

убрать перевод строки с помощью метода strip: input().strip().

C.                  Транспортировка

На складе лежат N ящиков с товарами, их веса равны .

К складу подъехали две машины, чтобы доставить эти товары в магазин. Требуется загрузить ящики в эти две машины так, чтобы веса перевозимых ящиков (вес ящиков в более загруженной к весу ящиков в менее загруженной) в них отличались не более, чем в D раз. Если разделить ящики таким образом возможно, вывести Yes, иначе No.

Разбор. Известная задача с Тимуса. Решается с помощью перебора. Можно кодировать ящики в первой машине нулями, а ящики во второй единицами, и брать оптимальное соотношение весов.

Жадный алгоритм не оптимален. Попробуйте, например, распределить оптимально ящики с весами  5 5 4 3 3 жадным алгоритмом.

D.                  Числа – палиндромы

Будем называть число палиндромом, если оно одинаково читается слева направо и справа налево. Например, числа 6, 232 и 1221 - это палиндромы, а число 3210 - нет. Для заданного числа N выведите первое число такого вида, которое строго больше N.

Разбор. Известная задача. Использовалась ранее на муниципальных олимпиадах.

Превращаем считанное число в палиндром, переписывая цифры из первой половины строки в обратном порядке во вторую половину строки. Если число получилось меньше исходного — увеличиваем первую половину числа на 1 и снова превращаем его в палиндром.

E.                  Подпоследовательность

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

Разбор. Известная задача. Использовалась ранее на муниципальных олимпиадах.

Рассмотрим частичные суммы элементов последовательности от ее начала до i-го элемента

включительно. Так как нас интересуют остатки от деления суммы на 1000000 и из свойства остатков

известно, что (X+Y) mod M= ((X mod M) + (Y mod M)) mod M, можно рассмотреть не сами суммы, а их остатки от деления. Так как нас интересует остаток равный 0, мы должны найти в последовательности остатков частичных сумм ближайшие одинаковые значения (если остатки одинаковы, значит остаток для суммы элементов подпоследовательности между ними равен 0). Для этого для каждого остатка нужно запоминать позицию, когда этот остаток встречался и находить минимальный вариант для разницы позиций.

F.                  Подпоследовательность - 2

Наибольший общий делитель двух чисел вычисляется по формуле: НОД(a,b)=a, если b=0; НОД(a,b)=НОД(b, a mod b), если b>0. НОД нескольких чисел вычисляется последовательным применением НОД к парам чисел: НОД(a,b,c)=НОД(НОД(a,b),c), НОД(a)=a.

Посчитайте, сколько различных значений принимает наибольший общий делитель для всевозможных последовательностей вида , где 1≤ i ≤ j ≤ N в последовательности .

Разбор. Известная задача. Использовалась ранее на муниципальных олимпиадах.

НОД подпоследовательности чисел не может возрастать при добавлении очередных элементов в подпоследовательность и таким образом не может принять более

log₂(10¹⁸) значений (примерно 60).

Пусть  D_i = { НОД(a_j , . . . , a_i ) | j ≤ i }, при этом размер D_i не превышает O(log₂ (a_i) ).

Тогда можно рассчитать D _i+1 = { gcd(v, a _i+1) | v ∈ D_i } ∪ { a_i+1}

Время работы алгоритма O(N log₂²(10¹⁸)).

Результаты XXI Открытого чемпионата СГУ по программированию

XXI Чемпионат по программированию «ПЕРВОКУРСНИК»

Начало: 16 ноя 2019, 12:25:00
Конец:   16 ноя 2019, 16:25:00
Длительность: 4 часа

№	Участник	A 33/93	B 23/135	C 4/33	D 1/83	E 1/6	F 0/7	Очки	Штраф
1	Нестеров Дан	+2 00:10	+ 00:16	+ 00:28	+4 02:57	+ 01:40	-7 03:58	5	452
2	Размыслов Константин	+2 01:47	+4 00:23	+2 01:20	-8 03:20	—	—	3	371
3	Федоров Павел	+6 02:31	+1 00:34	+ 00:51	-4 02:03	—	—	3	377
4	Копосов Вячеслав	+ 00:09	+ 00:43	—	—	—	—	2	53
5	Филиппов Денис	+ 00:10	+ 00:44	—	—	—	—	2	55
6-7	Арсеньев Виктор	+ 00:12	+ 00:45	—	-2 00:44	—	—	2	57
6-7	Тимошенко Аксинья	+ 00:15	+ 00:42	—	—	—	—	2	57
8	Глебова Ирина	+ 00:15	+ 00:45	—	-3 00:44	—	—	2	60
9	Попов Иван	+ 00:18	+ 00:45	-2 01:36	—	—	—	2	63
10	Матвийчук Богдан	+ 00:10	+1 00:40	—	—	—	—	2	71
11	Смоленцев Антон	+ 00:09	+ 01:18	—	—	—	—	2	88
12	Губанов Денис	+1 00:12	+2 01:07	—	—	—	—	2	139
13	Андрюков Арсений	+3 00:49	+2 00:34	-10 03:45	-2 03:11	-3 03:36	—	2	183
14	Хилько Павел	+1 00:11	+6 00:54	-4 01:25	-5 03:54	—	—	2	206
15	Богдан Арсений	+1 01:07	+2 01:55	-1 01:19	-7 02:24	—	—	2	242
16	Ушаков Иван Сергеевич	+ 02:30	+1 01:32	—	—	—	—	2	262
17	Некрасова Лена	+3 00:08	+1 03:19	-1 03:39	-2 00:47	—	—	2	287
18	Степанова Ольга	+ 02:05	+ 03:16	-2 03:49	—	—	—	2	321
19	Яруков Дмитрий	+2 02:34	+2 01:45	—	—	—	—	2	339
20	Сибилев Алексей	+ 00:34	+11 03:41	—	-4 01:04	-2 02:10	—	2	475
21	Бондаренко Анатолий	+17 02:32	-6 01:34	+3 02:11	—	—	—	2	684
22	Островский Максим	+ 00:11	-3 02:33	—	—	—	—	1	11
23	Козлов Иван Евгеньевич	-2 00:13	+ 00:24	—	—	—	—	1	24
24	Игнатович Вадим	—	+ 00:33	—	-2 02:17	—	—	1	33
25	Поповцев Никита	+ 00:34	-5 01:19	—	—	—	—	1	34
26	Агарков Вадим	+1 00:29	-3 03:22	—	-4 02:42	—	—	1	49
27	Поздин Михаил	+1 00:46	—	—	-4 02:38	—	—	1	66
28	Магац Александр	+ 01:14	—	—	-5 03:45	—	—	1	74
29	Денисов Александр	+2 00:46	—	-1 02:11	-3 02:32	—	—	1	86
30	Пувкоева Таисия	+ 02:40	-6 03:03	-2 03:35	—	—	—	1	160
31	Прошева Яна	+ 03:01	-3 01:43	—	—	—	—	1	181
32	Корчагин Юрий	+4 02:13	—	-1 02:15	—	—	—	1	213
33	Стрекалов Ростислав	+ 03:38	—	—	-4 01:46	—	—	1	218
34	Изъюров Степан	+3 02:55	-3 03:55	—	—	—	—	1	235
35	Григорьев В. С.	+5 02:29	-9 03:37	—	—	—	—	1	249
36	Ищук Виталий	—	+9 02:15	—	-2 00:55	—	—	1	315
37-40	Попел Семен	-2 00:34	-26 01:46	—	—	—	—	0	0
37-40	Рочев Алексей	—	-2 01:07	—	-7 01:49	—	—	0	0
37-40	Кожагельдиев Никита	-1 01:58	-4 01:37	—	-10 02:45	—	—	0	0
37-40	Пащак А. А.	-1 02:11	—	—	—	—	—	0	0