Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Решения и комментарии к задачам секции А

 

Условия секции «Алгоритмические задачи» были сформулированы так, чтобы участники турнира смогли продемонстрировать не только знание языков программирования и умение реализовывать достаточно сложные алгоритмы, но и провести исследование, насколько тот или иной способ годится для решения конкретной задачи, составить тесты, способные с высокой долей вероятности подтвердить корректность вычислений. Также в некоторых задачах участникам необходимо было самим сформировать ограничения на входные данные, исходя из математического, физического, географического (да и просто здравого) смысла задачи. Это и отличает Турнир от обычных олимпиад по программированию.

Разбор задач предлагается начать с самой простой. Как и прогнозировалось, ею стала задача про функцию.  (Рейтинг сложности 2,23. Максимальный набранный балл 30)

А3. Загадочная функция

 Рассмотрим дискретную функцию F(n1,n2,...,nM),  где n1, n2,...,nM — целые и 1<=n1,n2,...,nM<=M,  1<=M<=100. Функция задана на всей области определения следующим образом: F(1,2,3,4,...,M-1,M)=1 и  F(n1,n2,...,nM) меняет знак при перестановке любых двух аргументов: F(n1,...,nI,...,nJ,...,nM)= -F(n1,...,nJ,...,nI,...,nM) .

Например:  F(1,2,3,4,...,M,M-1)= -1.

Вычислить сумму S всех возможных квадратов F(n1,n2,...,nM)2.

Ввод:      M

Вывод:  S

 

Практически все участники решили, что S=M! .  При этом у некоторых значение F() от повторяющихся (равных) аргументов (F(1,1,2)) просто отбрасывалось,  как «незаданное в условии». Разумеется, такой подход не верен. Из двух фактов ( F(1,2,3,4,...,M-1,M)=1 и  F(n1,n2,...,nM) меняет знак при перестановке любых двух аргументов: F(n1,...,nI,...,nJ,...,nM)= -F(n1,...,nJ,...,nI,...,nM)) прямо следует F(1’,1’’,2)= F(1’’,1’,2)=0. Также из них следует, что при неповторяющихся аргументах |F()|=1 и значит при возведении в квадрат получим 1 столько раз сколько перестановок последовательности 2,…,M существует, то есть M! Однако, по условию M≤100 следовательно S(100) не поместится в стандартные целочисленные типы данных (содержит по крайней мере >100 десятичных знаков, но < 200). Поэтому придется реализовывать собственную длинную арифметику. Это уже стандартная задача по программированию и примеры реализации алгоритма можно найти во многих источниках. Стоит заметить, что использование чисел с плавающей точкой не приемлемо, так как они округляют результат

Следующая задача о замечательных числах. (Рейтинг сложности 2,27. Максимальный набранный балл 29)

A6.Замечательные числа

Число  R = pnpn-1...p1 (pi-цифры) называется замечательным тогда и только тогда, когда число Q= pmpm-1...p1, состоящее из последних m цифр числа R — простое (для любого m<= n). Число  Q может иметь произвольное число нулей в начале. ДаноцелоечислоS(1<=S<= 32000). Найти все замечательные числа меньшие S.

Ввод:      S

Вывод:  В первой строке число замечательных чисел, а на следующей строке — сами числа, в возрастающем порядке.

 

Задача решается в 2 этапа.

Вначале необходимо найти все простые числа. Для этого используется алгоритм «решето Эрастофена». Простые числа записываются в массив. Первое простое число – 2. Очередное нечетное число N проверяется на простоту по остатку от деления его на не превосходящие квадратного корня из N числа из массива простых чисел.

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

При этом необходимо учитывать случаи, когда S-однозначное число, S=1, числа, содержащие 0 в середине (103)  и т. д. Достаточно распространенной ошибкой был вывод чисел ≤S (по условию <S).

Необходимо указать, что было несколько решений, которые использовали уже готовый массив замечательных чисел. Сам массив описывался либо как константа, либо заполнялся из вспомогательного файла. Решением Жюри результаты работы подобных программ не засчитывались, так как (фактически) это являлось некоторым жульничеством, (формально) не выполнялось условие задачи (найти числа != только вывести их).

 

Разминочная задача А0 завершает тройку легких задач (Рейтинг сложности 2,49 Максимальный балл 38)

А0. Сосуды

В вашем распоряжении два сосуда A и B емкостью M и N литров соответственно. Написать программу, показывающую последовательность операций, с помощью которой можно получить в одном из сосудов Q литров жидкости. M , N , Q — целые положительные числа меньше 100. Разрешены операции:

1.        Опорожнение сосуда — (A–, B–);

2.        Наполнение сосуда до отказа — (A+, B+);

3.        Переливание из сосуда в сосуд, пока первый не опорожнится или второй не наполнится — (A–>B, B–>A)

Ввод:      три числа M , N и Q, разделенные пробелом.

Вывод: последовательность действий. Каждый шаг в новой строке. Если невозможно, вывести «NO».

Дополнительное задание: Выполнить задание минимумом действий.

 

Написание программы мало у кого вызвало затруднение. Чего нельзя сказать про алгоритм.

Внимательное обдумывание алгоритма позволяет установить, что имеются лишь 2 пути поиска последовательности: начинать с сосуда А или с сосуда Б. Рассмотрим первый путь: на каждом шаге сначала либо заполняем А, если он пуст, либо опустошаем Б если он полон, а потом делаем переливание из А в Б. Аналогичная (с точности до симметрии) процедура для второго пути.

