Язык программирования

Вам даны неотрицательные целые числа a и b (a<=b) и положительное целое число x. Сколько целых чисел от a до b включительно делятся на x?

Входные данные
В одной строке задаются три числа a, b и x (\(0<=a<=b<=10^{18}\), \(1<=x<=10^{18}\)).

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 8 2	3	Есть три целых числа от 4 до 8 включительно, которые делятся на 2: 4, 6 и 8.
2	0 5 1	6	Есть шесть целых чисел от 0 до 5 включительно, которые делятся на 1: 0, 1, 2, 3, 4 и 5.
3	9 9 2	0	Нет целого числа от 9 до 9 включительно, которое делится на 2.
4	1 1000000000000000000 3	333333333333333333	Остерегайтесь целочисленных переполнений!

 

Есть три упаковки конфет, каждая из которых содержит конфеты в количестве a, b и c штук соответственно. Двое воспитанников детского сада Сластена дерутся из-за этих конфет. Воспитательница Анна Николаевна пытается распределить пачки между двумя воспитанниками таким образом, чтобы каждый получил одинаковое количество конфет. Определите, возможно ли это.
Обратите внимание, что Анна Николаевна не может вынимать конфеты из упаковки, и все содержимое каждой упаковки должно быть отдано одному из учеников.

Входные данные
Во входной строке содержится три числа a, b и c (\(1<=a,b,c<=100\)).

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

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10 30 20	Yes	Раздайте пачку с 30 конфетами одному, а две пачки по 10 и 20 конфет - другому. Каждый получает по 30 конфет.
2	30 30 100	No	В этом случае у воспитанника, который получает упаковку со 100 конфетами, всегда больше конфет, чем у другого. Обратите внимание, что каждую упаковку нужно отдать одному из них.
3	56 25 31	Yes

 

Дана последовательность из N целых чисел (они могут быть положительными, отрицательными или равными 0). Необходимо выбрать из этих чисел два числа так, чтобы их произведение было как можно меньшим (не рассматриваются квадраты данных чисел, но можно выбрать произведение двух различных элементов последовательности, равных друг другу).
В первой строке входных данных записано целое число N, 2 ≤ N ≤10⁵ – количество данных чисел. Следующие N строк содержат сами числа, не превосходящие по модулю 40 000.
Программа должна вывести единственное целое число – наименьшее возможное произведение двух различных элементов этой последовательности.

Примеры

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

Громозека недавно купил три баллончика с краской. Цвет того, который он купил два дня назад, - a, цвет того, который он купил вчера, - b, и цвет того, что он купил сегодня, - c. Цвет каждого баллончика с краской условно представлен целым числом от 1 до 100 включительно. Поскольку Громозека забывчивый, он мог купить несколько баллончиков с краской одного цвета. Подсчитайте количество разных цветов этих баллончиков с краской и скажите ему.

Входные данные
В одной строке записаны три целых числа a, b и c (\(1 <= a,b,c<=100\)).

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

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

 

Володе очень понравились задачи олимпиады по информатике, поэтому он решил ходить на занятия кружка по программированию. Придя на первое занятие кружка, он узнал, что занятия будут проходить еженедельно в один и тот же день недели. Помогите Володе составить календарь занятий до конца года – определите даты всех занятий, начиная с первого занятия и до конца года.
Программа получает на вход два числа, записанных в разных строках: номер месяца и номер дня месяца, когда проходит первое занятие. Номер месяца может быть одним из четырёх возможных чисел – 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	Лена съест конфеты из левой, средней, правой, средней, левой, средней, правой вазы. После этого она захочет съесть конфету из средней вазы, но в ней уже не осталось конфет.

Сегодня в школе на уроке математики проходят делимость. Чтобы продемонстрировать свойства делимости, учитель выписал на доске все целые числа от 1 до
N в несколько групп, при этом если одно число делится на другое, то они обязательно оказались в разных группах. Например, если взять N = 10, то получится 4 группы.

• Первая группа: 1.
• Вторая группа: 2, 7, 9.
• Третья группа: 3, 4, 10.
• Четвёртая группа: 5, 6, 8.

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

Примеры

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

Для пополнения бюджета в стране Авалон, известной своими горными туристическими маршрутами, ввели новый налог для туристов. Величина налога
пропорциональна длине маршрута, но, поскольку маршрут проходит по горам и пройденное расстояние, зависящее от высоты спуска и подъёма, подсчитать сложно, налог считается без
учёта высоты, то есть величина налога пропорциональна горизонтальному перемещению, совершённому туристической группой. Кроме того, в силу старинного обычая все
туристические группы должны перемещаться по горам Авалона строго с запада на восток. Турфирма хочет сэкономить на налоге, поэтому она хочет разработать туристический
маршрут с минимальной величиной налога. При этом, поскольку маршрут является горным, он должен содержать подъём в гору и спуск с горы, то есть на маршруте должна быть точка,
которая находится строго выше начала и конца маршрута. 
Турфирма составила карту гор Авалона, содержащую информацию о высоте гор при передвижении с запада на восток. Высоты гор измерены в точках через равные расстояния. 
Найдите на данной карте гор Авалона туристический маршрут минимальной длины, удовлетворяющий условию наличия подъёма и спуска.
Первая строка входных данных содержит число N – количество точек на карте гор Авалона. Следующие N строк содержат информацию о высоте гор в данных N точках при движении с запада на восток. Все числа натуральные, не превосходящие 10⁵.
Программа должна вывести два числа – номер точки начала маршрута и номер точки окончания маршрута. Точки нумеруются от 1 до N. Если маршрута, удовлетворяющего
условиям, не существует, программа должна вывести одно число 0.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 18 10 15 20 20 10 3	3 6	Дано 7 точек с высотами 18, 10, 15, 20, 20, 10, 3. Самый короткий маршрут, содержащий подъём и спуск, – это 15, 20, 20, 10. Он начинается в точке номер 3 и заканчивается в точке номер 6.
2	3 9 8 5	0	Высота гор монотонно убывает, поэтому искомого маршрута не существует.

Антонин, Бальбин и Цезарь играют в игру "Карты на троих", алгоритм которой следующий:
- сначала у каждого из трех игроков есть колода, состоящая из некоторого количества карт. На каждой карточке написана буква a, b или c. Порядок карт в колодах не может быть изменен;
- игроки ходят по очереди. Антонин ходит первым;
- если в колоде текущего игрока есть хотя бы одна карта, ему необходимо сбросить верхнюю карту в колоде;
- следующий ход переходит к игроку, имя которого начинается с буквы на сброшенной карте (a - Антонин, b - Бальбин, c - Цезарь);
- если колода текущего игрока пуста, игра заканчивается, и текущий игрок выигрывает игру.
Вам выдаются начальные колоды игроков (Sa, Sb, Sc). Состояние колоды Антонина записано в строке Sa, где i-й (\(1<=i<=len(S_a)\)) символ это буква в i-й карты в колоде. Строка Бальбина (Sb) и строка Цезаря (Sс) описываются таким же образом. 
Определите победителя в игре.

Формат входных данных
На вход подаются три ненулевых строки Sa, Sb и Sc, каждая с новой строки. Длина каждой строки не более 100 символов. Каждая строка состоит только из букв a, b или c.

Формат выходных данных
Если выиграл Антонин. то выведите букву A, если Бальбин - букву B, если Цезарь - букву C.

Примечание 
В первом тестовом примере игра будет развиваться следующим образом:
Антонин сбрасывает верхнюю карту своей колоды, a. Антонин делает следующий ход.
Антонин сбрасывает верхнюю карту своей колоды, с. Цезарь следующий.
Цезарь сбрасывает верхнюю карту своей колоды, с. Цезарь следующий.
Цезарь сбрасывает верхнюю карту своей колоды: a. Антонин делает следующий ход.
Антонин сбрасывает верхнюю карту своей колоды: a. Антонин делает следующий ход.
Колода Антонина пуста. Игра заканчивается, и Антонин выигрывает игру.

 

Алёна собирает вещи в отпуск. С собой в самолёт она может взять ручную кладь и багаж. Для ручной клади у Алёны есть рюкзак, а для багажа – огромный чемодан.
По правилам перевозки масса ручной клади не должна превосходить S кг, а багаж может быть любой массы (за сверхнормативный багаж Алёна готова доплатить). Разумеется,
наиболее ценные вещи – ноутбук, фотоаппарат, документы и т. д. – Алёна хочет положить в ручную кладь.
Алёна разложила все свои вещи в порядке уменьшения их ценности и начинает складывать наиболее ценные вещи в рюкзак. Она действует следующим образом – берёт
самый ценный предмет, и если его масса не превосходит S, то кладёт его в рюкзак, иначе кладёт его в чемодан. Затем она берёт следующий по ценности предмет, если его можно
положить в рюкзак, то есть если его масса вместе с массой уже положенных в рюкзак вещей не превосходит S, то кладёт его в рюкзак, иначе в чемодан, и таким же образом процесс
продолжается для всех предметов в порядке убывания их ценности.
Определите вес рюкзака и чемодана после того, как Алёна сложит все вещи.

Первая строка входных данных содержит число S – максимально разрешённый вес рюкзака. Во второй строке входных данных записано число N – количество предметов.
В следующих N строках даны массы предметов, сами предметы перечислены в порядке убывания ценности (сначала указана масса самого ценного предмета, затем масса второго по
ценности предмета и т. д.). Все числа натуральные, число S не превосходит 2×10⁹, сумма весов всех предметов также не превосходит 2×10⁹. Значение N не превосходит 10⁵.

Программа должна вывести два числа – вес рюкзака и вес чемодана (вес пустого рюкзака и чемодана не учитывается).

Примеры

№	Входные данные	Выходные данные	Пояснение
1	20 5 6 10 5 2 3	18 8	Максимально возможная масса рюкзака 20 кг. Дано 5 предметов весом 6, 10, 5, 2, 3. Сначала предмет весом 6 кладётся в рюкзак, затем предмет весом 10 тоже кладётся в рюкзак. Предмет весом 5 нельзя положить в рюкзак, так как тогда вес рюкзака станет 21 кг, поэтому предмет весом 5 кладётся в чемодан. Затем предмет весом 2 кладётся в рюкзак, а предмет весом 3 – в чемодан. Вес рюкзака 6 + 10 + 2 = 18, вес чемодана 5 + 3 = 8.

Посередине озера плавает плот, имеющий форму прямоугольника. Стороны плота направлены вдоль параллелей и меридианов. Введём систему координат, в которой ось OX направлена на восток, а ось ОY – на север. Пусть юго-западный угол плота имеет координаты (x₁, y₁), северо-восточный угол – координаты (x₂, y₂).
Пловец находится в точке с координатами (x, y). Определите, к какой стороне плота (северной, южной, западной или восточной) или к какому углу плота (северо-западному, северо-восточному, юго-западному, юго-восточному) пловцу нужно плыть, чтобы как можно скорее добраться до плота.
Программа получает на вход шесть чисел в следующем порядке: x₁, y₁ (координаты юго-западного угла плота), x₂, y₂ (координаты северо-восточного угла плота), x, y (координаты пловца). Все числа целые и по модулю не превосходят 100. Гарантируется, что x₁ < x₂, y₁ < y₂, x ≠ x₁, x ≠ x₂, y ≠ y₁, y ≠ y₂, координаты пловца находятся вне плота.
Если пловцу следует плыть к северной стороне плота, программа должна вывести символ «N», к южной – символ «S», к западной – символ «W», к восточной – символ «E». Если пловцу следует плыть к углу плота, нужно вывести одну из следующих строк: «NW», «NE», «SW», «SE».
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	-1 -2 5 3 -4 6	NW

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

Входные данные
На вход подается строка. Длина строки не нулевая и не более 100 символов. Строка состоит только из строчных английских букв (a-z).

Выходные данные
Выведите Yes если s красива, в противном случае, выведите No.
 

 

Примеры

№	Входные данные	Выходные данные
1	abaccaba	Yes
2	hthth	No

 

Некоторый отель установил следующую плату за проживание:

• X рублей за ночь, за первые K ночей;
• Y рублей за ночь, за (K+1)-ю и последующие ночи.

Громозека решил остаться в этом отеле на N последовательных ночей. Посчитайте общую стоимость проживания Громозеки в данном отеле.

Входные данные
На вход подаются 4 положительных целых числа: N, K, X, Y (\(1<=N,K<=10000\); \(1<=Y<X<=10000\)). По одному числу в строке.

Выходные данные
Выведите на экран общую стоимость размещения в данном отеле.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 3 10000 9000	48000	Стоимость размещения: 10000 руб. за 1-ю ночь; 10000 руб. за 2-ю ночь; 10000 руб. за 3-ю ночь; 9000 руб. за 4-ю ночь;; 9000 руб. за 5-ю ночь; Итого: 48000 рублей.
2	2 3 10000 9000	20000

 

Громозека построил собственную клавиатуру. Эта клавиатура разработана для максимальной простоты, на ней всего 3 клавиши: клавиша 0, клавиша 1 и клавиша backspace.

Тестировать собственную клавиатуру Громозека решил в текстовом редакторе. Этот редактор всегда отображает одну строку (возможно, пустую). При запуске редактора эта строка пуста. При нажатии каждой клавиши на клавиатуре в строке происходят следующие изменения:
- клавиша 0: символ 0 будет вставлен справа от строки;
- клавиша 1: символ 1 будет вставлен справа от строки;
- клавиша backspace: если строка пуста, ничего не происходит. В противном случае удаляется крайняя правая буква строки.

Громозека запустил редактор и несколько раз нажал эти клавиши. Вам дана строке s, которая является записью нажатий клавиш по порядку. В этой строке символ 0 обозначает клавишу 0, символ 1 обозначает клавишу 1, а символ B обозначает клавишу backspace. Определите какая строка теперь отображается в редакторе?

Входные данные
На вход подается строка s (\(1 <= len(s) <=10\)). Строка состоит из символов 0, 1 или B.

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

№	Входные данные	Выходные данные
1	01B0	00
2	0BB1	1

 

У Ирохи есть последовательность из 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

 

Ироха любит Хайку. Хайку - это жанр традиционной японской лирической поэзии вака, известный с XIV века. Хайку состоит из трех фраз с 5, 7 и 5 слогами, именно в такой последовательности (схема 5-7-5). Для создания Хайку Ироха придумала три разные фразы. В этих фразах a, b и с слогов соответственно. Определите, может ли Ироха построить Хайку, используя каждую из фраз один раз в определенном порядке. 

Входные данные
На вход подаются три натуральных числа a, b и с (\(1 <= a, b, c <= 10\)) .

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

 

Примеры

№	Входные данные	Выходные данные
1	5 5 7	YES
2	5 7 7	NO

Ручка стоила K рублей. Первого сентября стоимость ручки увеличилась ровно на P процентов. Определите, сколько ручек можно купить на S рублей после подорожания.
Программа получает на вход три целых положительных числа. Первое число K – стоимость ручки в рублях до подорожания. Второе число P – величина подорожания ручки
в процентах. Третье число S – имеющаяся сумма денег. Числа K и S не превосходят 10⁷ , число P не превосходит 100.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	33 5 100	2	Ручка стоила 33 рубля. После подорожания на 5 % ручка будет стоить 34 рубля 65 копеек (заметим, что, поскольку первоначальная цена ручки была целым числом рублей, после подорожания стоимость ручки будет выражаться целым числом рублей и копеек). На 100 рублей после подорожания можно купить 2 ручки.

Имеется 4-мерный массив X, каждый индекс которого может принимать значения от 1 до N. Вы должны построить новый 4-мерный массив Y , элементы которого должны принимать следующие значения: Y [i₁, i₂, i₃, i₄] = min(X[j₁, j₂, j₃, j₄]), где 1 ≤ i_k ≤ N − M + 1, i_k ≤ j_k ≤ i_k + M − 1, а M -  заданное число.

Входные данные
В первой строке входного файла задаются N и M (1 ≤ M ≤ N). Остальные строки файла содержат элементы массива X. Количество элементов не будет превышать 1500000 и сами они будут целыми числами, не превышающими по абсолютному значению 10⁹. Они расположены в таком порядке, что считать их можно с помощью псевдокода:

for i = 1 to N:
for j = 1 to N:
for k = 1 to N:
for l = 1 to N:
read X[i, j, k, l]

Выходные данные
Выведите искомый массив Y в том же формате, в котором был дан массив X.
 

Примеры

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

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

Формат входного файла
В первой строке задается N — количество звезд на небе (3  ≤ N ≤ 300000). В каждой из следующих N строк заданы целые X, Y (|X, Y| ≤  10⁹) — координаты соответствующей звезды.

Формат выходного файла
Выведите ответ к задаче.
 

Примеры

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

Как известно, при разработке и отладке программ большую помощь могут оказать игрушечные жёлтые уточки (см. статью «Метод утёнка» в википедии), поэтому Денис собрал большую коллекцию жёлтых уточек. Коллекция уже настолько большая, что Денис решил расставить уточек на полки шкафа. Сначала он начал ставить на каждую полку по A уточек, но одна уточка оказалась лишней. Тогда он заново начал расставлять уточек на полки, ставя на каждую полку по B уточек, но в этом случае ему не хватило одной уточки, чтобы на каждой полке оказалось ровно B уточек. Определите минимальное число уточек, которое могло быть в коллекции Дениса.
Программа получает на вход два целых положительных числа A и B, 2 ≤ A ≤ 2×10⁹, 2 ≤ B ≤ 2×10⁹ – количество уточек при расстановке на полке в первом и во втором случаях.
Программа должна вывести одно число – минимально возможное количество уточек в коллекции Дениса. Гарантируется, что ответ существует и не превосходит 2×10⁹.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 3	11	11 = 5 × 2 + 1 11 = 3 × 4 − 1