Алгоритмы

Коля очень мечтал поступить в лучший ВУЗ – МГТУ им. Н.Э. Баумана и у него это получилось. Однако, ему не хватило 1 балла для того, чтобы ему предоставили общежитие, потому ему придётся добираться до института на электричках, благо институт находится не только у метро, но и у станции электричек, от которой идти всего 20 минут пешком.
Коля очень пунктуальный мальчик, потому, он каждый раз вечером садится и выписывает расписание электричек на следующий день, чтобы понять, как ему лучше всего добраться до института, чтобы успеть к нужной паре. Но есть проблема, Коле приходится добираться на нескольких электричках, так как он живёт уж очень далеко.
Коля хоть и пунктуальный мальчик, но он, как и все, очень любит поспать, поэтому он решил рассчитать во сколько он доберётся до института в самом оптимистичном случае.
Стоит учесть тот момент, что иногда электрички сбиваются с расписания и могут прийти раньше до 10 минут (включительно), но время в пути у них неизменно.
Помогите Коле рассчитать, во сколько ему нужно встать, по самому оптимистическому сценарию, чтобы приехать к паре вовремя, если известно время начала пары и расписание электричек на каждой станции, с которой он будет отправляться.

Входные данные
На первой строке задаётся время начала пары, к которой Коля должен успеть в формате (hh:mm).
На второй строке задаётся количество станций, с которых будет отправляться Коля (1 <= N <= 10).
На третьей строке задаётся N целых чисел через пробел (1 <= M_1, M_2, …, M_n <= 20) – количество отправлений поездов для каждой станции.
Далее следует N блоков данных по M строк в каждой из которых задано время отправления электрички со станции по расписанию и время в пути до нужной Коле станции (через точку с запятой) (например, 12:10;30, что означает, что электричка отправляется в 12:10, в пути она 30 минут.
Выходные данные
Вывести на одной строке время в формате hh:mm (например, 08:10 или 12:13), в которое Коля должен быть уже на первой станции электричек, чтобы отправиться в институт, притом в самом оптимистичном варианте.
Примечание:
•на вход подаются расписания электричек со станций в порядке,в котором Коля должен на них прибывать;
•гарантируется, что Коля 100% может успеть на пару вовремя.

В маленьком городе N, где нет ни интернета, ни телефонов, живут лучшие друзья Коля, Маша, Саша и Наташа. В очередной зимний день им очень хотелось провести время, играя в какую-нибудь игру, но такую, чтобы игра была не очень быстрой. Потому Маша предложила ребятам сыграть в своего рода модифицированную карточную версию игры «Пьяница» под названием «Круговерть_2».
Правила игры оказались следующими:

• ·игрокам заранее раздают поровну перетасованную колоду из52 карт (четыре масти: червы, бубны, трефы, пики, в каждой из которых 13 карт), таким образом у каждого игрока оказывается своя колода карт, стоящая в виде стопки, расположенной рубашкой вниз;
• ·каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, по порядку слева-направо (первый игрок, второй игрок, третий и четвёртый), далее происходит определение победителей:
•     - если карты одной масти, то побеждает тот, у кого картабыла наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта;
•     - если карты разных мастей, то побеждает тот, у когомасть выше по значению (порядок мастей по возрастанию: червы, бубны, трефы, пики);
•     - если карт высшей масти несколько, то рассматриваетсяопределение наибольшего значения среди этих карт (например, выложили 10 червы, 8 бубны, 7 трефы, 8 трефы, то карты разных мастей, потому выбирается наибольшая масть – в данном случае трефы, таких карт две, среди них самая наибольшая 8 трефы, потому побеждает игрок 4);
• ·победитель забирает четыре карты в свою колоду по порядку,кладя сперва карту первого игрока под низ колоды, затем второго, третьего, четвёртого;
• ·побеждает тот игрок, который заберёт все картыпротивников.

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого будут все 52 карты), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока, у второго, третьего, четвёртого.
Входные данные:
на первых 13 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты второго игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты третьего игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты четвёртого игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

• c – червы;
• b – бубны;
• t – трефы;
• p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

• t – туз;
• v – валет;
• d – дама;
• k – король.

Например:

• (t,10) – десятка треф;
• (c, t) – туз червей.

Выходные данные:
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) минимум у двух игроков останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока, у второго, у третьего, у четвёртого на одной строке через пробел (например, 48 3 1 0).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

В маленьком городе N, где нет ни интернета, ни телефонов, живут лучшие друзья Коля и Маша. В очередной зимний день им очень хотелось провести время, играя в какую-нибудь игру, но такую, чтобы игра была не очень быстрой. Потому Маша предложила Коле сыграть в своего рода модифицированную карточную версию игры «Пьяница» под названием «Круговерть».
Правила игры оказались следующими:
·игрокам заранее раздают поровну перетасованную колоду из52 карт (четыре масти: червы, бубны, трефы, пики, в каждой из которых 13 карт), таким образом у каждого игрока оказывается своя колода карт, стоящая в виде стопки, расположенной рубашкой вниз;

• каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, далее происходит определение, кто заберёт карты:

               - если карты одной масти, то забирает карты тот, у когокарта была наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта; 
               - если карты разных мастей, то забирает карты тот, у когомасть выше по значению (порядок мастей по возрастанию: пики, червы, бубны, трефы);

• забирающий карты забирает обе карты в свою колоду, кладясперва карту противника под низ колоды, затем свою карту также под низ колоды; 
• побеждает тот игрок, который останется без карт.

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого не будет карт), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока и сколько у второго.
Входные данные:
на первых 26 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 26 строках подаются карты второго игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

• c – червы;
• b – бубны;
• t – трефы;
• p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

• t – туз;
• v – валет;
• d – дама;
• k – король.

Например:

• (t,10) – десятка треф;
• (c, t) – туз червей.

Выходные данные: 
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) у всех останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока и у второго на одной строке через пробел (например, 50 2).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

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

1. Объем азотной кислоты должен быть не меньше требуемого для работы;
2. Объем азотной кислоты в лаборатории должен быть минимально возможным;
3. При прочих равных следует предпочесть переноску меньшего количества емкостей;

Напишите программу, которая поможет лаборантам.

Формат ввода
В первой строке программы вводится натуральное число N (N ≤ 20) – количество емкостей с кислотой. Во второй строке указывается натуральное число V (0 ≤ V ≤ 200 л) – ограничение по объему. Далее в N строчках вводится по одному натуральному числу v_i (v_i ≤ 20 л) – объем емкости под номером i.
Формат вывода
Вывести в одной строке через пробел в порядке возрастания объемы емкостей, которые надо отнести в лабораторию, уложившись в заданные условия. Если это невозможно, вывести 0.

В ходе игры «Зарница» Витя и Паша пересылают друг другу важные сообщения. Но для того, чтобы противник не смог их понять, сообщения кодируются. Для кодирования информации ребята используют латинский алфавит из 26 букв, все буквы заглавные. Слова кодируются следующим образом. Каждая буква в слове заменяется ее порядковым номером в алфавите, записанном в системе счисления с основанием Sys (2 <= Sys <= 36). Все полученные числа записываются подряд без пробелов. Если числа (порядковые номера букв) в заданной системе счисления могут иметь разную длину, то более короткие числа дополняются слева нулями до требуемой длины. Например, в десятичной системе счисления порядковый номер буквы A будет равен 1, а буквы Z – 26. Соответственно, при шифровании, к единице слева будет дописан ноль. То есть код буквы A будет 01, а код буквы Z – 26. Для усложнения возможной расшифровки сообщения противником, при кодировании разных слов, могут использоваться различные системы счисления. Основание использованной системы счисления, выраженное двухзначным десятичным числом дописывается справа к коду всего слова.
Например, слово AZ, при использовании десятичной системы счисления, будет закодировано как 012610, а при использовании троичной системы счисления будет закодировано как 00122203.

Напишите программу, которая будет расшифровывать закодированные сообщения.
На вход программе подается одно закодированное сообщение. Длина сообщения не более 100 символов. Программа должна вывести исходное слово.

