Информатика

А мы, тем временем, возвращаемся в поезд Москва-Адлер, где Максим все-таки был пойман папой, и три рулона туалетной бумаги не были выпущены из окна первого вагона («Ну паааап, ну мне было интересно, что длиннее — поезд или бумага, ну не надо за ухо»).

Теперь Максим сидит в купе вместе с мамой. Чтобы отвлечь его от продумывания деталей новых экспериментов, мама — неплохой математик — рассказала Максиму одну любопытную задачу («Мои студенты в среду ее так и не смогли решить, совсем считать разучились»).

Дано число x. Каждую его цифру нужно умножить на 19, прибавить к результату 40, полученное число снова умножить на 19, взять последнюю цифру этого произведения и поставить его на место исходной цифры в числе x. Вопрос: какое число получится в итоге?

Максим, впрочем, решил задачу гораздо быстрее, чем ожидала его мама, и, к сожалению, снова был готов к экспериментам. А сможете ли вы?

Входные данные
Дано целое число x (0≤x≤10000).

Выходные данные
Выведите одно число: ответ на задачу, которую мама рассказала Максиму.

Примеры

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

Теория относительности — штука сложная. Это Максим, семилетний сын одного известного физика, знает уже давно. Из отцовских объяснений Максим понял, что свет — это самая быстрая штуковина в мире. А если кажется, что что-то все-таки быстрее, чем свет, то на самом деле оно движется со скоростью, равной скорости света — 299 792 458 м/с.

Так что по пути на море, убегая по поезду Москва-Адлер от чем-то очень недовольного папы, Максим совершенно не думал над тем, за что именно он сейчас получит и можно ли это было как-то предотвратить. Волновало его одно: с какой скоростью его папа бежит относительно Земли, если учесть теорию относительности? Поезд едет из Москвы в Адлер со скоростью v м/c, а папа бежит за Максимом в сторону головы поезда со скоростью u м/с относительно поезда.

Входные данные
Даны два числа v и u — скорость поезда относительно Земли и скорость папы Максима относительно поезда соответственно. Обе скорости неотрицательны и не превышают скорости света (299 792 458 м/с).

Выходные данные
Выведите одно число — скорость папы Максима относительно Земли, найденную с учетом представлений Максима о теории относительности.

Примеры

№	Входные данные	Выходные данные
1	120 35	155
2	149896229 149896230	299792458

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

Они выписывают на печке угольком 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

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

Помогите Матроскину узнать уровень его гордости, то есть найдите средний вес всех родившихся за n лет телят.

Входные данные
Вводится одно целое число 1<=n<=1000 — количество лет, которое у Мурки рождались телята.

Выходные данные
Выведите средний вес всех родившихся телят.

Примеры

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

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

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

Зато у них сохранилась переписка в социальной сети, где они спорили, кто сколько банок тушенки понесет. В этой переписке Игорь сначала предложил поделить всю тушенку в отношении 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.

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

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


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

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

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

Входные данные
В первой строке вводится целое число N — количество новых фирм (1 ≤ N ≤ 10³).

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

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

Примеры

№	Входные данные	Выходные данные
1	4 lacoste hyundai renault peugeot	4
2	3 aaaaaaa bbbbbbb ccccccc	1

Сколько всего натуральных чисел состоят из не менее чем a цифр и не более, чем b цифр?

Входные данные
Вводятся два произвольных натуральных числа a и b через пробел. Каждое не превышает 10000.

Выходные данные
Выведите одно число: количество чисел, обладающих указанным свойством.

Примеры

№	Входные данные	Выходные данные
1	1 2	99
2	1 1	9

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

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

Нет? А вот редактор литературного журнала занимается этим каждый день, получая тонны корреспонденции от молодых авторов, желающих стать известными поэтами. Благо, в последнее время большая часть стихов присылается по электронной почте, поэтому у редактора возникла мысль автоматизировать процесс. Он твердо уверен, что стихи тем лучше, чем точнее в них рифма. Он считает две строки зарифмованными, если у них совпадает несколько последних букв. И чем больше букв совпадает, тем лучше зарифмованы строки. Например, у строк “палка” и “веревка” совпадают только пары последних букв “ка”, а у строк “олимпиада” и “рая и ада” совпадают четыре буквы (пробелы мы пропускаем). Поэтому вторая рифма лучше. Редактор считает, что в четверостишии (четыре строки) первая строка должна рифмоваться с третьей, а вторая – с четвертой. Для каждой из этих двух пар строк он считает количество совпадающих последних символов и из этих двух чисел выбирает наибольшее. Полученное число он называет коэффициентом качества стихотворения – чем он выше, тем больше шансов у стихотворения быть опубликованным. Помогите редактору – напишите программу, которая определяет качество стихотворения. И кто знает, может быть, благодаря вашим усилиям, мир познакомится с гениальными стихами (см. первый пример).

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

Выходные данные
Выведите одно число – коэффициент качества стихотворения.
 

№	Входные данные	Выходные данные
1	yapomnyuchudnoemgnovenje peredomnojyavilasty kakmimoletnoevidenje kakgenijchistoykrasoty	4
2	eto vovse ne stihi	0
3	etootlichnyestihi etootlichnyestihi etootlichnyestihi etootlichnyestihi	17

Два автомобиля движутся по кольцевой дороге длины L в противоположных направлениях. Они начинают движение из одной точки и едут с постоянными скоростями v1 и v2 соответственно. Требуется определить, на каком расстоянии друг от друга они окажутся в момент времени T.

Входные данные
На вход подаются 4 натуральных числа L, v₁, v₂, T, разделенных пробелом. Все числа не превосходят 100.

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

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

Вася учится делить с остатком. Он взял некоторое число, разделил его на 2 и отбросил остаток. То, что получилось, разделил на 3 и опять отбросил остаток. Полученное число он разделил на 4, отбросил остаток и получил число K. Какое число мог выбрать Вася изначально?

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

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

Примеры

№	Входные данные	Выходные данные
1	1	24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

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

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

Выходные данные
Выведите одно натуральное число – какой-нибудь (любой!) выигрышный ход второго игрока.

Примеры

№	Входные данные	Выходные данные
1	1	2
2	1000000000000000	1000000000000009

Петя долго готовился к сдаче ЕГЭ по информатике. Он научился решать все задачи, и лишь задачу А12 ему научиться решать не удалось. Но он надеется тайно пронести на экзамен ноутбук, и просит вас написать программу, которая ему поможет. Вот как выглядит эта трудная задача в демоверсии варианта ЕГЭ 2010 года:
"А12. Витя пригласил своего друга Сергея в гости, но не сказал ему код от цифрового замка своего подъезда, а послал следующее 5М5-сообщение:
"В последовательности цифр 3182 все цифры больше 5 разделить на 2 (при необходимости отбросив остаток), а затем удалить из полученной последовательности все четные цифр".
Какой код получил Сергей, выполнив указанные в сообщении действия?"

Входные данные
Вводятся 4 цифры в одной строке без пробелов – последовательность, содержащаяся в SMS-сообщении в реальном варианте ЕГЭ вместо 3182 в демоверсии.

Выходные данные
Выведите код цифрового замка без пробелов.

Примеры

№	Входные данные	Выходные данные
1	0586	53

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

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

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

Примеры

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

В доме несколько подъездов. В каждом подъезде одинаковое количество квартир. Квартиры нумеруются подряд, начиная с единицы. Может ли в некотором подъезде первая квартира иметь номер x, а последняя – номер y?

Входные данные
Вводятся два натуральных числа x и y (x ≤ y), не превышающие 10 000.

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

Примеры

№	Входные данные	Выходные данные
1	11 15	YES
2	2 10	NO

Вася выложил в ряд слева направо 100 карточек, на которых написаны числа 1, 2, 3, …, 100 соответственно (числами вниз). После этого он поменял местами карточки, на которых написаны числа i и j. Петя открывает карточки по очереди слева направо. Какое минимальное количество карточек ему придется открыть, чтобы точно выяснить, какие карточки поменял местами Вася?

Входные данные
Вводятся два числа i (1 ≤ i ≤ 100) и j (1 ≤ j ≤ 100). Числа записаны через пробел.

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

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

У меня в прихожей стоят в ряд 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

Возьмем произвольное слово и проделаем с ним следующую операцию: поменяем местами его первую согласную букву с последней согласной буквой, вторую согласную букву с предпоследней согласной буквой и т.д. Если после этой операции мы вновь получим исходное слово, то будем называть такое слово негласным палиндромом. Например, слова sos, rare, rotor, gong, karaoke являются негласными палиндромами.

Вам требуется написать программу, которая по данному слову определяет, является ли оно негласным палиндромом.

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

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

Примеры

№	Входные данные	Выходные данные
1	tennete	YES

Сегодня в индийском городке Старый Гоа отмечают День святого Франциска Ксавьера. Святой Франциск Ксавьер – миссионер, член ордена иезуитов, считается величайшим католическим миссионером Нового времени.

Мощи святого Франциска Ксавьера – духовного покровителя индийских христиан – покоятся в Старом Гоа в известном католическом храме – Базилике Бом Иисус. Со дня постройки храма в 1605 году раз в десять лет мощи святого выставляются для всеобщего обозрения.

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

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

Примеры

№	Входные данные	Выходные данные
1	1610 1640	3
2	1615 1645	3

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

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

Входные данные
Cначала вводится число N – общее количество рассматриваемых дней (1 ≤ N ≤ 100). В следующей строке задается N целых чисел, разделенных пробелами. Каждое число – среднесуточная температура в соответствующий день. Температуры – целые числа, принадлежащие диапазону от –50 до 50.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	6 -20 30 -40 50 10 -10	2	Рассматриваются 6 дней. Самая продолжительная оттепель была на 4-й и 5-й день (50 и 10 градусов соответственно)
2	8 10 20 30 1 -10 1 2 3	4	Самая продолжительная оттепель была в первые 4 дня
3	5 -10 0 -10 0 -10	0	Дней с положительной температурой не было