Алгоритмы

Входные данные
Четыре числа – координаты двух различных точек на прямой.

Выходные данные
Три числа – коэффициенты A, B и C уравнения этой прямой.

Примеры

№	Входные данные	Выходные данные
1	1 0 2 1	1 -1 -1

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


Входные данные
Вводятся два числа N и M - размеры таблицы (1<=N<=10, 1<=M<=10).

Выходные данные
Выведите искомое количество вариантов.
 

Примеры

№	Входные данные	Выходные данные
1	2 3	3

 

Требуется вычислить площадь комнаты в квадратном лабиринте.

Входные данные
В первой строке  вводится число N – размер лабиринта (3 <= N <= 10). В следующих N строках задан лабиринт (‘.’ – пустая клетка, ‘*’ – стенка). И наконец, последняя строка содержит  два числа – номер строки и столбца клетки, находящейся в комнате, площадь которой необходимо вычислить. Гарантируется, что эта клетка пустая и что лабиринт окружен стенками со всех сторон.

Выходные данные
Требуется вывести единственное число – количество пустых клеток в данной комнате.

 

Примеры

№	Входные данные	Выходные данные
1	5 ***** **..* *.*.* *..** ***** 2 4	3

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

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

Выходные данные
Выведите одно целое число – искомое количество слов.
 

Примеры

№	Входные данные	Выходные данные
1	solo	12

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

Для простоты будем считать, что все карты различны по номиналу, а также, что самая младшая карта побеждает самую старшую карту ("шестерка берет туза").

Игрок, который забирает себе карты, сначала кладет под низ своей колоды карту первого игрока, затем карту второго игрока (то есть карта второго игрока оказывается внизу колоды).

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

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

Выходные данные
Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 10⁶ ходов игра не заканчивается, программа должна вывести слово botva.

Примеры

№	Входные данные	Выходные данные
1	1 3 5 7 9 2 4 6 8 0	second 5

Весельчак У любит дарить алмазных черепашек. У него в сумке лежат черепашки либо трех цветов: розовый, белый и зеленый, либо четырех цветов: розовый, белый, зеленый и желтый. Он по очереди дарил черепашек из сумки, цвет i-й черепашки был Si. Цвета представлены следующим образом: P - розовый, W - белый, G - зеленый, Y - желтый. Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four. 

Входные данные
В первой строке записано число N (\(1<=N<=100\)) - количество Черепашек, которое вынимал Весельчак У. Во второй строке содержатся N символов Si - цвета, вынимаемых черепашек. Каждый символ Si равен P, W, G или Y. Всегда существуют такие i, j и k, что Si = 'P', Sj = 'W' и Sk = 'G'.

Выходные данные
Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four. 

 

Примеры

№	Входные данные	Выходные данные
1	6 G W Y P Y W	Four
2	9 G W W G P W P G G	Three
3	8 P Y W G Y W Y Y	Four

У Громозеки есть N часов. Стрелка i-х часов (\(1<=i<=N\)) поворачивается на 360 ° ровно за Ti секунд. Изначально стрелка всех часов стоит на месте и направлена прямо вверх. Громозека запускает все часы одновременно. Через сколько секунд стрелка всех часов снова укажет прямо вверх?

Входные данные
В первой строке записано целое число N (\(1<=N<=100\)). В следующих N строках записаны целые числа Ti (\(1<=T_i<=10^{18}\)), по одному числу в строке. 

Выходные данные
Выведите на экран ответ. Гарантируется, что ответ не превышает \(10^{18}\).
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 2 3	6	У нас есть двое часов. Время, когда стрелка каждых часов указывает вверх, выглядит следующим образом: Часы 1: 2, 4, 6, ... секунд после начала. Часы 2: 3, 6, 9, ... секунд после начала. Таким образом, требуется 6 секунд, пока стрелки обоих часов снова не укажут прямо вверх.
2	5 2 5 10 1000000000000000000 1000000000000000000	1000000000000000000

 

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

Иван хочет принести в приемную комиссию выбранного вуза папку, в которой находится диплом Московской олимпиады по программированию (такой диплом у Ивана ровно один). Для того чтобы понять, что в данной папке нужного диплома нет, Ивану нужно просмотреть все дипломы из этой папки. Чтобы открыть одну папку Ивану нужно потратить одну секунду, просмотр одного диплома занимает у него также одну секунду, и он может мгновенно переходить к следующей папке после окончания просмотра предыдущей. Порядок просмотра папок Иван может выбирать. То, что в пустых папках диплом можно не искать, Ивану очевидно.

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

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 10⁵) - количество папок. Во второй строке записаны N целых чисел a₁, a₂, ..., a_N (0 ≤ a_i ≤ 10⁵) - количество дипломов в каждой из папок.

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

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