Город имеет форму круга радиуса R с центром в точке (0,0).
Сеть метро состоит из N линий метро (часть линий или все проходят через город).
Линия метро - ломаная из отрезков прямых, вершины которых имеют целочисленные координаты. Линия метро не имеет самопересечений и может быть замкнутой. Во всех точках с целочисленными координатами, через которые проходят линии метро расположены станции метро .
Для каждой точки с целочисленными координатами определим параметр вес вершины. Вес вершины — это количество станций метро, расстояние до которых не более 1 (длины клетки).
Город разбит на кварталы. Квартал — это единичная клетка с целочисленными координатами вершин, хотя бы одна из которых находящаяся строго внутри города.
Для каждого квартала определим параметр доступность. Доступность квартала равна сумме весов вершин квартала (вершина квартала может быть вне города)
Найдите значение "доступности" для каждого квартала. Для каждой полученной "доступности" определите число кварталов, имеющих эту доступность.
Входные данные
В первой строке заданы значения R, N (4<R<201, 0<N<1001)
В следующих N строках заданы описания линий метро.
Каждая линия описывается следующим образом:
первое число в строке M равно количеству вершин ломаной, далее даны координаты вершин (по два числа на вершину).
Замкнутые ломаные определяются тем, что координаты начальной и конечной вершины совпадают.
Выходные данные
В первой строке выведите число K - количество различных значений "доступности" (включая нулевую).
В следующих K строках выведите по два числа - значение "доступности" и число кварталов, имеющих такое значение "доступности"

Примеры:

 

 

№	Входные данные	Выходные данные	Примечание
1	5 3 6 2 -4 -2 -4 -4 0 0 4 4 0 2 -4 4 -6 3 0 -1 2 -1 5 -4 3 5 4 0 -1 -6 -4	14 0 3 1 1 2 4 3 8 4 10 5 9 6 12 7 11 8 13 9 5 10 6 11 3 12 2 13 1	Город (рис. 1,2) расположен в круге радиуса 5 с центром в точке (0,0). Сеть метро состоит из 6 линий метро (2 радиальных, 1 кольцевая): 6 2 -4 -2 -4 -4 0 0 4 4 0 2 -4 - кольцевая линия из 5 звеньев, 16 станций 4 -6 3 0 -1 2 -1 5 -4 - радиальная линия из 3 звеньев, 8 станций 3 5 4 0 -1 -6 -4 - радиальная линия из 2 звеньев, 9 станций Есть три пересадки ( в вершинах (-3,1), (0,-1), (3,-2)) На рис.1 отмечены вершины, которые не являются станциями и имеют не нулевой вес (треугольник - вес 1, крестик - вес 2, ромб - вес 3) На рис.2 для всех городских кварталов указано значение параметра доступности квартала.

 

В ходе игры «Зарница» Саша и Женя пересылают друг другу важные сообщения. Но для того, чтобы противник не смог их понять, сообщения кодируются. Для кодирования информации ребята используют латинский алфавит из 26 букв, все буквы заглавные. Слова кодируются следующим образом. Каждая буква в слове заменяется ее порядковым номером в алфавите, записанном в системе счисления с основанием Sys (2 <= Sys <= 36). Все полученные числа записываются подряд без пробелов. Если числа (порядковые номера букв) в заданной системе счисления могут иметь разную длину, то более короткие числа дополняются слева нулями до требуемой длины. Например, в десятичной системе счисления порядковый номер буквы A будет равен 1, а буквы Z – 26. Соответственно, при шифровании, к единице слева будет дописан ноль. То есть код буквы A будет 01, а код буквы Z – 26. Для усложнения возможной расшифровки сообщения противником, для кодирования букв, стоящих на разных местах в слове, используются различные системы счисления. Основание использованной системы счисления выбирается исходя из порядкового номера буквы в кодируемом сообщении. Для кодирования первой буквы сообщения используется двоичная система счисления, для второй – троичная, для третьей – четверичная и т.д., до системы счисления с основанием 36 включительно. Далее основания систем счисления повторяются циклически – 2, 3, 4, …36, 2, 3, … Например, слово AZ, будет закодировано как 00001222.
Напишите программу, которая будет расшифровывать закодированные сообщения.
На вход программе подается одно закодированное сообщение. Длина сообщения не более 200 символов. Программа должна вывести исходное слово.

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

Формат ввода
На вход программе в первой строке подается натуральное число N, не превышающее 10000 – количество замеров температуры.
Во второй строке подается натуральное число X, не превышающее 1000 – пороговое значение температуры.
Далее в N строках подается по одному натуральному числу t_i, не превышающему 1000 – температура смеси при измерении номер i.
Формат вывода
Вывести одно целое число – сколько минут длился самый длительный нагрев смеси.

Электронная схема состоит из элементов И и НЕ.
Элемент НЕ имеет один вход и один выход. Принцип его работы следующий: если на входе появится сигнал 0, то через 1 мс на выходе установится сигнал 1, а если на входе 1, то через 1 мс на выходе установится сигнал 0.
Элемент И имеет два входа и один выход. Если на обоих его входах появится сигнал 1, то через 1 мс на выходе установится сигнал 1. Если хотя бы на один из входов поступает 0, то через 1 мс на выходе устанавливается сигнал 0.
Все точки подсоединения элементов пронумерованы. Если в точку поступает сигнал с выходов нескольких элементов, то в этой точке сигнал равен 0 тогда, когда со всех выходов поступает сигнал 0. Если с одного или нескольких выходов, подсоединенных в одной точке, поступает сигнал 1, то в этой точке устанавливается сигнал 1. В последних двух случаях сигнал устанавливается мгновенно (без задержки).
Известно состояние (сигнал 0 или 1) каждой точки в момент включения схемы. Необходимо выдать состояние некоторой указанной точки К в течение первых T мс с момента включения схемы.
В точках, которые соединены только с входами элементов, сигнал остается неизменным с момента включения схемы до окончания ее работы.
Формат ввода
На вход программе в первой строке подаётся натуральное число N. Далее идет N строк, каждая из которых содержит несколько целых десятичных чисел, отделенных друг от друга одним или несколькими пробелами. Первое число в строке показывает, что именно описывают оставшиеся числа данной строки:
0 - описание точки соединения;
   0 m n - точка с номером m имеет в момент включения состояние n (0 или 1)
1 - описание элемента НЕ;
   1 x y - элемент НЕ, вход которого соединен с точкой под номером x, а выход - с точкой под номером y
2 - описание элемента И;
   2 x y z - элемент И, один вход которого соединен с точкой под номером x, второй вход соединен с точкой под номером y, а выход - с точкой под номером z
3 - описание задания.
   3 K T - необходимо выдать состояние точки K в течение первых T мс с момента включения схемы.
Формат вывода
T строк: первая строка - состояние точки K в первую мс, вторая строка - состояние точки K во вторую мс, и так далее до T мс.

Пример
Пусть имеется схема, приведенная на рисунке. Необходимо выдать состояние точки 3 в течение 5 мс с момента включения схемы.

Старшеклассник Миша собирает робота, который должен передвигаться по рельсам вокруг испытательного стенда. Всего робот умеет выполнять 13 различных команд, но для нас представляют интерес три из них – «вперёд», «назад», «стой». Миша решил передавать роботу инструкции в виде цифр числа: робот получает число, переводит его в систему счисления с основанием 13 и выполняет соответствующие цифрам команды. Коды команд, отвечающих за изменение скорости робота, кратны шести.
На вход подаётся N чисел с наборами команд. Сколько раз робот изменит скорость, если считать, что он не встречает препятствий?

Формат ввода
На вход программе в первой строке подается натуральное число N (N ≤ 10000) – количество наборов команд. Далее в N строках на вход подаётся по одному целому числу в диапазоне от 0 до 4*109 – набор тринадцатеричных команд, записанных в десятичной системе счисления.
Формат вывода
Вывести одно целое число – сколько раз робот изменит скорость.

