В кинотеатре «Дружба» через неделю пройдет премьера мирового хита «Осторожный Макс», и шушпанчики обязательно хотят попасть на первый сеанс. Зал в кинотеатре состоит из \(n\) рядов по \(n\) мест в каждом. Ряды пронумерованы от \(1\) до \(n\), места в каждом ряду также пронумерованы от \(1\) до \(n\). Обозначим место с номером \(c\) в ряду \(r\) как \((r, \ c)\).

Шушпанчики точно знают, что лучшее место в зале — место \((r_b, \ c_b)\). Для любого места \((r, \ c)\) можно посчитать неудачность этого места как
\(|r \ − \ r_b| \ + \ |c \ − \ c_b|\), и чем неудачность меньше, тем лучше.

Шушпанчики пойдут на сеанс группой из \(k\) шушпанчиков. Они хотят сидеть рядом друг с другом, поэтому договорились купить \(k\) мест подряд в одном ряду. Таким образом, шушпанчики купят билеты на места \((r_a, \ c_a), \ (r_a, c_a \ + \ 1) \ , \dots, \ (r_a, \ c_a \ + \ k \ − \ 1)\) для некоторых \(r_a\) и \(c_a\).

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

Завершилась Командная Интернет-олимпиада Новой Зеландии по Алгоритмам (КИНЗА). После олимпиады оргкомитет принял решение отправить футболки всем призерам олимпиады. Доставка футболок была поручена компании, в которой работает курьер Билл.

Биллу требуется доставить \(n\) футболок. Он должен доставлять посылки в том порядке, в котором они значатся в его обходном листе. При этом, если посылку доставить не удалось, то в обходном листе ставится отказ, и Билл едет по следующему адресу.

Билл начинает свой рабочий день в офисе компании в момент 0. Приезжая к адресату посылки, он ждет не более \(k\) минут, и если за это время адресат открывает дверь, то Билл отдает ему посылку, процесс передачи посылки без учета времени ожидания занимает \(t\) минут. Если же в течение \(k\) минут дверь не открывается и получатель не появляется, то Билл едет дальше. При этом, если получатель появился ровно ровно через \(k\) минут после приезда Билла, то Билл успевает это заметить, и посылка оказывается доставлена. Рабочий день Билла заканчивается, когда он заканчивает передавать последнюю посылку, либо отмечает в обходном листе отказ от ее получения.

Начальник Билла Джон хочет проверить, насколько добросовестно тот работает. Джону известно, сколько времени ему потребуется на то, чтобы доехать от офиса до первого адресата, а также время на переезд от очередного адресата до следующего. Кроме того, он провел телефонный опрос и знает время, начиная с которого каждый из получателей футболок будет дома. Теперь Джон хочет узнать, в какой момент Билл закончит свой рабочий день.

Сегодня Леша проходил в школе деление столбиком. На дом ему задали вычислить частное двух больших чисел: \(n\) и \(m\). Леша уже попробовал решить пример, но, неожиданно для себя, понял, что \(n\) на \(m\) не делится. Он уверен, что учитель задавал пример, в котором результат не имеет остатка, поэтому он предположил, что допустил ошибку при переписывании примера с доски.

Теперь он хочет исправить несколько цифр в числе \(n\), чтобы оно стало делиться на \(m\). При этом, Леша хочет, чтобы новое число отличалось от записанного у него в минимальном количестве позиций.

Числа, записанные Лешей, не имеют ведущих нулей, он уверен, что числа, записанные на доске, также не имели ведущих нулей, поэтому и в новом числе их не должно быть. Само число 0 при этом является допустимым.

Помогите Леше.

Вася очень силен в подсчёте ворон за окном на уроках математики. Сегодня выдался необычный день, ведь ворон было очень много. К тому же, их было целых два вида: белые и чёрные. К середине урока Вася закончил подсчёт — за окном оказалось \(a\) белых и \(b\) чёрных ворон.

Поскольку до конца урока было невыносимо много времени, Вася решил послушать, что говорит учитель. Как раз в этот момент учитель рассказывал, что такое наибольший общий делитель двух чисел. Вася очень талантливый мальчик и сразу понял, что к чему. Он моментально посчитал наибольший общий делитель чисел \(a\) и \(b\).

После этого он придумал новый термин — милый общий делитель. Милым общим делителем чисел \(x\) и \(y\) Вася решил назвать такое положительное целое число \(d\), что \(x\) делится на \(d\), \(y\) делится на \(d\), а сумма цифр числа \(d\) максимальна.

Помогите Васе найти милый общий делитель чисел \(a\) и \(b\).

Компания «Филипп индастриз» отправила на Марс новый робот-марсоход. Целью робота является исследование поверхности Марса.

Для исследования Марса робот будет перемещаться по поверхности планеты на север и на юг вдоль прямой. Программа робота состоит из \(n\) команд, каждая из которых описывается целым числом \(a_i\) . Каждое число \(a_i\) задаёт количество шагов, которое необходимо сделать роботу. Если \(a_i \ > \ 0\), то робот совершает \(|a_i |\) шагов на север, если \(a_i \ < \ 0\), то \(|a_i |\) шагов на юг. Робот исполняет команды последовательно, начиная с первой.

Однако по пути на Марс робот подвергся космическому излучению и его программа могла повредиться. Запустив процедуру тестирования памяти, ученые выяснили, что в программу было внесено от \(0\) до \(k\) ошибок следующего вида: число \(a_i\) оказалось заменено на \(−a_i\) . Тем не менее, приземлившись на Марс, робот выполнил свою, возможно поврежденную, программу.

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