Во втором примере Иван за 2 секунды просмотрит папку 1, потом за 2 секунды просмотрит папку 4, а если ни в одной из них диплома не встретилось, он поймет, что диплом в папке 3.

Примеры

№	Входные данные	Выходные данные
1	2 2 1	2
2	4 1 0 2 1	4

Два игрока, Петя и Ваня, играют в следующую игру. Имеется строка s длиной 3 или больше символов. Никакие два соседних символа в s не равны. Игроки ходят по очереди. Петя ходит первым. За один ход нужно удалить один из символов из строки s, за исключением крайних (первого и последнего). Символ не может быть удален, если удаление символа приведет к появлению двух соседних одинаковых символов в строке. Игрок, который не может выполнить операцию, проигрывает игру. Определите, какой игрок выиграет, если они будут играть оптимально.

Входные данные
На вход подается строка s (\(3 <= len(s) <= 10^5\)). Строка состоит только из строчных английских букв (a-z). Никакие два соседних символа в s не равны.

Выходные данные
Если Петя выиграет, выведите First. Если выиграет Ваня, выведите Second.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	aba	Second	Петя не может выполнить операцию, так как удаление символа b, который является единственным символом, который можно удалить, приведет к тому, что s станет равной aa, два одинаковых символа будут соседними.
2	abc	First	Когда Петя удаляет b из s, строка становится равной ac и Ваня не сможет выполнить операцию, поскольку в s нет других символов, за исключением крайних.
3	abcab	First

 

В ряд ставятся N кеглей. Громозека красит каждую из них в один из K цветов из своих банок с краской. Из эстетических соображений любые две соседних кегли должны быть окрашены в разные цвета. Найдите количество возможных способов раскрасить кегли.

Входные данные
Входная строка содержит два целых числа N и K (\(1<=N<=1000\), \(2<=K<=1000\)).

Выходные данные
Выведите на экран ответ на задачу. Гарантируется, что верный ответ не превышает \(2^{31}-1\).
 

 

Примеры

№	Входные данные	Выходные данные
1	2 2	2
1	1 10	10

 

Володе очень понравились задачи олимпиады по информатике, поэтому он решил ходить на занятия кружка по программированию. Придя на первое занятие кружка, он узнал, что занятия будут проходить еженедельно в один и тот же день недели. Помогите Володе составить календарь занятий до конца года – определите даты всех занятий, начиная с первого занятия и до конца года.
Программа получает на вход два числа, записанных в разных строках: номер месяца и номер дня месяца, когда проходит первое занятие. Номер месяца может быть одним из четырёх возможных чисел – 9, 10, 11, 12. Номер дня месяца – число от 1 до 30 для сентября и ноября (месяцы с номерами 9 и 11) или от 1 до 31 для октября и декабря (месяцы с номерами
10 и 12). 
Программа должна вывести даты всех занятий кружка до конца года в хронологическом порядке, по одной дате в строке, сначала месяц, затем день месяца, через пробел. Занятия проходят еженедельно, в тот же день недели, что и первое занятие. Формат вывода дат такой же, как в условии. Считайте, что каникулы отсутствуют, а последнее занятие может происходить в любой день декабря, в том числе и 31 числа.
 

Примеры

№	Входные данные	Выходные данные
1	11 20	11 20 11 27 12 4 12 11 12 18 12 25

На столе стоят три вазы с конфетами. В левой вазе лежат A конфет, в средней вазе лежат B конфет, в правой вазе лежат C конфет. Лена съедает одну конфету из левой вазы,
затем – одну конфету из средней вазы, затем из правой, средней, левой, средней, правой, средней и т. д. (слева направо, затем налево, опять направо и т.д.)
Если Лена хочет взять конфету из какой-то вазы, а конфет там нет, она расстраивается и идёт спать. Определите, сколько конфет съест Лена.
Программа получает на вход три целых неотрицательных числа A, B, C – количество конфет в левой, средней, правой вазе. Сумма трёх данных чисел не превосходит 2×10⁹.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 3	7	Лена съест конфеты из левой, средней, правой, средней, левой, средней, правой вазы. После этого она захочет съесть конфету из средней вазы, но в ней уже не осталось конфет.

Для выбора водящего в детской игре N человек становятся в круг, после чего произносится считалка. На первом слове считалки указывается на первого человека в кругу, на втором слове – на второго человека и т. д. После N-го человека снова идёт первый человек (все люди в кругу пронумерованы числами от 1 до N, круг зацикливается, после человека с номером N идёт человек с номером 1).
Всего в считалке M слов. Определите, на какого человека придётся последнее слово считалки.
Программа получает на вход два целых положительных числа. Первое число N – количество людей в кругу. Второе число M – количество слов в считалке. Оба числа не превосходят 10⁹.
Программа должна вывести одно целое число от 1 до N – номер человека в кругу на которого придётся последнее слово считалки.