На уроке информатики Фоме задали задачу о проверке гипотезы Гольдбаха.
Условие задачи выглядело так:
Гипотеза Гольдбаха (не доказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел.
Фома легко решил данную задачу методом поиска "первого решения".
Дома, Фома заметил, что во время отладки, он получал решения, в которых одно из чисел было не очень большим.
Так, для числа 1000000, он получил разложение 1000000=17+999983. Фома решил проверить, в чем сложность гипотезы Гольдбаха.
Для этого Фома придумал задачу:
Определим функцию g(n) = количеству разложений числа n в сумму двух простых чисел. (разложения, отличающиеся порядком слагаемых, считаются одинаковыми).
На отрезке натуральных чисел от A до B найдите чётное число x такое, что: g(x) кратно 5 и имеет минимальное значение среди всех g(x) кратных 5 на этом отрезке.
Решите задачу Фомы.

Входные данные
Границы отрезка A, B (два натуральных числа 5≤ A<B≤106 )
Выходные данные
- "Impossible" если для всех чётных x из отрезка [A;B] значение g(x) не кратно 5.
- два числа - x, g( x ) ( g(x) кратно 5 и минимальное для A≤ x≤B). Если таких x несколько, то выведите минимальное значение x.

Примеры

№	Входные данные	Выходные данные	Примечание
1	5 10	Impossible	На отрезке всего три четных числа (6, 8, 10) Число 8 =3+5 и других представлений нет (5+3 считается таким же как 3+5) Для 10 есть два представления (3+7 и 5+5) Таким образом значений x, при которых g(x) кратно 5 нет.
2	20 60	48 5	g(x) может принимать значения меньшие 3 (g(20)=2) g(x)=5 для x из множества {48, 54}. 48 -минимальное значение
3	2000 2005	Impossible

Галактическая станция «Вавилон» имеет N (0 < N <= 10) ангаров для космических кораблей.
Цикл предполетной подготовки длится M (0 < M <= 10) суток. Цикл начинается в тот же момент, как корабль залетает в ангар. До окончания цикла корабль не может покинуть ангар и соответственно начать новый рейс.
Сутки на станции составляют 24 часа. Календарь на станции составляет 365 дней, которые не делятся на месяцы.
Вам попали в руки фрагменты станционного журнала (0 < K <= 1000 строк). В нем фиксируются даты и время прибытия кораблей в зону станции, а также заявки на рейсы со станции. Гарантируется, что все страницы относятся к одному году.
Если корабль подлетает к станции, а все ангары заняты, то ему отказывают в обслуживании. Если вылет со станции назначен на тот же час, что и прилет нового корабля, будем считать, что сначала ангар освобождается, а потом новый корабль размещается в пустом ангаре (начало цикла будет считаться с момента прилета).
Если приходит запрос на рейс со станции, то в рейс уходит тот корабль, который готов к вылету. Если таких кораблей несколько, то выбирается тот, который дольше находится на станции. Если готовых к рейсу кораблей нет, то рейс задерживают и ждут, когда появится корабль, который пройдет цикл предполетной подготовки. Если до конца периода кораблей для выполнения рейса не найдется, то заявка считается НЕ задержанной, а отклоненной.
По данным журнала определите скольким кораблям было отказано и сколько рейсов было отклонено в рассматриваемый период.

Входные данные:
В первой строке через пробел три числа N M K.
Дальше K строк в формате
День Час Признак
Где День – это номер дня от начала года; Час – час события; Признак это 1, если корабль прилетает, -1, если это запрос на вылет.
Выходные данные:
Два целых числа, каждое на новой строке:
– количество отказов в обслуживании;
– количество отклоненных заявок.

Примечание
В журнале 9 записей.
1) 1 9 1
2) 8 12 -1
3) 6 15 -1
4) 6 12 -1
5) 2 18 1
6) 5 6 1
7) 6 12 1
8) 7 12 -1
9) 2 21 1
Корабли, прибывшие 1-го в 9:00 и 2-го в 18:00, были поставлены в два ангара, имеющиеся на станции (1-ая и 5-ая строки журнала).
6-го числа в 12:00 1-ый ангар покинул корабль по заявке из 4-ой строки журнала. В тот же момент его место занял корабль с 7-ой строки.
На момент прилета кораблей из 6-ой и 9-ой строк оба ангара были заняты. Эти корабли получили отказ.
Выполнение заявок с 3-ей и 8-ой строк журнала было задержано, так как не было готовых к вылету кораблей.
Заявка со 2-ой строки была отклонена, так как в ангарах и на подлете в рассматриваемый интервал времени кораблей не было.

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

