воскресенье, 14 мая 2017 г.

Разбор задач

A.    Бригада грузчиков

Для переноски тяжестей собирается бригада из n грузчиков-огров. Бригада может состоять из одного, трёх или пяти огров. Шрек, огр уровня Y, собирает бригаду огров разного уровня, уровень которых отличается не более чем на x от его уровня. Вам даны уровни всех грузчиков в бригаде. Определите уровень Шрека. 


Разбор. Это задача с Codeforces, контест VK Cup 2017 - Квалификация 1, задача A. Год поступления в университет. Данную задачу можно решать разными способами. Самый простой из них — положить все заданные числа в массив, отсортировать его и вывести медиану получившегося массива (то есть элемент, находящийся в его середине).

      B. Сеть порталов

Университету Магии выделили грант на создание лаборатории телепортаций. Провели тендер и закупили генератор магии, n порталов разной мощности и k распределителей. Для каждого распределителя известно число Ai слотов в нем и максимальная суммарная мощность Bi порталов, которые могут быть в него подключены, а для каждого портала известна потребляемая им мощность Ci.
Теперь необходимо составить схему подключения порталов к генератору с использованием распределителей с учетом следующих соображений. Для каждого i-го распределителя суммарная мощность порталов, включенных в него как напрямую, так и через другие распределители, не превосходит соответствующего значения Bi. Число порталов и распределителей, напрямую включенных в i-й распределитель, не превосходит Ai. При этом, в соответствии с правилами безопасности, в каждый распределитель можно подключать не более одного другого распределителя.
Гарантируется, что мощность генератора магии достаточна, чтобы выдержать подключение всех имеющихся устройств. Отметим также, что при необходимости к генератору можно подключить портал напрямую.
Напишите программу, которая найдет требуемую схему подключения устройств.

 Разбор. Эта задача, как и следующие, за исключением последней, с X Всероссийской командной олимпиады школьников по программированию 13-14 ноября 2009 года. Задача D. Электричество. Не влезай, убьет.
По условию задачи в наличии имеется:
              k распределителей
              n порталов
              1 генератор магии
Требуется подсоединить все порталы так, чтобы потребляемая ими мощность не превышала допустимую для распределителя. К распределителю можно подсоединить не более одного распределителя.
Основные идеи:
Не имеет смысла подключать фильтр к фильтру с меньшей максимальной нагрузкой.
Наиболее мощные приборы имеет смысл ставить ближе к розетке.

Решение.

Отсортировать электроприборы и фильтры в порядке невозрастания мощностей.
Строить ответ жадно, начиная с фильтра, подключенного к розетке.

С.    Разбиение Гноллов

Комбинаторика - она и в Холмах Гноллов комбинаторика. Каждый гнолл знает, что разбиения числа n на слагаемые - это набор целых положительных чисел, сумма которых равна n. При этом разбиения, отличающиеся лишь порядком слагаемых, считаются одинаковыми, поэтому можно считать, что слагаемые в разбиении упорядочены по неубыванию.
Например, существует 7 разбиений числа 5 на слагаемые:
5=1+1+1+1+1
5=1+1+1+2
5=1+1+3
5=1+2+2
5=1+4
5=2+3
5=5

В приведенном примере разбиения упорядочены лексикографически ‑ сначала по первому слагаемому в разбиении, затем по второму, и так далее. В этой задаче гноллу Гоше требуется по заданному разбиению на слагаемые найти следующее в лексикографическом порядке разбиение. Помогите ему.

Разбор. Это задача H. Следующее разбиение на слагаемые с X Всероссийской командной олимпиады школьников по программированию 13-14 ноября 2009 года

Решением задачи является генерация следующего комбинаторного объекта:

Дано разбиение
   5=1+1+3
  1. Идём с конца, пока нельзя увеличить слагаемое
  2. Увеличим слагаемое на минимальную величину
  3. Допишем минимальный «хвост»

Когда можно увеличить слагаемое?

Первое слагаемое с конца нельзя увеличить
Второе слагаемое с конца можно увеличить
Например можно прибавить к нему последнее слагаемое
5=1+1+3   →   5=1+4

На сколько можно увеличить слагаемое?

Слагаемое можно увеличить на 1, если оно было меньше последнего хотя бы на 2
5=1+1+3   →   5=1+2+2
Иначе его надо увеличить на величину последнего слагаемого
5=1+2+2   →   5=1+4

Как дописать минимальный «хвост»?

Надо вывести хвост с суммой S, при этом последнее слагаемое которое было выведено перед ним равно K
Выведем несколько(возможно ноль) слагаемых K, а затем остаток
Остаток должен быть не меньше чем K

D.    Эльфы – такие эльфы

Эльфов, населяющих леса в окрестностях Одинокой горы, очень беспокоит активное строительство путей между городами людей. Недавно эльфийский резидент в Дейле выкрала секретный документ. Сотрудники первого отдела разведки подозревают, что это список пар городов, между которыми проложены пути. Попытавшись сопоставить номера городов с городами людей, сотрудники убедились, что это можно сделать.
Однако сотрудники второго отдела высказали другое предположение. Они предположили, что этот список --- это в точности список пар городов, между которыми нет путей. Попытавшись сопоставить номера городов с городами людей, они также убедились, что это можно сделать.
Трандуил в затруднении. Решив проверить, возможно ли такое, он попросил сотрудников третьего отдела выяснить, может ли так быть, что между некоторыми городами людей проложены пути, а между некоторыми --- нет, и существует самодвойственный список пар.
Список пар целых чисел от 1 до n называется самодвойственным, если можно занумеровать города так, чтобы он задавал все пары городов, между которыми есть путь, а можно перенумеровать города таким образом, чтобы тот же самый список задавал все пары городов, между которыми путей нет.
Помогите сотрудникам третьего отдела решить поставленную задачу.

Разбор. Это задача I. Самодвойственный документ с X Всероссийской командной олимпиады школьников по программированию 13-14 ноября 2009 года. Соответственно, разбор сделан в технике копи-паст. 

По условию задачи надо построить граф из n вершин
Первый отдел: пары чисел – это ребра графа
Второй отдел: пары чисел – это вершины между которыми ребра нет
Граф изоморфен своему дополнению

Когда ответ существует?

В полном графе из n вершин  n(n - 1)/2 ребер

Если n = 4k + 2 или n = 4k + 3, то ребер нечетное число – ответ «No»

Если n = 4k или n = 4k + 1, то ответ «Yes» 



E.    Красота эльфийского леса

Несколько отрядов эльфов были посланы на восстановление Пущи Драколесья после опустошительного пожара, вызванного извержением Одинокой горы.
Отрядам выделены одинаковые участки, на которых они высаживают деревья. На участке деревья одного вида занимают ровно один ряд. Прошел назначенный срок, и распорядитель работ затребовал и получил отчеты о результатах посадочных работ. В сборном отчете данные о количестве заполненных рядов каждым отрядом были приведены в порядке невозрастания. Знакомясь с отчетом, Трандуил обратил внимание на тот факт, что количество рядов, посаженных каждым отрядом, является делителем числа видов деревьев (или нулем).
Красивый математический факт восхитил Трандуила. Его заинтересовало, сколько еще рядов смогут суммарно посадить отряды так, чтобы после каждого посаженного ряда сохранялось указанное свойство: количество рядов, посаженное отрядом, является делителем числа видов деревьев (или нулем).


Как решать? Для каждого отряда увеличивать количество рядов, пока это не изменяет красоту эльфийского леса.
У количества рядов не может быть более 24 подряд идущих делителей, так как минимальное число, которое делится на все числа от 1 до 24 это ― 5354228880.

F.    Трудный выбор

Достигнув необходимого возраста, наш герой отправляется в центральный мир АВ, дабы выучить всё что должен знать дворянин, и заодно отдать свой долг империи и отслужить на звёздном флоте. Путь тяжел и долог и почти на каждом шагу надо делать выбор. Результат каждого выбора ‑ некоторое целое неотрицательное число (штраф). Чем меньше будет суммарный штраф после прохождения пути, тем лучше. Но горе герою, если штраф будет выражаться четным числом! 
Задача. Набрать в сумме по всем строкам минимальный штраф, который должен быть нечетным числом. 
Во входных данных имеется последовательность строк (не более 10000). Каждая строка состоит из двух непустых слов, разделенных пробелом. Слово - последовательность латинских букв и цифр. Длина каждого слова не превосходит 100 символов. Штраф - сумма цифр в слове.

Разбор.  Задача навеяна демоверсией ЕГЭ по информатике 2017 года. Последнее время в задачах #27 ЕГЭ часто используются однопроходные алгоритмы. В данной задаче имеется дополнительная техническая трудность, связанная с необходимостью прочитать неизвестно сколько строк. В Паскале эта проблема решается конструкцией вида

while not seekEOF do begin read(...); ...  end;

Для каждой строки извлекаем цифры, суммируем, получаем пару чисел. Чтобы получить минимально возможную сумму по всем строкам, будем брать из каждой пары самое маленькое число. Если полученная при этом сумма будет четной, её необходимо увеличить. Для этого достаточно в одной из пар, где числа имеют разные остатки при делении на 2, заменить ранее выбранное 
число на другое число из той же пары. При этом разница между числами в паре должна быть минимально возможной. Если во всех парах оба числа имеют одинаковый остаток при делении на 2, получить нужную сумму невозможно.

Командный тур. Чемпионы

Командный тур чемпионата по программированию впервые проходил  на платформе Яндекс.Контест. Это сервис для онлайн-проверки заданий по математике и программированию. Здесь https://contest.yandex.ru/contest/4537/standings/ можно посмотреть результаты прошедшего чемпионата. Для участников командного тура открыто дорешивание.
Фотографии с чемпионата здесь.

Немного статистики. 17 команд зарегистрировались, 15 пришли на контест.

4 студенческих команды. Лучшая из них – Trinity: команда магистров 1 курса, 6 место. Первокурсников не было. Очень печально. От второго и третьего курса хотелось бы лучшего результата, но надо признать, выступили достойно, решили столько же задач, сколько и магистры, уступив им по штрафу.


Trinity: Осипов Константин, Гладин Виталий, Лахтионов Александр
5 команд из ТхЛ. Команды сбалансированы по составу. Все команды выступили ровно. Можно сделать предположение, что старшие воспитывают младших. Вполне вероятно, что скоро будет рост результатов.

4 команды от физмат-лицея и 1 команда от лицея народной дипломатии. Тут все интересно. Начну, пожалуй, со сборной команды с очень многозначным названием LA IOI 
Виноградов Олег ДмитриевичГОУ РК ФМЛИ, 11 класс
Зизганова Елена СергеевнаГОУ РК ФМЛИ, 11 класс
Шморгунов Александр АлексеевичГимназия им. А.С.Пушкина, 10 класс
Чистая победа - решили 5 задач из 6. Не удивительно, в команде победители и призеры республиканских олимпиад по информатике. Хотя сначала заставили поволноваться. Не с первой попытки решили самую простую задачу контеста про бригаду грузчиков-огров, затормозили с решением еще одной несложной задачи про красоту эльфийского леса. Наверное, не верили, что все так просто. Но сдали за 20 минут до конца контеста пятую задачу и стали недосягаемы для соперников: "Последний правильный ответ:B,LA IOI,02:41" 

А соперники были. Встречайте племя молодое, незнакомое! Команда Трое из ларца
                 Чекменёв Владимир Дмитриевич, ГОУ РК ФМЛИ, 9 класс
                 Алексеев Валерий Михайлович
, ГОУ РК ФМЛИ, 9 класс
                Александров Максим Андреевич
, ГОУ РК ФМЛИ, 9 класс



4 задачи из 6, 2-е место на контесте. Первыми решили задачу про эльфийский лес и про трудный выбор. Боролись до конца У них 
"Последнее отправленное решение:D,Трое из ларца,02:59". Молодцы! 

3 задачи из 6 у двух команд. 

             LightmassImportanceVolume

                  Попов Антон Дмитриевич, ЛНД, 11 класс
                  Селезнёв Руслан Александрович, ЛНД, 10 класс 
Через 2 минуты после начала контеста сдали задачу про грузчиков-огров. Это как можно? Это с какой скоростью ребята на клавиши жмут? Хотя, если вспомнить, что в составе команды призер республиканской олимпиады по информатике, то начинаешь что-то понимать.

         Мелочь пузатенькая
                  Рябинин Андрей Олегович, ГОУ РК ФМЛИ, 10 класс
                  Зиновьев Илья Сергеевич
, ГОУ РК ФМЛИ, 10 класс
Первыми решили задачу про разбиение гноллов. Настойчивые, сделали 16 попыток решения задачи про трудный выбор, к сожалению, безуспешных. Но это рекорд контеста. 

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







суббота, 13 мая 2017 г.

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


Завершился очередной чемпионат по программированию Сыктывкарского университета. В этом году он впервые проходил на платформе Яндекс.Контест. 
Зарегистрировалось 17 команд, на контест пришли 15. Все команды подтвердили свою квалификацию, решив хотя бы одну задачу.  Победителями признаны первые четыре команды. Им вручили призы и дипломы.


XVIII Open Championship SyktSU
13 май 2017, 16:50:16
начало:13 май 2017, 13:15:00
конец:13 май 2017, 16:15:00
длительность:03:00:00
Участник
A
15/27
B
1/4
C
3/28
D
0/6
E
10/22
F
3/23
Очки
Штраф
1
LA IOI
+1
00:08
+2
02:41
+1
02:22
+
00:35
+1
02:06
5
574
2
Трое из ларца
+
00:19
+2
02:37
-2
02:59
+
00:11
+
01:27
4
315
3
LightmassImportanceVolume
+
00:02
-4
02:58
+
00:19
+1
01:44
3
146
4
Мелочь пузатенькая
+
00:06
+3
02:11
+
00:19
-16
02:46
3
218
5
RandWin
+
00:08
-8
02:54
-4
01:31
+
00:17
2
26
6
Trinity
+
00:18
-3
02:21
+
00:52
2
71
7
ThL_1
+
00:23
+
01:11
2
94
8
ThL3
+
00:39
+
00:57
-1
01:12
2
97
9
Brothers
+3
01:08
+
01:27
-1
02:55
2
215
10
Ежики
+
00:03
-1
00:18
+6
01:39
2
223
11
ThL_4
+
00:14
-6
01:22
1
14
12
Code Monkey
+
00:16
1
16
13
ThL_5
+
00:25
-3
01:42
1
25
14
ThL_2
+
00:31
-1
01:42
1
31
15
HardWind
+8
02:09
1
289