Пока не был сформулирован критерий существования решения. А без него наша процедура может продолжаться бесконечно, что приведет к зависанию программы.  Помимо тривиального случая, когда Q>M,N следует учесть делимость Q на НОД(M,N).

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

Задача про выбор передач (Рейтинг сложности 3.2 Максимальный балл 26)

A4. Программа передач

Телепузик очень любит днем смотреть интересные передачи по телевизору. Беда в том, что очень часто они идут в одно и то же время по разным каналам. Помогите ему просмотреть наибольшее их количество (полностью!). Примечание: считать, что если одна передача заканчивается в 10:00, а другая начинается в 10:00, то можно посмотреть обе.

Ввод:     N (0<N<1000) строк формата ЧЧ:ММ ЧЧ:MM название  (время начала и окончания передачи, название короче 10 символов).

Вывод: M строк с названиями передач, которые Телепузик посмотрит (названия передач не повторяются).

 

Задача решается при помощи «жадного» алгоритма. Отсортируем программы в неубывающем по времени окончания порядке. Затем каждый раз выбираем подходящую передачу с наименьшим временем окончания. Задача похожа на классическую задачу о непересекающихся отрезках.

Задача про точки и окружности оказалась немногим сложнее (Рейтинг сложности 3,27 максимальный балл

A 5. Окружности

На плоскости заданы N различных точек посредством пары целых декартовых координат. Необходимо определить максимальное число M точек,черезкоторыеможнопровести(одну)окружность.Ограничения:-1000<=Xi,Yi<= 1000и1<=N<=16. Вычисления производить с абсолютной точностью.

Ввод:      В первой строке число N. В следующих N строках по два действительных числа, отделенных пробелами — координаты Xi,Yi.

Вывод:  M

 

Задача решается перебором. Но не простым. Если проверялось принадлежность точки D окружности, образованной точками А, B, С, то выполнять проверку принадлежности точки D окружности BAC, CAB, точки В окружности ACD и т. д. не стоит.

Что касается  проверки принадлежности точки окружности, то здесь существует несколько способов: находить центр окружность, используя серединные перпендикуляры; использовать свойство углов вписанного четырехугольника (сравнивать косинусы углов, найденные по теореме косинусов)

 

Задача про чиновников (Рейтинг сложности – 3,6. Максимальный балл – 30)

А2. Коррумпированное государство

В тридевятом царстве в тридесятом государстве для получения лицензии на проведение любых исследований необходимо разрешение председателя Комиссии по наукоемким технологиям. В комиссии N<=100 чиновников. Соответственно, у каждого чиновника (кроме самого главного №1) есть 1 непосредственный  начальник и могут быть подчиненные (как непосредственные, так и подчиненные его подчиненных).  Согласно естественным правилам бюрократической системы каждый чиновник, кроме самых младших, на заявлении может потребовать на заявлении подписи одного или нескольких своих прямых подчиненных и взятку, как за то, чтобы можно было обойти нижестоящих чиновников, так и просто за свою подпись.  Для каждого чиновника известен непустой список возможных наборов «виз» (подписей своих подчиненных) и соответствующая каждому набору взятка (достаточно наличие только одного набора). Пустой набор означает, что данный чиновник не требует виз в данном случае. В какую минимальную сумму обойдется лицензия на проведение исследований?

Ввод:     Ν , в следующих строках: <номер чиновника (1..N)> <взятка — целое число меньше 10000> <набор виз (может быть пустым) — номера чиновников, разделенные пробелом> (Замечание: для каждого чиновника можно записать несколько таких строк). Количество виз в наборе не превосходит 50. Количество наборов для каждого чиновника не превосходит 15.

Вывод:              <Сумма взяток>

  Задача решается методом «Динамическое программирование». При помощи рекурсии (или другим обходом) заполняется массив минимальных сумм взяток, заплаченных, чтобы получить подпись данного чиновника. В конце получаем ответ.

Типичными ошибками является использование типа integer(16bit) для хранения суммы, что приводит к отрицательным значениям из-за переполнения, а у некоторых участников и к зависанию программы.

Некоторые писавшие на Паскале столкнулись с проблемой нехватки памяти. Для ее решения можно было воспользоваться «кучей» (Heap) или же просто аккуратно продумать структуру данных.  

 

И, наконец, самая сложная задача Турнира (Сложность 6,9 Максимальный балл – 22)

А1. Освоение полюса

Один из проектов глобального исследования и освоения полярной шапки предполагает создание некоторого количества (до 50) станций, расположенных по всей территории ледника. При переезде от одной станции к другой необходимо составлять маршрут, так чтобы расстояние между соседними станциями-остановками не превышало (≤)Х км. Считать пути между соседними станциями прямыми. Найти К(<100) самых коротких путей от станции А до станции B и вывести их в неубывающем по длине порядке. Если количество путей не превышает К, найти  их все.

Ввод:      N — кол-во станций, A, B, K, X. Затем N пар целых чисел — координат (в км) станций. Все числа разделены пробелами или символами новой сроки.

Вывод:  K (или, если количество путей M<K, то М) различных маршрутов, представляющие последовательность номеров станций, начиная с начальной и заканчивая конечной. Станции отделяются пробелами, маршруты — символами новой строки.

 

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

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

В итоге получаем классическую задачу на нахождения К кратчайших путей в графе. Здесь рекурсия будет достаточно неэффективной и решение ищется, как правило, алгоритмом Йена, которых достаточно хорошо описан в различных книгах по программированию и в Интернете.  Алгоритм достаточно сложный, в данной задаче можно использовать алгоритм Флойда, хотя последний и менее эффективный.

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

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика