Алгоритмы

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

Напомним, что если мы сравниваем две последовательности, и у них первые K символов совпадают, а (K+1)-е символы отличаются, то раньше будет идти по алфавиту та, в которой (K+1)-й символ идет раньше по алфавиту. Если же одна последовательность является началом другой, то раньше по алфавиту идет более короткая из них.

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

Входные данные
В первой строке входного файла записано число N — длина исходной последовательности (1≤N≤1000). Во второй строке идет сама последовательность. Последовательность состоит только из заглавных латинских букв.

Выходные данные
В выходной файл выведите выигрышную последовательность.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 MAMA	A	Рассматриваются строки MAMA, AMA, MA, A. Выигрышная строка A
2	4 ALLO	ALLO	Выигрышной является исходная строка
3	5 BBABB	ABB

Телефонные номера в адресной книге мобильного телефона имеют один из следующих форматов:

+7<код><номер>

8<код><номер>

<номер>

где <номер> — это семь цифр, а <код> — это три цифры или три цифры в круглых скобках. Если код не указан, то считается, что он равен 495. Кроме того, в записи телефонного номера может стоять знак “-” между любыми двумя цифрами (см. пример).

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

Два телефонных номера совпадают, если у них равны коды и равны номера. Например, +7(916)0123456 и 89160123456 — это один и тот же номер.

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

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

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

Примеры

№	Входные данные	Выходные данные
1	8(495)430-23-97 +7-4-9-5-43-023-97 4-3-0-2-3-9-7 8-495-430	YES YES NO

Рассмотрим N-домино. В таком домино каждая костяшка состоит из двух половинок, на каждой из которых нарисовано от 0 до N точек. Полный комплект костяшек такого домино содержит все возможные костяшки, каждую — по одному разу. Например, для N=2 в комплект войдут следующие костяшки: (0,0), (0,1), (0,2), (1,1), (1,2) и (2,2)

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

Входные данные
Вводится натуральное число N (1<=N<=30).

Выходные данные
Программа должна напечатать одно число - общее количество точек на всех костяшках полного комплекта N-домино.

Примеры

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

На клетчатой бумаге Петя нарисовал отрезок из точки с координатами (a,b) в точку с координатами (c,d). Через сколько клеток проходит этот отрезок (считается, что отрезок проходит через клетку, если он проходит через ее внутренность, если же он проходит только через вершину или по границе клетки, считается, что он не проходит через клетку).

Входные данные
Вводятся целые числа a, b, c, d. Числа по модулю не превышают 10⁹.

Выходные данные
Выведите одно число — количество клеток, через которые проходит отрезок.

Примеры

№	Входные данные	Выходные данные
1	0 0 6 4	8
2	3 3 -3 3	0

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

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

Выходные данные
Выведите два числа — размеры стола. Если возможно несколько ответов, выведите любой из них (но только один).

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

Примеры

№	Входные данные	Выходные данные
1	10 2 2 10	20 2 2 20 4 10 10 4
2	5 7 3 2	9 5 5 9

В школе продолжительность каждого урока 45 минут, а перемены между уроками – всего 5 минут. Первый урок начинается ровно в 8 часов утра. Напишите программу, отвечающую на вопрос «во сколько в этой школе заканчивается K-ый урок?»

Формат входных данных
Вводится одно натуральное число K, не превышающее 15.

Формат выходных данных
Выведите время окончания K-ого урока: сначала часы, потом минуты, разделяя их пробелом.

На координатной плоскости расположены равнобедренный прямоугольный треугольник ABC с длиной катета d и точка X. Катеты треугольника лежат на осях координат, а вершины расположены в точках: A (0,0), B (d,0), C (0,d).

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

Входные данные
Сначала вводится натуральное число d(не превосходящее 1000), а затем координаты точки X – два целых числа из диапазона от ­–1000 до 1000.

Выходные данные
Если точка лежит внутри, на стороне треугольника или совпадает с одной из вершин, то выведите число 0. Если точка лежит вне треугольника, то выведите номер вершины треугольника, к которой она расположена ближе всего (1 – к вершине A, 2 – к B, 3 – к C). Если точка расположена на одинаковом расстоянии от двух вершин, выведите ту вершину, номер которой меньше.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1 1	0	Точка лежит внутри треугольника.
2	3 -1 -1	1	Точка лежит вне треугольника и ближе всего к ней вершина A
3	4 4 4	2	Точка лежит на равном расстоянии от вершин B и C,в этом случае нужно вывести ту вершину, у которой номер меньше, т.е. выведено должно быть число 2
4	4 2 2	0	Точка лежит на стороне треугольника.

Дано натуральное четырехзначное число. Найдите минимальное натуральное четырехзначное число, состоящее из тех же цифр, что и заданное. Заметим, что четырехзначные числа не могут начинаться с нуля.

Входные данные
Вводится натуральное четырехзначное число.

Выходные данные
Выведите минимальное натуральное  четырехзначное число, состоящее из тех же цифр.

Примеры

№	Входные данные	Выходные данные
1	1513	1135

В Берляндии плачевная ситуация с междугородним автобусным сообщением. Во всей стране есть всего три автобусных маршрута, по каждому из которых курсирует лишь один автобус. В первый день нового года ровно в полночь все три автобуса отправляются по своим маршрутам из столицы Берляндии. Известно, что первому автобусу на то, чтобы проехать весь маршрут и вернуться в столицу требуется a минут, второму — b минут, а третьему — c минут. Таким образом, первый автобус отправляется из столицы Берляндии в моменты времени 0, a, 2a, 3a , второй — в моменты времени 0, b, 2b, 3b , а третий в моменты времени 0, c, 2c, 3c .

Момент времени называется подходящим для пересадки , если в этот момент все три автобуса отправляются из столицы Берляндии. Например если a=1, b=2, c=1, то моменты времени 0 и 2 являются подходящими для пересадки, а момент времени 1 не является, потому что в этот момент времени второй автобус находится в пути. Берляндия — особая страна с особым измерением времени, поэтому в берляндских сутках ровно t минут. Это означает, что в первый день происходят все моменты времени с 0-го по (t−1)-й включительно, во второй день — c t-го по (2t−1)-й включительно, в третий — с 2t-го по (3t−1)-й включительно и так далее.

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

Входные данные
В пяти строках заданы пять целых чисел a, b, c, t  и d (1≤a, b, c≤10⁶ , 1≤t, d≤10⁹ ) — время полного прохождения маршрута первым, вторым и третьим автобусами, соответственно, количество минут в сутках и номер дня, которым интересуется министерство транспорта Берляндии.

Выходные данные
Выведите одно целое число — количество подходящих для пересадки моментов времени в d-й день.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	1 2 1 3 1	2	Сутки длятся 3 минуты, поэтому все моменты времени в день с номером 1 — это 0, 1, 2, из них моменты времени 0 и 2 являются подходящими для пересадки
2	2 3 4 7 2	1	Здесь рассматриваются вторые сутки с моментами времени 7, 8, 9, 10, 11, 12, 13. Первый автобус отправляется в моменты времени 8, 10, 12, второй автобус — в моменты времени 9 и 12, а третий — в моменты времени 8 и 12. Таким образом, только момент времени 12 является подходящим для пересадки.
3	2 3 4 3 3	0	Нет ни одного подходящего для пересадки момента времени

Маше на день рождения подарили набор матрёшек!

Теперь Маша сидит и вкладывает их одну в другую. Она заметила, что матрёшки отличаются по размеру, и одна помещается внутри другой, только если ее размеры строго меньше. Так, если есть две матрёшки i и j , а их размеры a_i и a_j соответственно, то матрёшка i вкладывается внутрь матрёшки j тогда и только тогда, когда a_i < a_j . Разумеется, непосредственно внутрь матрёшки можно вложить только одну другую матрёшку, иначе получится неаккуратно, а Маша — очень аккуратная девочка.

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

Входные данные
В первой строке находится число n — количество матрёшек, подаренных Маше ( 1 ≤ n ≤ 1000 ). В следующей строке через пробел находятся n чисел — размеры матрёшек. Число a_i , стоящее на месте i , задает размер матрёшки с номером i ( 1 ≤ a_i ≤ 10 000 ).

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

Примеры

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

Когда настала зима и дел в Простоквашино стало мало, Шарик и Матроскин все дни проводили за настольными играми. Но шахматы, шашки, крестики-нлоики и домино им быстро надоели, а других игр у них не было. Поэтому они придумали новую игру.

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

Входные данные
В единственной строке записаны через пробел 100 чисел a_i (1≤a_i≤1000)

Выходные данные
В ответ выведите Matroskin, если выигрывает Матроскин, иначе выведите Sharik. Если выигрывает Матроскин, то на следующей строке выведите оптимальный первый ход Матроскина: если он должен взять самое левое число, то выведите «left», если он должен взять самое правое число — выведите «right». Если Матроскину не важно, какое из чисел взять, выведите любое из слов «left» и «right».

Примеры

№	Входные данные	Выходные данные
1	1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2	Matroskin right

Приближалось лето, и Игорь, Гена и Денис решили пойти вместе в поход, как и в прошлом году. Почти все вопросы уже были решены: уже был проработан маршрут, куплены билеты на поезд, в шкафу у Дениса найдена четырехместная палатка, а под кроватью у Игоря — топор. Осталось решить только вопрос с продуктами.

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

Зато у них сохранилась переписка в социальной сети, где они спорили, кто сколько банок тушенки понесет. В этой переписке Игорь сначала предложил поделить всю тушенку в отношении a: b: c, так, что первую часть понесет сам Игорь, вторую — Гена, а третью — Денис. Но Денису это не понравилось, и он предложил поменять соотношение на d: e: f.

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