Формат входных данных
На вход программе в первой строке подаётся натуральное число N (N ≤ 1000) – количество игроков. Далее в N строках идёт по одному натуральному числу k_i – рейтинг ELO игрока номер i (1 ≤ k_i ≤ 2500).
Формат выходных данных
Выведите одно целое число – ELO, начиная с которого, игроки попадают в высшую лигу. Если в высшей лиге окажется весь турнир, надо вывести наименьший ELO среди заявленных игроков.

Пояснение
Всего пять игроков, значит, в высшей лиге должно быть не меньшедвух. 1750 – точно в высшей лиге. 1600 надо брать в высшую лигу, но их два. Значит, оба идутв высшую лигу, после чего она набрана.
 

Заданы два различных целых положительных числа a и b, записанные в восьмеричной системе счисления. Оба числа двузначные. В условии данной задачи в двузначном числе старшая цифра может быть и нулем.
В двузначном числе за один ход разрешается заменить любую цифру на сумму цифр по модулю 8 (остаток от деления суммы цифр на 8). Построить цепочку ходов минимальной длины, которая переводит a в b. Если существует несколько цепочек минимальной длины, то выбрать ту из них, в которой сумма всех чисел максимальна (числа a и b являются частью цепочки). В качестве ответа записать сумму чисел в найденной цепочке. Результат записывается в десятичной системе счисления. В случае невозможности построить цепочку вывести число 0.

Формат входных данных
На вход программе подается строка, содержащая два целых положительных восьмеричных двузначных числа a и b, записанные через пробел.
Формат выходных данных
Вывести целое десятичное число – сумму чисел в найденной цепочке.

Находясь в агрессивной среде аппарат, снабженный целым комплексом датчиков, мониторит сразу несколько параметров. Необходимо написать программу анализа для параметра F. Этот параметр принимает целые значения. Задан диапазон допустимых значений [X; Y] (границы отрезка тоже являются допустимыми значениями). Каждую минут снимаются показания с датчика F. После выключения оборудования датчик показывает 0. Это значение в серию измерений уже не включается. Необходимо посчитать наибольшее отклонение от допустимых значений и сколько раз за время наблюдения оно было зафиксировано.

Формат входных данных
На первых двух строчках вводятся два целых числа X и Y (X < Y), которые задают диапазон допустимых значений.
На последующих строчках вводятся целые числа (по одному в каждой строке) – показания параметра F, передаваемые аппаратом. Последнее значение 0 – признак выключения аппарата – это значение в показания НЕ включается.
Все числа по модулю не превосходят 1 000.
Гарантируется, что хотя бы один выход из допустимого диапазона значений был.
Формат выходных данных
Два целых числа в одной строке через пробел: максимальное отклонение и количество отклонений на такое значение за время наблюдения.

Примечание
В данном примере 11 измерений. Максимальное отклонение 2 от заданного допустимого диапазона [-4; 11] будет достигнуто 3 раза на значениях -6, 13 и 13
|-6 – (-4)| = |13 – 11| = 2

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

Формат входных данных
На вход на первой строке подаётся число X (1 <= X <= 100000) – длина дороги в метрах.
На второй строке подаются числа W, H (1 <= W,H <= 100) – высота и ширина жителя-прямоугольника в метрах соответственно.
На третьей строке подаётся число N (1 <= N <= 1000) – количество ям на дороге.
Далее на N-строках подаются координаты начала ямы (в метрах от начала дороги) и её ширина в виде целых положительных чисел от 1 до X. Координаты ям могут подаваться в любом порядке. Но все ямы не пересекаются и не накладываются.
Формат выходных данных
Выведите на первой строке количество ям, которые необходимо заделать, чтобы житель-прямоугольник, для которого производится расчёт, смог добраться до конца дороги.
Далее выведите координаты всех ям отсортированные в порядке появления от начала дороги до конца, КАЖДУЮ С НОВОЙ СТРОКИ.