Примеры

№	Входные данные	Выходные данные
1	10 25	5

У Ирохи есть последовательность из N строк s1, s2, .., sN. Каждая строка длиной L. Ироха хочет объединить все строки, чтобы получить очень длинную строку. Среди всех строк, которые она может получить таким образом, найдите лексикографически наименьшую. 

Будем считать, что строка s = s1s2...sn лексикографически меньше строки t = t1t2...tm, если выполняется одно из следующих условий:
- существует индекс i (\(1<=i<=min(n,m)\)), такой что \(s_j =t_j \), для всех индексов j (\(1<=j<=i\)), и \(s_i <t_i \);
-  \(s_i=t_j\) для всех i (\(1<=i<=min(n,m)\)), и \(n<m\).


Входные данные
В первой строке задаются числа N и L. Далее идут строки s1, s2, .., sN, каждая в отдельной строке.

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

 

Примеры

№	Входные данные	Выходные данные
1	3 3 dxx axx cxx	axxcxxdxx

 

Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число 1910 = 1·2⁴+0·2³+0·2²+1·2¹+1·2⁰ в двоичной системе запишется как 10011₂.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик — он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:
10011
11001
11100
01110
00111
10011
…
и результатом игры, следовательно, окажется число 1·2⁴+1·2³+1·2²+0·2¹+0·2⁰ = 28.

Поскольку придуманная игра с числами все больше занимает воображение учителя, отвлекая тем самым его от работы с ну очень одаренными школьниками, Вас просят написать программу, которая бы помогла Юрию Петровичу получать результат игры без утомительных ручных вычислений.
Формат входных данных
Входной файл содержит одно целое число N (0 ≤ N ≤ 32767).
Формат выходных данных
Ваша программа должна вывести в выходной файл одно целое число, равное результату игры.

Примеры

№	Входные данные	Выходные данные
1	19	28

Найти закопанный пиратами клад просто: всё, что для этого нужно – это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм нахождения клада так: «Встаньте около одинокой пальмы. Пройдите тридцать шагов в сторону леса, потом семнадцать шагов в сторону озера, …, наконец десять шагов в сторону большого булыжника. Клад находится под ним». Большая часть таких указаний просто сводится к прохождению какого-то количества шагов в одном из восьми направлений (1 – север, 2 – северо-восток, 3 – восток, 4 – юго-восток, 5 – юг, 6 – юго-запад, 7 – запад, 8 – северо-запад) (см. рис). Длина шага в любом направлении равна 1.
    Путешествие по такому пути обычно является прекрасным способом посмотреть окрестности, однако в наше время постоянной спешки ни у кого нет времени на это. Поэтому кладоискатели хотят идти напрямую в точку, где зарыт клад. Например, вместо того, чтобы проходить три шага на север, один шаг на восток, один шаг на север, три шага на восток, два шага на юг и один шаг на запад, можно пройти напрямую, использовав около 3.6 шага (см. рис).


Вам необходимо написать программу, которая по указаниям пиратов определяет точку, где зарыт клад.
 Формат входных данных
    Первая строка  содержит число N – число указаний (1≤N≤40). Последующие N строк содержат сами указания – номер направления (целое число от 1 до 8) и количество шагов (целое число от 1 до 1000). Числа разделены пробелами.
Формат выходных данных
    Выведите координаты X и Y точки (два вещественных числа, разделённые пробелом), где зарыт клад, считая, что ось Ox направлена на восток, а ось Oy – на север. В начале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с погрешностью не более 10^-3.
 

Примеры

№	Входные данные	Выходные данные
1	6 1 3 3 1 1 1 3 3 5 2 7 1	3.000 2.000
2	1 8 10	-7.071 7.071

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

Как известно, обычно все солдаты выстраиваются в шеренгу по росту, начиная с самого низкого. Но Павлу Андреевичу это показалось слишком скучным и он потребовал от Андрея Юрьевича выстроить солдат в другом порядке. Случайный порядок ему показался слишком хаотичным, поэтому он потребовал построения, в котором будет ровно k инверсий. Инверсией называется такая пара солдат, что более высокий из них стоит в шеренге раньше более низкого.

К счастью для Андрея Юрьевича, все солдаты разного роста и для каждого он знает, какой он по росту среди всех солдат. Исходя из этого, каждому солдату Андрей Юрьевич присвоил номер: первый номер получил самый низкий, а последний — самый высокий солдат.

