Задача A. Треугольник ≡

Условие

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

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

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

В строке входных данных заданы четыре целых положительных числа, разделенных пробелами — длины палочек. Числа не превосходят 10⁸.

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

Выведите TRIANGLE, если из заданных палочек возможно составить треугольник положительной площади, SEGMENT — если невозможен первый вариант, но можно сложить треугольник, который вырождается в отрезок, если никакой треугольник составить невозможно - IMPOSSIBLE.

Помните, что обязательно использовать три палочки. Ломать или использовать неполную длину палочек запрещено.

Примеры тестов

4 2 1 3

TRIANGLE

7 2 2 4

SEGMENT

3 5 9 1

IMPOSSIBLE

Задача B. Ксюша и массив ≡

Условие

Ксюша — начинающий программист. Сегодня она знакомится с массивами. У нее есть массив a₁, a₂, …, a_n, состоящий из n целых положительных чисел. Преподаватель в университете задал ей задачу. Найти такое число в массиве, на которое делятся все элементы массива. Помогите ей, найдите это число!

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

В первой строке вводится целое число n (1 ≤ n ≤ 10⁵) — количество элементов в массиве. В следующей строке через пробел содержатся целые числа a₁, a₂, …, a_n(1 ≤ a_i ≤ 10⁹) — элементы массива.

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

Выведите единственное целое число — число из массива, на которое делятся все элементы массива. Если такого числа нет, выведите  − 1.

Если существует несколько ответов, разрешается вывести любой.

Примеры тестов

3
2 2 4

2

5
2 1 3 1 6

1

3
2 3 5

-1

Задача C. Роботы ≡

Условие

Сообщество роботов живет по следующим законам:

- каждый год они объединяются в полностью укомплектованные группы по 3 или 5 роботов (причем количество групп из 3 роботов - максимально возможное);

- ни один робот не может существовать вне группы, а также не может входить в состав нескольких групп;

- за год группа из 3 роботов собирает 5 новых собратьев, а группа из 5 - 9 новых собратьев;

- каждый робот живет 3 года после сборки.

Известно начальное количество роботов (К > 7), все они только что собраны. Определите сколько роботов будет через N лет.

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

В строке входных данных задано два целых положительных числа, разделенных пробелами K — количество роботов, N — количество лет.

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

Выведите единственное целое число — количество роботов через N лет.

Ограничения

7 < K < 20

1 < N < 20

Пояснения к примерам

В первом примере из 10 роботов в первый год собираются 2 группы по 5 роботов, т.к. собрать группы из 3-х роботов невозможно. Каждая из двух групп в первый год собирает по 9 роботов. Итого в конце первого года получается 28 роботов. На второй год 28 роботов делятся на 6 групп по 3 робота и 2 группы по 5 роботов. Каждая из 6-ти групп собирает по 5 роботов, каждая из 2-х групп собирает по 9 роботов. Роботов в возрасте 3 лет нет, поэтому от общего количества роботов ничего не отнимаем. Общая схема за два года выглядит следующим образом:

10+2*9=28

28+6*5+2*9=76

Во втором примере общая схема выглядит следующим образом:

0*5+2*9+(10-0)=28

6*5+2*9+(28-0)=76

22*5+2*9+(76-10)=194

63*5+1*9+(194-18)=500

165*5+1*9+(500-48)=1286

427*5+1*9+(1286-128)=3302

1099*5+1*9+(3302-324)=8482

2824*5+2*9+(8482-834)=21786

7262*5+0*9+(21786-2144)=55952

18649*5+1*9+(55952-5504)=143702

В третьем примере общая схема выглядит следующим образом:

5*5+0*9+(15-0)=40

Примеры тестов

10 2

76

10 10

143702

15 1

40

Задача D. Без пробелов ≡

Условие

Коля считает себя самым лучшим программистом в мире. Если его другу Ване нужно напечатать в заданной системе счисления все целые числа, начиная с единицы, то Коля сделает это «в два счѐта». Вот только работает его программа так, что все эти p-ичные числа печатаются подряд без пробелов. Помогите Ване узнать, какая цифра находится на месте с номером n в последовательности слитно записанных чисел. (Напомним, что в системах счисления с основанием, большим 10, в качестве цифр используются цифры от 0 до 9, а также начальные заглавные буквы латинского алфавита A, B, C и т.д.)

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

На вход подаются два целых числа через пробел: p — основание системы счисления (2 ≤ p ≤ 16) и n — номер места определяемой цифры (1 ≤ n ≤ 10¹⁸).

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

Выведите один символ — цифру, которая находится на месте с номером n.

Примеры тестов

10 15

2

15 10

A

Задача E. Идеальная команда ≡

Условие

Для соревнований между ВУЗами формируются команды ровно из трех человек. Однако для идеальной команды необходимо нечто большее. У студента может быть некоторая специализация: кодер или математик. Она/он может не иметь специализации, но иметь обе сразу не может.

Команда считается идеальной, когда в нее входит хотя бы один кодер и хотя бы один математик, и она состоит из ровно трех человек.

Вы тренер команд в одном из ВУЗов и Вы знаете, что cc из Ваших студентов — кодеры, mm — математики и xx не имеют никакой специализации.

Какое наибольшее число полных идеальных команд Вы можете из них составить?

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

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

На вход подаются три целых числа через пробел cc, mm и xx — количество кодеров, математиков и студентов без специализации в университете, соответственно.

Обратите внимание, что ни один студент не является кодером и математиком одновременно.

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

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

Ограничения

(0 ≤ cc,mc,xx ≤ 10⁸)

Пояснения к примерам

В примерах команды составляются следующим образом:

1) единственная команда состоит из 1 кодера, 1 математика и 1 без специализации;

2) все три команды состоят из 1 кодера и 2 математиков;

3) нельзя составить ни одной команды;

4) нельзя составить ни одной команды;

5) одна команда состоит из 1 кодера, 1 математика и 1 без специализации, остальные не могут образовать команду;

6) одна команда состоит из 1 кодера, 1 математика и 1 без специализации, одна из 2 кодеров и 1 математика и одна из 1 кодера и 2 математиков.

Примеры тестов

1 1 1

1

3 6 0

3

0 0 0

0

0 1 1

0

10 1 10

1

4 4 1

3