Примечание
Житель-прямоугольник перед стартом дороги находится так, что три его вершины находятся за пределом начала дороги, а одна вершина, являющаяся самой правой, стоит на позиции 0. Первоначальное положение жителя-прямоугольника может быть любым, нужно выбрать оптимальное, чтобы залатать как можно меньше ям.
Если решений несколько, выведите то, в котором сумма координат ям для залатывания наименьшая.

В данном случае житель может стоять основанием перед началом дороги на стороне 2 (положение №1) или 3 (положение №2).
Если он стоит на основании длиной 2, то он попадёт только в яму под номером 14.
Если он стоит на основании длиной 3, то он попадёт в ямы 10 и 14.
Городу выгоднее заделать только одну яму, под номером 14.

Положение №1.


Положение №2.

 

В школе №1920 решили провести соревнование по написанию небольших игр среди школьников. Первым критерием данного соревнования было условие того, что в игре нельзя заранее рассчитать результат зная входные данные.
Коля написал игру, в которой задаётся квадратная матрица, состоящая из целых чисел, но не содержащая нулей. Суть игры в том, что в неё играют два участника и каждый может сделать одно из следующих действий:
1.Повернуть матрицу на 90 градусов по часовой стрелке
2.Повернуть матрицу на 90 градусов против часовой стрелке
3.Повернуть матрицу на 45 градусов по часовой стрелке (если есть нули,то они схлопываются (см. пример))
4.Повернуть матрицу на 45 градусов против часовой стрелке (если естьнули, то они схлопываются (см. пример))
У игроков есть ограниченное чётное количество ходов. Каждый из игроков ходит по очереди. Победой в игре считается сумма чисел на ближайшей стороне матрицы, которая находится ближе к игроку. Если матрица в конце повёрнута на 45 градусов, то результатом берётся ближайший угол матрицы к каждому из игроков (одно число в вершине).
Помогите Коле написать алгоритм, который будет по входной матрице и порядку действий ребят определять сколько очков набрал игрок №1 и игрок №2.
Поворот квадратной матрицы на 45 градусов по часовой стрелке будет выглядеть следующим образом.

Формат входных данных
На вход первой строкой подаются число N (1 <= N <= 1000) – размер исходной сгенерированной квадратной матрицы (N – количество строк). Далее на N строках подаются по N целых чисел (кроме нуля).
Далее подаётся число K (2 <= K <= 100, K – чётное)– количество ходов у игроков.
На последующих K-строках вводятся команды, которые выбрали ребята (от 1 до 4), где первая команда соответствует первому игроку (сидящему слева), следующая команда второму (сидящему справа) и так далее.
Формат выходных данных
Вывести на одной строке через пробел результат игры для первого игрока и для второго.

Примечание:

1	2	3
4	5	6
7	8	9

1 команда (повернуть на 90 градусов по часовой стрелке)

7	4	1
8	5	2
9	6	3

2 команда (повернуть на 45 градусов по часовой стрелке)

0	0	7	0	0
0	8	0	4	0
9	0	5	0	1
0	6	0	2	0
0	0	3	0	0

3 команда (повернуть на 90 градусов по часовой стрелке)

0	0	9	0	0
0	6	0	8	0
3	0	5	0	7
0	2	0	4	0
0	0	1	0	0

4 команда (повернуть на 45 градусов против часовой стрелке (нули схлопываются))

9	8	7
6	5	4
3	2	1

Первый игрок находится слева, значит ячейки, которые идут ему в счёт 9 + 6 + 3.
Для второго игрока справа 7 + 4 + 1.
 