Например, в построении (3, 1, 2) есть две инверсии — пары (3, 1) и (3, 2), в которых более высокий солдат стоит раньше более низкого.

Андрей Юрьевич поручил Вам помочь ему в построении солдат в требуемом порядке, и для этого вы должны написать программу, находящую расстановку n солдат в порядке, в котором есть ровно k инверсий.

Входные данные
Первая и единственная строка входного файла содержит два целых числа n и k (1 ≤ n ≤ 100 000) — количество солдат в строю и требуемое количество инверсий.

Гарантируется, что существует построение солдат с требуемым числом инверсий, то есть 0 ≤ k ≤ n(n - 1) / 2.

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

Примеры

№	Входные данные	Выходные данные
1	3 2	3 1 2
2	3 0	1 2 3

У Индианы Джонса есть ключ от двери, ведущей к тайным богатствам инков. Ключ имеет форму правильного треугольника, который, в свою очередь, разбит на n² маленьких правильных треугольников, в каждом из которых написана одна десятичная цифра. Пример ключа приведен ниже на рисунке.


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


Поскольку вы не хотите смерти Индианы и хотите получить свою долю сокровищ, вам придется помочь ему!

Входные данные
В первой строке входного файла содержится одно целое число n (1 ≤ n ≤ 100). В следующих n строках описан сам треугольник. Строка входного файла, имеющая номер i + 1, содержит 2i - 1 цифру — содержание i-й строки ключа-треугольника.

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

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

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3 4 5 6 7 8 9 counterclockwise	9  4 8 7  1 3 2 6 5
2	3 1 2 3 4 5 6 7 8 9 clockwise	5  7 6 2  9 8 4 3 1

Как и у каждого мальчика, у Феди есть игрушечные машинки. Однако ему повезло больше, чем обычному мальчику — все n его машинок являются радиоуправляемыми. Целыми днями он может устраивать различные автогонки и играть с друзьями.

Из всех видов гонок Федя предпочитает гонки по прямой. В данном формате соревнования трасса имеет форму прямой и является бесконечной (соревнования идут до тех пор, пока Феде это не надоест). Изначально каждая из n машинок находится на некотором расстоянии от старта — имеет фору x_i метров. По команде все машинки начинают свое движение от старта, при этом каждая машинка движется во время гонки с постоянной скоростью v_i метров в секунду. Все машинки движутся в одном направлении — удаляются от старта.

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

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

Входные данные
В первой строке входного файла содержится единственное число n — количество машинок на трассе (2 ≤ n ≤ 100). Каждая из следующих n строк содержит по два целых числа x_i и v_i — расстояние от старта (в метрах) и скорость машинки i (в метрах в секунду) соответственно (1 ≤ x_i, v_i ≤ 1000).

Исходно никакие две машинки не находятся в одной точке. Гарантируется, что хотя бы один обгон во время гонки произойдет.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 1 3 4 2	3.00000	На рисунке точкой A обозначено место обгона.
2	2 12 20 2 21	10.00000

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

Входные данные
Во входных данных записано сначала число N (2≤N≤100) – количество остановок на маршруте. Далее задается количество человек, севших в автобус на конечной. Далее идет (N-2) пары чисел, задающих для промежуточных остановок количество вышедших и количество вошедших пассажиров. Наконец, идет число, задающее количество вышедших из автобуса на конечной остановке.

Количество вошедших пассажиров на каждой остановке не превышало 100. Данные корректны, в частности, суммарное количество вошедших в автобус на всех остановках пассажиров всегда равно суммарному количеству вышедших.

Выходные данные
Выведите одно целое число — максимальное количество человек, которые в какой-то момент одновременно ехали в автобусе.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 10 3 1 5 10 0 2 15	15	На конечной в автобус село 10 человек. Далее 3 вышло и 1 зашел. В автобусе стало 8 человек. На следующей остановке вышло 5 и зашло 10. Стало 13 человек. На последней промежуточной остановке никто не вышел, а зашло 2 человека. На конечной вышло 15 человек. Итого максимальное количество – 15.
2	5 10 10 0 0 0 0 10 10	10	На конечной село 10 человек, которые на следующей остановке вышли. После этого на следующей остановке никто не сел и никто не вышел. Дальше опять село 10 человек, которые доехали до конечной.
3	5 0  0 9 3 4 2 0 8	10	С конечной автобус отправился без пассажиров. Дальше в него село 9 человек. На следующей остановке 3 вышли и зашли 4. В автобусе стало 10 человек. На следующей остановке 2 вышли и никто не зашел. 8 человек доехало до конечной. Максимальное количество пассажиров составляло 10
4	3 100 0 100 200	200	На начальной и на промежуточной остановку в автобус село по 100 человек. Вышло из автобуса 200 человек.