Задача Baksis

   В абсолютно нам чужой и ужасно коррумпированной стране бригада из N старателей мыла золото, причем каждый ссыпал добычу в свой мешочек. Бригадир, дабы Честные Власти Страны закрыли глаза на их проделки, велел подготовить 2 взятки – Большому Столичному Боссу (БСБ) и Маленькому Местному Царьку (ММЦ). Хитрый Бригадир знал, сколько грамм золота намыл каждый из старателей. Он выстроил их в шеренгу, а затем, руководствуясь Высшими Соображениями, прошел вдоль шеренги от начала до конца, указывая пальцем на тех, кто должен из нее выйти. Первый вышедший делал шаг вперед, а второй – назад, далее, по очереди, вперед-назад. В любом случае количество тех, кто делал шаг вперед равно количеству тех, кто совершал шаг назад. Понятно, что каждый очередной выходящий из строя изначально стоял в шеренге правее предыдущего вышедшего. Количество тех, кто вышел из шеренги, не менее 2-х.
   Далее Хитрый Бригадир велел «передним» отдать свою добычу для взятки Большому Столичному Боссу, а «задним» - Маленькому Местному Царьку. И вот тут-то и стал ясен смысл Высших Соображений: разница между суммами добычи, идущими на взятку Большому Столичному Боссу и Маленькому Местному Царьку, должна быть максимальной. Помогите Хитрому Бригадиру реализовать Высшие Соображения.

 Технические условия

    Программа Baksis читает с клавиатуры число N (2≤N≤32 767), а далее P₁, P₂, ..., P_N (1 ≤ P_i ≤ 100 000) целых чисел , где P_i – добыча старателя, стоящего в шеренге на і-м месте. Шеренга нумеруется от левого края, начиная с единицы. Все числа разделены пробелами.
    Программа выводит на экран единственное число – максимально возможную разность между взятками.

 Примеры

Ввод
 2    10000   1
Вывод
 9999

Ввод
7  7  6  2  4  8  1  5
Вывод
12

Ввод
4  1  2  3  4
Вывод
-1

Задача Lottery

    Есть лотерея, которая проводится по  правилам: играют N (2 ≤ N ≤ 500 000) человек, каждый игрок называет любое K-значное (2 ≤ K ≤ 17) число в системе счисления с основанием M (2 ≤ M ≤ 10). Все числа сравниваются с выигрышным числом, и те игроки, числа которых совпали с выигрышным лишь в 1-ой цифре, получают выигрыш c₁; в 1-ой и 2-ой — c₂ (причем не дополнительно к c₁, а вместо c₁), в 1-ой, 2-ой и 3-ей — c₃ и так далее. Гарантированно, что 1 ≤ c₁ ≤ c₂ ≤ … ≤ c_K ≤ 4000.
   Ведущий лотереи имеет возможность схитрить: не брать выигрышное число случайно, а подобрать его, зная, какие числа назвал каждый из игроков. Какую наименьшую сумму выигрышей ему все же придется выплатить?

 Технические условия

   Программа Lottery должна прочитать с клавиатуры количество цифр в каждом числе K, основание системы счисления M, количество игроков N, а далее N штук K-значных чисел, потом суммы выигрышей c₁, c₂ ..., c_K. Все входные данные записаны в одну строку, любые соседние числа («обычные» или в системе счисления с основанием M) разделены ровно одним пробелом.

   Программа должна вывести на экран два числа через пробел — минимальную сумму, которую все же придется выплатить (ее выводить в десятичной системе), и выигрышное число, которое подбирает ведущий (его нужно вывести как K-значное в системе счисления с основанием M, если нужно — с нулями спереди). Если есть разные выигрышные числа, при которых нужно выплатить одинаковую минимальную сумму, вывести меньшее из них.

 Пример
     Ввод
     2  2  5  00  10  01  00  11  7  35
     Вывод
    42  10
 

Задача Billiard

    У Пети и Васи дома есть большой стол,  поверхность которого  имеет форму эллипса. Ребята иногда играют, катая по его поверхности маленькие металлические шарики. Шарики всегда запускают из некоторых «любимых» точек на краю стола, пытаясь попасть в другие «любимые» точки, тоже на краю стола. Всего таких «любимых» точек имеется N (7≤N≤200 000), и каждая из них может быть стартом или финишем.
    Однажды к ребятам пришли друзья (общее количество детей оказалось равным M, где 2≤M≤10 000, и все решили поиграть в игру. Каждый выбрал для своего шарика «трассу», концы которой размещены в двух (гарантированно разных) «любимых» точках.
     Напишите программу, которая выяснит, удалось ли игрокам выбрать «трассы» так, чтобы они не пересекались (ни внутри стола, ни в «любимых» точках). Программа должна или сообщать, что выбранные трассы действительно не имеют пересечений, или находить любую пару «трасс», которые пересекаются (внутри стола или имеют общий край).

 Технические условия

    Программа Billiard читает  с клавиатуры  два числа: N (7≤N≤200 000) и M (2≤M≤10 000) - количество «любимых» точек и количество «трасс»; дальше M пар натуральных чисел — номера тех «любимых» точек, которые являются концами соответствующей «трассы». Нумерация «любимых» точек начинается с 1 и соответствует порядку обхода вокруг стола по часовой стрелке. Гарантированно, что все «любимые» точки лежат на эллипсе  – крае стола.
    Программа должна вывести на экран два числа через пробел. Если выбранные детьми «трассы» не пересекаются и не имеют общих краев, это должны быть два числа –1. Иначе нужно вывести два натуральных числа — номера любых двух «трасс», которые пересекаются (или имеют общий край). Нумерация «трасс» задается порядком описания этих «трасс» во входных данных. Если возможны разные правильные ответы, вывести любой из них.

 Пример

Ввод
7  3  2  4  7  1  6  3
Вывод
1  3

Ввод
100  2  1  17  42  64
Вывод
-1  -1

Задача Meet

     Лабиринт имеет форму квадрата nxn, который разбит на единичные клеточки. Некоторые клеточки заняты стенами. На двух разных свободных клетках находятся два робота. Роботы одновременно выполняют одну из команд: N - перемещение на одну клетку на север, S - на юг, W - на запад и E - на восток. Если клетка, на которую робот должен перейти, занята стеной или не существует, команда игнорируется, при этом робот остается на месте. За какое минимальное количество команд роботы смогут встретиться (очутиться на одной клетке)?

 Технические условия

   Программа Meet читает из клавиатуры размер лабиринта n (2<=n<=50) и количество занятых стенами клеток К, дальше пары чисел - координаты этих клеток, дальше еще две пары чисел - координаты роботов.
   Программа выводит на экран минимальное количество команд, необходимых для встречи. Если роботы не смогут встретиться, программа выводит -1.

 Пример

     Ввод
     8  6  2  4  3  3  4  6  5  7  7  4  6  3  5  3  2  7
     Вывод
     9

Задача Lucky2

   Назовем натуральное число S-счастливым, если произведение его цифр равно S. Найдите k-е по величине S-счастливое число.

 Технические условия

  Программа Lucky2 читает с клавиатуры через пробел натуральные числа S (2<=S<=1000000) и k (1<=k<=10000).
  Программа выводит на экран искомое число. Если для заданного S ни одного S-счастливого числа не существует, программа выводит -1.

 Пример
     Ввод
     60  5
     Вывод
     435

Задание подготовили Г.Непомнящий, Ю.Пасихов, И.Порублёв