В школе в очередной раз заболел преподаватель физкультуры Виктор Дмитриевич. Поэтому директор принял решение, что кто-то из свободных учителей проведёт занятие. После долгих размышлений, самым свободным оказался учитель информатики Анатолий Иванович, который очень любит алгоритмы сортировки, что вызвало сразу проблему у учеников. Ведь Анатолий Иванович первым делом сказал ребятам построиться в шеренгу, но не как обычно (по убыванию роста, ), а так, чтобы каждое нечётное место было отсортировано по росту по убыванию (первое место - самый высокий ученик, третье место выше пятого, пятое выше седьмого и так далее)), а каждое чётное по возрастанию (второе место - самый низкий ученик, четвёртый второй по росту среди всех, шестой - третий по росту среди всех и так далее) (учеников Анатолий Иванович нумеровал с 1).
Помогите ученикам получить правильный порядок, как встать им в шеренгу так, чтобы Анатолий Иванович оказался доволен.
Формат входных данных
На первой строке подаётся число N (1 <= N <= 121)– количество учеников в классе.
На N последующих строках подаются строки вида имя-рост (например, «Ivan 175»), где на первом месте указывается имя ученика – оно всегда одним словом на английском языке, без пробелов, а в конце указывается рост ученика (целое число от 100 до 220).
Формат выходных данных
Выведите имена учеников в одну строку через пробел, как они должны встать на уроке физкультуры.
Примечание:
Имена учеников у всех уникальны, рост ни у кого не повторяется.

В королевстве Полерам расположен длинный линейный сад из N деревьев, стоящих в один ряд (по порядку с запада на восток). У каждого дерева i (нумерация от 1 до N) имеется некоторый урожай a_i — количество собранных яблок (целое число, может быть положительным, нулевым или даже отрицательным, если учитывать затраты или потери).
Королевский интендант хочет упаковывать собранный урожай в большие ящики, рассчитанные ровно на K яблок. Для удобства он рассматривает непрерывные отрезки деревьев [L,R] и проверяет, делится ли сумма (a_L )+ (a_L+1) + … + (aR) на K без остатка. Если делится, то такой отрезок можно упаковать в ящики без недогруза и перегруза.
Требуется найти общее количество таких отрезков [L,R], для которых сумма урожая деревьев на этом участке кратно K, количество яблонь нечётное, а количество собранных яблок - положительное число.
Примечание:
В отрезке [L, R] должно быть выполнено неравенство 1<= L <= R <= N.
Формат входных данных
Первая строка: два целых числа N и K, (1 <= N <= 200000, 1 <= K <= 10⁶).
Вторая строка: N целых чисел a₁, a₂, …, a_N (-10⁶ <= a_i <= 10⁶).
Формат выходных данных
Выведите одно число — количество всех пар (L, R) для которых (a_L )+ (a_L+1) + … + (a_R) делится без остатка на K, количество яблонь нечётное, а количество собранных яблок - положительное число.

Пояснение: в данном примере есть четыре последовательности: (1 + 2), (1 + 2 + 3), (3), (6), в данном случае все с положительным количеством собранных яблок, но только 3 с нечётным количеством яблонь.

Саша и Маша живут в разных домах одного района. Их дома находятся возле пруда в форме квадрата. Однажды глава района предложил жителям нарисовать тропинки, которые они хотели бы видеть в своём районе, чтобы в дальнейшем проложить их. Потому ребята решили рассчитать самый короткий маршрут, который может быть, чтобы пройти от одного дома к другому. На изображении ниже представлен вариант расположения пруда и двух домов ребят (зелёная точка и оранжевая). Требуется рассчитать, какое самое кратчайшее расстояние требуется им преодолеть, чтобы оказаться друг у друга в гостях.


Примечание:

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

Формат входных данных
На первой строке подаются параметры пруда через пробел a, x1, y1 (1 <= a <= 1000; -1000 <= x1,y1 <= 1000), где x1,y1 – координаты левого верхнего угла пруда.
На второй строке подаются координаты дома Маши в виде точки xm, ym (-1000 <= xm, ym <= 1000).
На третьей строке подаются координаты дома Саши в виде точки xs, ys (-1000 <= xs, ys <= 1000).
Все числа - целые.
Формат выходных данных
Выведите на одной строке самое кратчайшее расстояние, которое можно пройти от дома Маши к дому Саши. Ответ представляет собой всегда вещественное число с одним знаком после запятой. Если ответ получился больше, то округлить до одного знака после запятой (было 4.5764, стало 4.6).