По данным двум отношениям a: b: c и d: e: f вычислите, сколько банок тушенки ребята покупали для прошлогоднего похода. Из всех возможных ответов выведите минимальный. Ребята помнят, что как минимум одна банка тушенки у них точно была.

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

Все числа не превышают 1000.

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

Примеры

№	Входные данные	Выходные данные	Пояснения
1	10 3 7 3 1 1	20	При делении тушенки между ребятами в отношении 10:3:7 Игорь понесет 10 банок, Гена — 3 банки, а Денис — 7 банок. А в случае соотношения 3:1:1 Игорю достанется 12 банок, а Гене и Денису по 4.

В числе подсчитали количество единиц, в получившемся опять подсчитали количество единици т.д.
Например: 111211121112111 - 12 - 1 - 1 - 1 - ...

В итоге полученная последовательность стабилизировалась. На каком числе?

Например, последовательность 111211121112111 - 12 - 1 - 1 - 1 - ... стабилизировалась на числе 1.

Входные данные
Вводится одно натуральное число, состоящее из не более чем 100 цифр.

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

Примеры

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

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	abcdefg abd	NO
2	abcdg bag	YES
3	a aaa	YES

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [2385177; 2385437] простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку (каждое число с номером выводите с новой строки). 

У меня в прихожей стоят в ряд 20 тапочек – 10 левых и 10 правых. Приходя домой, я переобуваюсь и выбираю два тапочка – левый и правый, в которые мне удобнее всего засунуть ноги. Естественно, что левый тапочек должен стоять левее правого, и расстояние (количество других тапочек) между ними должно быть как можно меньше. Напишите программу, которая вычисляет, сколько же тапочек стоит между теми, которые мне удобнее всего надеть.

Входные данные
Вводится последовательность из 10 нулей и 10 единиц, записанных в некотором порядке. Единица соответствует левому тапочку, 0 – правому тапочку. Числа разделены пробелами.
Выходные данные
Программа должна вывести количество тапочек между самыми удобными тапочками, или -1, если таких нет.
 

Примеры

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

Для натурального числа N (1<=N<=10⁵) выведите на экран все его делители, включая 1 и само число N, в последней строке выведите количество этих делителей, включая 1 и само число N.

Входные данные
На вход подается натуральное число N (1<=N<=10⁵).

Выходные данные
В первой строке выведите все делители числа N, в порядке возрастания, разделяя их одним пробелом. Во второй строке выведите одно число - количество делителей исходного числа.
 

Примеры

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

Домовой Кузьма очень любит играть в шашки на доске 8х8. Когда никто не хочет с ним играть, он просто сидит и думает. Например, сейчас он пытается посчитать сколько есть вариантов провести белую шашку в дамки, если она находится одна на доске?
(Белая шашка ходит по диагонали на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)

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

Вводятся два числа от 1 до 8: номер номер столбца (считая слева) и строки (считая снизу), где изначально стоит шашка.

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

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

 

 

Примеры

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

 

Когда-то в далеком детстве мы все с удовольствием играли в игру "Камушки" или "Пять камешков", кто как называл. Для игры нужны были обычные камешки, которые можно было запросто найти на улице. Играть можно было в любом месте, Для игры нужна была небольшая ровная площадка утоптанной земли или ровный пол крыльца или беседки. 
Первый шаг игры заключался в следующем. На землю перед собой бросаются все пять камешков. Выбирался один из них. Это биток. Этот камешек подбрасывается в воздух и, пока он летит, необходимо поднять один из оставшихся на земле камешков и успеть подхватить этой же рукой летящий. Подобранный камешек откладывается в сторону и действие повторяется для всех оставшихся камешков.
На следующих шагах количество камешков, которые надо подхватить увеличивается. Последним шагом был экзамен, когда необходимо было подбросить все собранные камешки в воздух и поймать их тыльной стороной ладони, а затем опять подбросить, и поймать открытой ладонью. Сколько камешков в итоге оставалось, столько баллов и получаешь. Ход переходит к следующему игроку, который также повторяет все шаги. Далее запускался новый тур игры. Выигрывал тот, кто набирал больше всего баллов за все туры.
Многие ребята усложняли игру самыми разными способами.
Допустим у ребят есть бесконечное число камешков лежащих на земле. В конце тура им необходимо поймать в ладони не все камешки, а ровно столько, чтобы общее число баллов у них увеличилось на 1 или удвоилось или утроилось. Перед началом игры у всех уже имеется 1 балл. Победителем будет считаться тот, кто быстрее наберет N баллов.
Будем считать, что у всех играющих достаточно опыта игры, и они всегда доходят до экзамена с нужным им числом камней (чтобы была возможность нужное число баллов увеличить на 1, удвоить или утроить).

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

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

Программа получает на вход одно число, не превосходящее 10⁶.

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

Требуется вывести одно число: наименьшее количество искомых операций.

 

 

Примеры

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