Информатика

Найдите сумму пяти заданных чисел. 

Формат входных данных
В первой строке записаны три целых числа a, b, c, разделенных пробелом. Во второй строке записаны два целых числа d, e, разделенных пробелом.

Формат выходных данных
Выведите сумму всех целых чисел, т.е. выведите a+b+c+d+e.

У свинофермера Васи есть свиноферма рядом с городом М. Он решил навестить своего друга в городе С.-П. По дороге из М. в С.-П. расположено N городов, в которых свинина пользуется стабильным спросом. Вася решил совместить приятное с полезным и заработать немного денег. Он взял с собой N свиней и решил продавать по одной свинье в каждом из городов.

Цены на свиней в разных городах разные. В j-ом городе за один килограмм живого веса платят P_j рублей. Расстояние до j-го города по дороге из М. в С.-П. равно D_j километров.

Васины свиньи имеют разные веса. Перевозка одного килограмма свиньи на один километр обходится в T рублей.

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

Входные данные
Первая строка входного файла содержит числа N(1≤N≤1000) и T(1≤T≤10⁹). Вторая строка содержит N чисел W_i, задающих вес Васиных свиней (1≤W_i≤10⁹). Третья строка содержит N чисел D_i, задающих расстояния до города i от М(1≤D_i≤10⁹). Четвертая строка содержит N чисел P_i, задающих цены в городах (1≤P_i≤10⁹). Все числа целые.

Выходные данные
Выведите N чисел. j-ое число должно быть номером свиньи, которую следует продать в j-ом городке. Свиньи нумеруются с 1 в том порядке, как они перечислены во входном файле.

В операционной системе Xunil информация обо всех файлах и директориях хранится в специальном файле в следующем формате:

emoh

 vonavi

  a.doc

  b.doc

 vortep

  .bashrc

 vorodis

  onrop

   1.avi

   2.avi

rav

 bil

 

Имена файлов, и только они, содержат точку.

Требуется по данному имени файла найти путь к нему. Если таких файлов несколько, вывести путь к файлу, который записан выше.

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

Выходные данные
Выведите путь к файлу в формате /директория/директория/…/файл

Гарантируется, что такой файл есть.

Гарантируется, что длина строки ответа не превосходит 255.

Бегемот – это шахматная фигура, которая живет на доске размером 100x100 клеток. За один ход бегемот перемещается на n клеток по горизонтали или вертикали и на m клеток в перпендикулярном направлении. Например, шахматный конь – это бегемотик, у которого n=2, m=1 (или наоборот). Раскрасьте доску, на которой живет бегемот, в два цвета (каждую клетку – в один из двух цветов), так чтобы любой ход из любой клетки приводил бегемота в клетку другого цвета.

Входные данные
Вводятся два натуральных числа n и m, не превосходящие 99.

Выходные данные
Выведите 100 строк по 100 цифр – 1 или 0, обозначающих клетки разного цвета (через пробел).

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

Входные данные
В первой строке вводится количество ящиков – натуральное число, не превышающее 100. В следующих строках вводятся размеры ящиков: в каждой строке вводятся три натуральных числа, не превышающие 101 – размеры очередного ящика.

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

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

Система Интернет-банкинга Bank 2.0, используемая одним Очень Крупным Банком, использует следующий способ ввода пароля. Серверной частью системы случайно генерируются n строк s₁,…,s_n, каждая из которых состоит из m строчных букв латинского алфавита (предполагается, что пароли состоят только из таких букв).

При вводе пароля пользователю разрешается выполнять такую операцию: выбрать из данных строк две (обозначим их как s_i и s_j, 1 ≤ i,j ≤ n, i≠j) и некоторую позицию k (1 ≤ k ≤ m) в них, после чего поменять местами k-е символы в s_i и s_j. Например, если s_i=abcde, s_j=vwxyz, k=3, то после выполнения этой операции будут верны следующие равенства: s_i=abxde и s_j=vwcyz. Для ввода пароля пользователю необходимо за минимальное число таких операций добиться состояния, в котором хотя бы одна из строк s₁,…,s_n совпадает с p.

Ваша задача состоит в том, чтобы написать программу, которая по заданному набору строк s1,…,sn и паролю пользователя p определит минимальное число операций указанного типа, которые необходимо выполнить для ввода пароля, а также найдет способ ввода пароля за такое число операций.

Входные данные
Первая строка содержит целое число n (2 ≤ n ≤ 100). Каждая из последующих n строк содержит строки s₁,…,s_n. Все они состоят только из строчных букв латинского алфавита и имеют одинаковую длину m (2 ≤ m ≤ 100).

Последняя строка содержит пароль пользователя p. Его длина равна m, и он состоит только из строчных букв латинского алфавита.

Выходные данные
Первая строка должна содержать минимальное число c операций, необходимых для ввода пароля. Если с помощью описанных в условии операций пароль ввести нельзя, то выведите в первой строке "−1".

В случае существования решения следующие c строк должны содержать описания операций. Операции должны быть перечислены в порядке их применения, каждая из строк должна содержать три целых числа: i, j и k (1 ≤ i,j ≤ n, i≠j, 1 ≤ k ≤ m). Эти числа означают, что соответствующая операция состоит в обмене k-ых символов строк s_i и s_j.

Приехав в Хоббитанию, белый маг Гэндальф принялся рассказывать Бильбо последние новости из Средиземья. Больше всего впечатлительного хоббита поразил рассказ о Большом огромном коллайдере - только представить себе гигантских размеров кольцо, зарытое под землей!

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

Бильбо хочет прокопать новые коридоры в норе, но так как копать будут только Фродо и сам Бильбо (не Гэндальф же!) , есть возможность прокопать только один или два новых коридора.

После этого последовательность из нескольких комнат будет названа коллайдером. При этом должны быть выполнены следующие условия: первая комната в этой последовательности соединена коридором со второй, вторая - с третьей, и так далее, наконец, последняя комната последовательности должна быть соединена с первой. Кроме того, каждая комната может входить в эту последовательность не более одного раза.

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

Входные данные
В первой строке входного файла содержится целое число n (3≤n≤100000) - число комнат в норе Бильбо.

В следующих n−1 строках содержатся по два целых числа - номера комнат, соединенных коридорами. Комнаты нумеруются от 1 до n.

Выходные данные
В первую строку выходного файла выведите максимально возможное число комнат в коллайдере.

На следующих одной или двух строках выведите пары номеров комнат, между которыми следует прокопать новые коридоры.

Если существует несколько возможных планов строительства коллайдера максимальной длины, выведите любой из них.

Примечание
В первом примере коллайдер состоит из комнат с номерами 1, 2, 3 и 4 (именно в этом порядке), во втором примере - 1, 3, 2, 4.

В последнее время фитнесс-клубы стали очень популярны среди жителей столицы Флатландии. В такие клубы люди ходят после работы для того, чтобы поддерживать себя в хорошей физической форме. В фитнесс-клубe «Флат» каждому из посетителей на время посещения выделяется один из k шкафчиков, в который он может убрать свои вещи на время тренировки.

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

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

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

Необходимо найти максимальное число шкафчиков, которые окажутся закрытыми, в случае оптимальных действий персонала фитнесс-клуба.

Входные данные
Первая строка входного файла содержит два целых числа: n (1≤n≤100) и k (1≤k≤1000) Каждая из последующих n строк содержит по два целых числа a_i и b_i (0≤a_i,b_i≤k, a_i+b_i≤k).

Выходные данные
В выходной файл выведите одно число — ответ на задачу.

Примечание
Пронумеруем шкафчики числами от 1 до 4. Посетителям, пришедшим на первую тренировку выдадим ключи так: тому, кто закроет, от шкафчика 1, тем, кто не закроет, от 2 и 3. Посетителям, пришедшим на вторую тренировку, выдадим ключи так: тому, кто закроет, номер 2, тому, кто не закроет, номер 3. В итоге открытым после окончания дня останется только шкафчик номер 3.

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

Чтобы ничего не перепутать, мастера договорились, что Олег будет только включать лампы, а Сергей только выключать.

Театральная сцена представляет собой прямоугольник W на L метров, внутри которого расположено N ламп подсветки.

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

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

Перед началом спектакля Олег и Сергей получили подробный сценарий, в котором указано количество действий M и для каждого действия свой набор ламп подсветки, которые должны быть включены. Лампы, которые не входят в этот набор, должны быть выключены. Перед первым действием Олег должен находиться в левой части кулис, а Сергей − в правой. Изначально включены лампы, необходимые для первого действия.

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

Входные данные
На первой строке входного файла находится пять чисел − W,L,V₁,V₂ и N (1≤W,L≤50, 1≤V₁,V₂≤20, 1 ≤ N ≤ 15)− размеры сцены, максимальные скорости мастеров и число ламп подсветки соответственно.

Далее идут N строк с координатами ламп подсветки в метрах x_i,y_i (0<x_i<L, 0<y_i<W).

Следующая строка содержит число M(1≤M≤10000) − число действий в спектакле. Далее идут M строк, каждая из которых содержит число ламп подсветки, которые должны быть включены в соответствующем действии, и номера ламп подсветки. Все числа во входном файле целые.

Выходные данные
В выходной файл выведите единственное число − минимальное суммарное время перерывов между действиями в секундах с точностью 10^-5.

В 2222 году экспедиция на планету XZ-238 в звездной системе ню Малой Медведицы обнаружила в одной из пещер загадочное устройство. Вдоль стены по прямой расположены n треугольных и n круглых гнезд. Расшифровка инструкций, расположенных рядом на стене, показала, что эти гнезда следует соединить проводами: каждое треугольное гнездо должно быть соединено с каким-либо круглым, расположенным правее.

Были изготовлены n треугольных и n круглых штекеров, которые можно соединять проводами. Однако никакой маркировки нет, поэтому понять какое гнездо следует соединить с каким не удается. Начальник экспедиции хочет заказать с Земли провода. Решено было заказать один большой моток кабеля, который затем нарезать на соединительные провода. Поскольку доставка грузов с Земли дорога, необходимо заказать как можно меньше кабеля. С другой стороны, поскольку неизвестно какое гнездо требуется соединить с каким, нужно заказать такое количество кабеля, чтобы при любом способе соединения длины кабеля хватило на изготовление соединительных проводов. Помогите руководству экспедиции по заданному расположению гнезд вычислить, кабель какой длины следует заказать. Гарантируется, что хотя бы один способ соединить гнезда описанным образом существует.

Например, рассмотрим расположение гнезд, изображенное на рисунке.



Можно соединить треугольное гнездо 1 с круглым гнездом A, а треугольное гнездо 2 − с круглым гнездом B. Для такого соединения необходимы провода длины 5 и 4, суммарная длина − 9. Можно также соединить 1 с B и 2 с A, в этом случае необходимы провода длины 7 и 2, суммарная длина также 9. Таким образом необходимо заказать с Земли кабель длиной 9 метров.

В случае же, показанном на следующем рисунке, есть лишь один способ соединить гнезда: 1 с A, а 2 с B. Гнездо 2 нельзя соединить с A, поскольку A расположено левее. Так что в этом случае необходимо 2 метра кабеля.



Входные данные
Первая строка входного файла содержит число n (1≤n≤1000). Вторая строка содержит n целых чисел, i-е число означает расстояние от начала стены до i-го треугольного гнезда. Третья строка также содержит n целых чисел, i-е число означает расстояние от начала стены до i
-го круглого гнезда. Все числа во второй и третьей строках различны и лежат в диапазоне от 0 до 10⁵.

Выходные данные
Выведите одно число − кабель какой длины необходимо заказать с Земли.

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

Входные данные
Первая строка входных данных содержит число бактерий N (1 ≤ N ≤ 500). Каждая из следующих N строк содержит 2 целых числа x_i, y_i – координаты i-й бактерии (−10⁹ ≤ x_i, y_i ≤ 10⁹). Никакие 2 бактерии не располагаются в одной точке.

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

Напишите программу, вычисляющую остаток от деления заданного «длинного» числа на заданную цифру.

Входные данные
В первой строке задана цифра K (1≤K≤9). Во второй строке задано натуральное число N, состоящее из не более чем 100000 цифр.

Выходные данные
Выведите остаток от деления N на K.

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

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

Стороны коробок должны быть параллельны сторонам склада

Коробку при помещении на склад разрешается расположить где угодно (с выполнением предыдущего условия), в том числе на другой коробке, но все коробки должны быть ориентированы одинаково (т.е. нельзя одну коробку расположить «стоя», а другую – «лежа»)

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

Входные данные
Вводится шесть натуральных чисел. Первые три задают длину, высоту и ширину склада. Следующие три задают соответственно длину, высоту и ширину коробки с ноутбуком. Каждое из чисел не превышает 1000.

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

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

Входные данные
Сначала вводится натуральное число N, не превосходящее 100 – количество точек. Далее вводится N пар координат этих точек – целые числа, не превосходяшие 1000.

Выходные данные
Вывести слово YES (заглавными латинскими буквами), если такой треугольник нарисовать можно и NO в противном случае.

В салон красоты пришли n девушек. Каждая из них должна посетить парикмахера и косметолога. У каждого она проводит по m часов. За какое наименьшее время k сотрудников салона красоты смогут обслужить всех девушек, если каждый сотрудник может выполнять функции как косметолога, так и парикмахера?

Входные данные
Вводится три натуральных числа k, m, n, не превосходяших 10 000.

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

Есть кучка спичек. Играют двое. Сначала первый берет из кучки любое количество спичек от одной до пяти. Затем то же самое делает второй. Затем первый берет столько спичек, сколько есть у второго, затем второй берет столько спичек, сколько есть у первого и т. д. Выигрывает тот, кто не может сделать хода. Кто выигрывает при правильной игре?

Входные данные
Вводится одно число, не превосходящее 1000 – изначальное количество спичек.

Выходные данные
Вывести число 1, если первый игрок может выиграть независимо от действий второго, или число 2, если второй может выиграть независимо от действий первого. В остальных случаях вывести 0.

Дана картинка. Требуется повернуть ее на 90 градусов по часовой стрелке вокруг центра.

Картинка представляет собой квадрат, разбитый на N x N маленьких квадратиков. Каждый маленький квадратик закрашен в свой цвет. Цвета имеют номера от 0 до 255.

Входные данные
В первой строке вводится число одно натуральное число N, не превосходящее 100.

В следующих N строках записано по N чисел – цвета соответствующих квадратиков.

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

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


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

Входные данные

Программа получает на вход несколько строк. Первая строка содержит целые числа M и N - размеры лабораторного стола (1 <= M, N <= 10⁶). Во второй строке записано число K - количество монстров (0 <= K <= 10³).  Следующие K  строк содержат описания монстров - два целых числа и один символ из множества {N, E , S, W} - начальные координаты и направление соответствующего монстра (соответствие направлений и координат приведено на рисунке 1). Символ отделен от чисел ровно одним пробелом.
Символами обозначены следующие направления движения: N - вверх, S - вниз, W - влево, Е - вправо.

Выходные данные

Выведите единственное число - количество клеток стола, на которых побывают монстры.


Пояснения
Поле исполнителя и расположение "Квадратиков" для первого примера, показаны на рисунке ниже. Стрелочкой обозначено направление движения соответствующего "Квадратика".

 

Примеры

№	Входные данные	Выходные данные
1	8 5 4 4 4 S 6 2 W 6 3 N 6 4 S	13

У исполнителя Калькулятор две команды:

прибавь 1

умножь на 4

Выполняя первую из них, Калькулятор прибавляет к числу на экране 1, а выполняя вторую, умножает число на экране на 4. Запишите порядок команд в программе для получения из нуля числа N.

Входные данные
Вводится одно натуральное число N, не превосходящее 1000.

Выходные данные
Выведите последовательность из команд 1 (прибавь 1) и 4 (умножь на 4), разделенные пробелами. Если решений несколько, выведите любое из них.