150 000 рублей за первое место: готовимся к Russian Code Cup, разбирая решения задач предварительного тура

Российский чемпионат по спортивному программированию Russian Code Cup 2017 стартует 19 марта. Талантливые программисты со всего мира вновь будут соревноваться в правильности и скорости решения задач и поборются за призовой фонд в размере 750 тысяч рублей.

Для участия в чемпионате необходимо зарегистрироваться на сайте Russian Code Cup. Соревнования пройдут онлайн. С 19 марта стартует предварительный раунд: участники смогут ознакомиться с платформой и оценить свои силы в решении одной типичной задачи. Участие в этом раунде необязательно, а его результаты не влияют на итоги следующих. Ниже в статье вы найдете разборы прошлогодних задач предварительного раунда.

Основная программа Russian Code Cup традиционно состоит из трех этапов: три квалификационных раунда (2 апреля, 16 апреля и 29 апреля), отборочный раунд (14 мая) и финал (10 сентября). На каждом этапе участникам предстоит решить от четырех до восьми разноплановых задач. Те, кому не повезло в первом квалификационном раунде, могут попытать удачи в следующих. В отборочный тур пройдут по 200 лучших участников с каждой квалификации, а в финале сойдутся 50 лучших программистов.

Победителю чемпионата достанется главный денежный приз в размере 150 тыс. рублей. За второе и третье место конкурсанты получат 100 и 65 тыс. рублей соответственно.

В прошлом году в Russian Code Cup впервые официально вышел на международную аудиторию. Из 4,5 тысяч участников соревнования более тысячи были англоговорящими: в финальном раунде за титул чемпиона боролись жители стран СНГ, Германии, Финляндии, Японии, Швейцарии, Китая и Южной Кореи, — говорит Ольга Августан, руководитель образовательного направления Mail.Ru Group. —Чемпионат проводится уже в седьмой раз, и с каждым годом конкуренция возрастает, а значит на вершину прорваться становится все сложнее и почетнее.

Задания и техническую часть соревнования обеспечивают специалисты Mail.Ru Group и эксперты университета ИТМО. На странице чемпионата можно изучить подробные правила проведения Russian Code Cup.

Задачи предварительного раунда прошлого года

Предлагаем вашему вниманию разборы первых трех задач «разогревочного раунда» 2016 года.

A. Секретный код

Сейчас Марти находится в прошлом и хочет вернуться домой в 1985 год. Он уже влюбил своих родителей друг в друга и нашёл плутоний. Всё, что осталось сделать, — это включить машину времени и отправиться в путь. Здесь Марти ждёт ещё одно испытание. Чтобы включить машину времени, нужно ввести секретный код. Секретный код знает только Док. Марти известно, что все символы, из которых состоит код, различны, а также он знает количество символов. Пока Марти ждёт приезда Дока, он пытается угадать код и вводит различные комбинации символов.

Ваша задача — написать программу, которая для каждого запроса Марти выдает два числа — количество верных символов, которые стоят на своих позициях, и количество символов, которые встречаются в коде, но стоят на неверных позициях.

Формат входных данных
В первой строке находится строка s — секретный код. Код состоит из латинских заглавных букв и цифр, все символы в коде различные.Во второй строке содержится натуральное число n (1 ≤ n ≤ 105) — количество попыток Марти.

В каждой из следующих n строк содержится очередная комбинация, которую вводит Марти. Комбинации также состоят из латинских заглавных букв и цифр. Символы в каждой комбинации различны. Длина каждой комбинации совпадает с длиной секретного кода.

Формат выходных данных

Для каждого запроса Марти выведите два числа a и b, где a — количество верных, b — количество символов, которые встречаются в коде, но стоят на неверных позициях.

Примеры

Входные данные
BACKTO1985
3
BACKTO1958
BACKON1985
TOYEAR1985

Выходные данные
8 2
8 1
4 3

B. Хаос

Расставлять кости домино и наблюдать за их падением — недостаточно интересное занятие для Дока Брауна. Поэтому он придумал более математическое развлечение.

На доске находятся n чисел. Док много раз применяет следующий алгоритм:

• Выбирает три любых числа, написанных на доске, и стирает их.
• Из этой тройки Док выбирает два числа и вычисляет их среднее арифметическое с округлением вниз.
• Затем он пишет на доске два раза полученное среднее арифметическое.

Например, если на доске были написаны числа 1, 2 и 4, то после их удаления с доски, Док может написать две 1 (среднее 1 и 2, округленное вниз), две 2 (среднее 1 и 4, округленное вниз) или две 3 (среднее 2 и 4). Процесс останавливается, когда на доске останутся два числа. Ясно, что эти два числа равны.

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

Формат входных данных

В первой строке задано одно целое число n (3 ≤ n ≤ 105) — количество чисел, написанных на доске.

Вторая строка состоит из n целых чисел ai (1 ≤ ai ≤ 109) — числа, написанные на доске.

Формат выходных данных

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

Примеры

Входные данные №1
3
1 4 2
Входные данные №2
5
3 3 3 3 3

Выходные данные №1
3

Выходные данные №2
3

C. Новое приключение Марти и Дока

После возвращения Дока на поезде из 1885, он воодушевился идеей перевоплощения разных видов транспорта в машины времени, поэтому, недолго думая, переместился в 2015 и сделал машину времени-самолет. Однако во время испытаний у самолета отказали двигатели, и Доку пришлось катапультироваться, а самолет упал в огромное поле и разбился.

Теперь части разбившегося самолета надо собрать и утилизировать. Марти вызвался помочь Доку и нарисовал схему поля. У него получился прямоугольник n × m, в каждой клетке которого лежало несколько частей самолета. Марти решил, что удобнее будет утилизировать все части в одном месте, для этого он предложил построить утилизатор в одной из клеток поля. Собирать части самолета будет робот Дока, он умеет делать три действия:

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

Исходно робот находится в одной клетке с утилизатором.

Теперь главная задача Марти — понять, где надо построить утилизатор, чтобы минимизирновать число действий, которые понадобятся роботу, чтобы утилизировать все части разбитого самолета. Помогите ему с этой задачей.

Формат входных данных

В первой строке даны числа n, m (1 ≤ n·m ≤ 106) — размеры поля.

В i-й из следующих n строк дано описание i-й строки поля — m чисел ai, j (0 ≤ ai, j ≤ 106) — количество частей самолета, расположенных в данной клетке поля.

Формат выходных данных

Выведите три числа: r, c и x (1 ≤ r ≤ n, 1 ≤ c ≤ m) — координаты местоположения утилизатора и количество действий, которое придется сделать роботу. Если оптимальных положений утилизатора несколько, выведите любое из них.

Примеры

Входные данные №1
3 3
0 0 0
0 1 0
0 0 0
Входные данные №2
3 3
2 0 0
0 0 0
0 2 0

Выходные данные №1
2 2 2

Выходные данные №2
2 1 20

В разогревочном раунде 2016 года были также еще задачи D и E. После просмотра условий вы можете также ознакомиться с разборами их решений.

Russian Code Cup входит в число инициатив Mail.Ru Group, направленных на развитие IT-отрасли в России. Наряду с RCC компания проводит чемпионаты Russian AI Cup (кстати, турнир 2016 года недавно завершился и мы пообщались с победителем), Russian Design Cup и Russian ML BootCamp, реализует образовательные проекты Технопарк в МГТУ им. Н. Э. Баумана, Техносфера в МГУ им. М. В. Ломоносова, Технотрек в МФТИ, Техноатом в НИЯУ МИФИ и Технополис в Санкт-Петербургском Политехническом Университете им. Петра Великого.