Олимпиада

30 марта 2019 года на факультете ИТ в рамках мероприятия ProFit прошли ежегодные командные соревнования по программированию. Была зарегистрирована 31 команда.

Первое место заняла команда 4 курса спец. ПОИТ (Зайцев, Мартынюк, Чистяков), второе место команда 2 курса спец. ПОИБМС и ПОИТ (Плотников, Голубев, Фандо). Неожиданностью стало выступление студентов 1 курса (Макеев, Злобин, Калоша) занявших третье место.

                   

 Победители -  команда 4 курса специальности ПОИТ (Зайцев, Мартынюк, Чистяков),

 

       

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Команда 2 курса специальности ПОИБМС и ПОИТ (Плотников, Голубев, Фандо)

 

                                   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   Команда 1 курса специальности ПОИТ (Макеев, Злобин, Калоша),

По просьбам студентов рассмотрим задачи:

Условия и тесты можно найти

 http://contester.belstu.by/ru/contest-cid-1396-sh-1?ps=1&smt=1

 

Задача A:    Выбор  

Решение:

В описании задачи явно не указана стратегия.  Преподаватель пытается выиграть и ищет последовательность ходов, которая гарантирует победу. Одна из таких стратегий - попытаться выиграть с наибольшей возможной разницей. Частью его стратегии является предположение, что студент также играет оптимально. После первого хода студента круг разваливается, и у нас остается цепочка чисел. Игроки поочередно берут цифры с двух концов цепочки (они выбирают, с какого конца взять). Предположим, что студент  сделал свой первый ход и осталась  цепочка из N – 1. Пусть f (a, b) наибольшая разница в баллах, которую может достичь игрок, набравший в данный момент (это число может быть отрицательным, если игрок всегда проигрывает), если то, что осталось от цепочки, это числа, изначально имеющие индексы от a до b. Текущий игрок либо берет номер по индексу a и оставляет противника с подзадачей f (a + 1, b), либо он берет номер по индексу b, а у противника остается подзадача f (a, b – 1). Функция f может быть эффективно вычислена для всех пар индексов с использованием динамического программирования.

Имеют место следующие тождества:

• f (i, i) = 1, если число в индексе i нечетное, или 0, если оно четное

• f (a, b) = max {f (a, a) - f (a) +1, b), f (b, b) - f (a, b – 1)}

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

Задача B:    Большие числа  

Решение:

Так как в питоне реализована арифметика с большими числами, то задача представляет собой суммирование и умножение. В других языках: для умножения – количество  нулей в результате является суммой чисел нулей в обоих числах.

Для сложения   - изменится только одна цифра в большем числе: ноль в единицу или в 2. Некоторые не предусмотрели 2-ку. 

Задача С:    Геометрия такси

Решение:

Круг в геометрии такси - это квадрат в правильной геометрии (под углом 45 градусов, если он помещен в декартову систему координат). Таким образом, площадь такого «круга» равна (sqrt (2) · r) 2 = 2 · r2.

Задача D:    Дипломы 

Решение:

Оптимальный алгоритм перестановки будет следующим: выберите диплом с номером K, затем поместите дипломы K, K-1, K-2, ..., 2, 1 (от K до 1) в верхнюю часть стопки. Ниже приводится доказательство оптимальности для такого алгоритма. Если мы сначала поместим диплом с номером K в верхнюю часть, то, несомненно, мы должны будем позже поместить каждый диплом с номером, меньшим K, на верхнюю часть. В противном случае этот диплом окажется ниже диплома K в последнем массиве.Точно так же, если мы ранее положили диплом K сверху во время нашего оптимального алгоритма переупорядочения, никакой другой диплом с номером больше K не стоит ложить сверху, потому что нам пришлось бы снова положить диплом K сверху. Тем не менее, нет смысла перемещать K дипломов сверху дважды. Отсюда следует, что мы не должны ложить любой диплом выше K сверху.Поэтому, если K - это номер книги, которую мы ставим сверху в начале оптимального протокола, мы должны поместить все книги с номером меньше K, и никакой другой книги. Теперь ясно, что эти книги должны быть расположены в порядке от K до 1.После этих перемещений первые K чисел будут от 1 до K, поэтому нам интересно, будет ли отсортирована остальная часть массива, чтобы следовали числа от K + 1 до N. Для этого, все числа, большие K, должны образовывать возрастающую подпоследовательность в исходном массиве, потому что, перемещая числа 1, 2, ..., K, сохраняется относительное упорядочение других чисел.Таким образом, мы можем позволить K быть любым числом таким, что K + 1, K + 2, ..., N образуют возрастающую подпоследовательность в исходном массиве. Ясно, что, поскольку мы ищем решение с минимальным количеством перемещений, мы выберем наименьшее K так, чтобы выполнялись вышеуказанные условия.Обратите внимание, что если K обладает вышеуказанным свойством, то K + 1 также обладает этим свойством, потому что если K + 1, K + 2, ..., N образует возрастающую подпоследовательность, то это также верно для K + 2, K +3, ..., N. Таким образом, мы можем найти минимальное K, используя бинарный поиск, или мы можем проанализировать числа N, N-1, N-2, ... и найдите наибольшее из них, которое не образует убывающую подпоследовательность с предыдущими элементами массива.

Задача E:    Пятнашки

Решение:

 Для каждой буквы мы вычисляем, где она должна стоять. Затем мы суммируем расстояния от начальных позиций всех букв до их текущих позиций. Индексы строк и столбцов позиции буквы можно найти, используя целочисленное деление на 4 (как частное и остаток) от значения буквы ASCII, или  с помощью таблицы -  вручную. 

Задача F:    Слова 

Решение: 

На каждом шаге необходимо отслеживать список всех оптимальных позиций, в которых мы могли бы оказаться после определенного количества шагов. Мы начинаем просмотр с начального поля (0, 0), и на каждом шаге обновляем список, чтобы сначала мы проверили минимальное значение соседей всех позиций в текущем списке, а затем создали новый список, который будет содержать все соседние позиции с этим значением. Поскольку мы можем достичь поля двумя способами, мы должны быть осторожны, чтобы не добавлять одну и ту же позицию дважды в список, потому что таким образом мы будем копировать количество появлений одной и той же позиции в каждой итерации. 

Задача G:   Счастливое число 

Решение:

Учитывая число N, надо найти первую цифру слева, которая нарушает чередующийся паритет, другими словами, тот же паритет, что и предыдущая цифра. У нас есть два варианта:

A. Изменить текущую цифру и оставить все предыдущие цифры без изменений.

 B. Измените цифру, предшествующую этой.

Вариант A состоит из двух под опций: увеличение и уменьшение числа цифр. Если 0, то его можно только увеличить, если 9, то его можно только уменьшить, в противном случае его можно увеличить или уменьшить. Очевидно, что не стоит увеличивать или уменьшать цифру более чем на единицу.

После увеличения или уменьшения цифры, что делать со следующими цифрами? Если мы увеличили цифру, то, соответственно, число будет больше, чем значение N, чтобы получить ближайшее, следующие цифры должны быть как можно меньше: 0101 ... или 1010 ..., в зависимости от четности увеличенной цифры. Аналогично, если мы уменьшили цифру, результирующее число, безусловно, меньше, чем N, поэтому, чтобы приблизиться к ней, следующие цифры должны быть максимально большими: 9898… или 8989…, в зависимости от четности. Конечно, если бы у нас была возможность увеличить или уменьшить цифру, необходимо было бы найти число ближайщее к N между двумя полученными числами. Мы можем сделать это путем вычитания и сравнения различий (в Python есть встроенная поддержка произвольно больших чисел). Ограничения в задаче позволили также рассмотреть вариант B. Однако в этом не было необходимости, потому что вариант B на самом деле никогда не лучше, чем A.

Задача I:  Испорченный телефон 

Решение:

Обратите внимание, что серия занятых столов всегда будет последовательностью. Теперь мы хотим увеличить префикс, добавив нового студента. Мы можем разместить нового  студента за столом p + 1, p + 2,…, p + d, потому что, если посадить его справа от стола p + d, он не будет полезен. Очевидно, что лучше всего посадить студента за стол p + d, потому что таким образом новый префикс будет иметь максимальную длину. Мы реализуем это путем итерации слева направо и отслеживания местоположения последнего занятого стола и размещения нового студента, если разница между текущей позицией и последнего студента равна d. Сложность O (n).

Задача J:  Многоугольник

Решение:

Представьте, что вершины многоугольника помечены от 0 до N-1 последовательно. Рассмотрим диагональ от вершины 0 до некоторой вершины i. Вершины с 1 по i-1 находятся на одной стороне диагонали, а вершины с i + 1 по N-1 - с другой. Диагональ пересекает только те диагонали, у которых одна вершина находится на одной стороне, а другая - на другой. Таким образом, есть (i-1) * (N-1-i) диагоналей, пересекающих ее. Мы считаем все диагонали с одной вершиной, являющейся вершиной 0, и умножаем число диагоналей на n (мы могли бы пометить любую вершину 0 и получить тот же результат). Мы пересчитывали каждое пересечение по одной диагонали дважды (по одному от каждой вершины на одной диагонали) и каждое пересечение в общей сложности четыре раза (потому что оно лежит на двух диагоналях). Следовательно, мы делим результат на 4.

 

Подробный обзор предыдущей командной олимпиады можно посмотреть по ссылке.

Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter