Информатика

Дано число. В этом числе необходимо изменить одну цифру таким образом, чтобы новое число делилось на 3 и было бы максимально возможным. В исходном числе нужно
обязательно изменить одну цифру, даже если исходное число уже делилось на 3. Программа получает на вход одно длинное натуральное число. Длина числа может
достигать 100 цифр.
Программа должна вывести другое натуральное число, удовлетворяющее условиям:
1. Новое число должно отличаться от данного ровно одной цифрой.
2. Новое число должно делиться на 3.
3. Новое число должно быть максимально возможным из всех таких чисел.

Примеры

№	Входные данные	Выходные данные
1	123	723

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

Примеры

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

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

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

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

Примеры

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

Алёна собирает вещи в отпуск. С собой в самолёт она может взять ручную кладь и багаж. Для ручной клади у Алёны есть рюкзак, а для багажа – огромный чемодан.
По правилам перевозки масса ручной клади не должна превосходить 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

 

Ироха любит Хайку. Хайку - это жанр традиционной японской лирической поэзии вака, известный с 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 ручки.

У вас есть таблица c N строками и M столбцами. В каждой ячейке таблицы записана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла до правого нижнего угла, если вам разрешено идти только вправо и вниз. Конкатенация букв в порядке обхода составляют строку. Скажем, что эта строка - значение пути. Теперь рассмотрим все такие пути и отсортируем их значения в алфавитном порядке. Ваша задача найти значение K-го пути в этом отсортированном листе.

Входные данные
В первой строке задается два целых числа N - количество рядов и M - количество столбцов заданной таблицы (1 <= N, M <= 30). Каждая из следующих N строк содержит ровно M строчных букв английского алфавита. Последняя строка входного файла содержит целое число K (1 <= K <= 10¹⁸). Гарантируется, что для K ответ всегда существует.

Выходные данные
Выведите ответ на задачу

Пояснения к примеру
abcdgk, abcdgk, abcdjk, abfdgk, abfdjk, abfijk, aefdgk, aefdjk, aefijk, aehijk
 

Примеры

№	Входные данные	Выходные данные
1	3 4 abcd efdg hijk 4	abfdgk

Вы хотите, чтобы небоскребы в вашем городе имели красивый вид. Решено построить N небоскребов в ряд. У небоскреба с номером i должно быть ровно h[i] этажей.

У Вас есть предложения от различных строительных компаний. Первая из них предлагает строить один этаж в любом из небоскребов за 3 миллиона евро. Вторая предлагает строить по одному этажу в каждом из двух соседних небоскребов за 5 миллионов евро. Заметим, что не имеет значения, находятся ли эти этажи на одинаковой высоте или нет. Третья компания предлагает строить по одному этажу в каждом из трех последовательных небоскребах за 7 миллионов евро.

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

Входные данные
Первая строка содержит одно целое число N (1 ≤ N ≤ 300). Вторая строка содержит N целых чисел h[1], h[2] ..., h[N], 1 ≤ h[i] ≤ 200.

Выходные данные
В единственной строке выведите одно целое число: минимальную сумму денег для строительства, в миллионах.

Дана сетка с N + 1 рядами и M + 1 столбцами. Черепаха находится на клетке (0, 0) и хочет попасть в клетку (N, M). Черепаха может идти только вверх или вправо. На сетке в K клетках находятся ловушки. Если черепаха пойдет в одну из этих клеток, то она перевернется. У черепашки есть силы для того, чтобы встать не более чем T раз. Посчитайте, сколькими различными путями черепаха может попасть в клетку (N, M). Так как это число может быть очень большим, выведите остаток от его деления на Z.

Входные данные
В первой строке входного файла задается 5 целых чисел: N, M, K, T и Z (1 ≤ N,M ≤ 300000, 0 ≤ K, T  20, 1 ≤ Z ≤ 10⁹). В каждой из следующих K строк расположены координаты соответствующей клетки с ловушкой X, Y (0 ≤ X ≤ N, 0 ≤ Y ≤ M). Гарантируется, что все клетки с ловушками различные и в клетках (0, 0) и (N, M) ловушек нет.

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

Примеры

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

Имеется 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

Маша любит чётные числа, а Миша – нечётные. Поэтому они всегда радуются, если встречают числа, которые им нравятся.
Сегодня им встретились все целые числа от A до B включительно. Маша решила посчитать сумму всех чётных чисел от A до B, а Миша – сумму всех нечётных, после чего они начали спорить, у кого получилась сумма больше. Помогите им – найдите разность
между суммой Маши и суммой Миши.
Программа получает на вход два целых положительных числа A и B, не превосходящие 2×10⁹.
Программа должна вывести одно число – разность между суммой чётных чисел и суммой нечётных чисел от A до B.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 6	2	Сумма чётных чисел равна 4 + 6 = 10, сумма нечётных чисел равна 3 + 5 = 8, разность равна 2.
2	3 7	-5	Сумма чётных чисел равна 4 + 6 = 10, сумма нечётных чисел равна 3 + 5 + 7 = 15, разность равна −5.

Таня решила позвонить своей подруге, но вспомнила, что та живёт очень далеко, поэтому в часовом поясе подруги может быть слишком поздно или рано. Часы у Тани показывают ровно H часов, Таня живёт в часовом поясе с ними UTC+A, а её подруга – в часовом поясе UTC+B. Помогите Тане определить время в часовом поясе подруги в этот момент.
Программа получает на вход три целых числа H, A и B, 0 ≤ H ≤ 23, −11 ≤ A ≤ 12, −11 ≤ B ≤ 12.

В часовом поясе UTC+A местное время больше, чем время в часовом поясе UTC+0 на A часов (если же A < 0, то меньше на |A| часов). Например, если в часовом поясе UTC+0 сейчас 12 часов, то в часовом поясе UTC+1 – 13 часов, а в часовом поясе UTC−1 – 11 часов. 
Программа должна вывести одно число – время (количество часов) в часовом поясе подруги.
Под временем в этой задаче подразумевается количество часов, которое может принимать значения от 0 до 23. При решении задачи обратите внимание, что в часовом поясе подруги может быть уже следующая дата или предыдущая дата, программа должна вывести количество часов на часах подруги в этот момент, то есть число от 0 до 23.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	15 3 -5	7	У Тани – 15 часов, она живёт в часовом поясе UTC+3. В часовом поясе UTC+0 сейчас 12 часов. Подруга живёт в часовом поясе UTC−5, и у неё сейчас 7 часов.

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


Шахматную доску повернули на 90° по часовой стрелке. Выведите получившуюся расстановку ладей.


Входные данные
Первая строка входных данных содержит целое число N, 1 ≤ N ≤ 10⁵ — размер доски. Следующие N строк содержат по одному числу от 1 до N, а именно, в i-й строке записано число a_i — номер вертикали, в которой стоит ладья на i-й горизонтали. В этой задаче горизонтали нумеруются числами от 1 до N сверху вниз, вертикали нумеруются числами от 1 до N слева направо (см.рисунок).

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

Примеры

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

Замечание
Пример в условии соответствует рисункам. Первоначально ладьи стояли в столбцах 4, 2, 3, 5, 1
при перечислении их по строкам сверху вниз. После поворота ладьи стоят в столбцах 1, 4, 3, 5, 2.

 

На складе кондитерской фабрики хранятся пирожные двух видов - круассаны и эклеры. Круассанов A штук, а эклеров - B штук. Есть неограниченный запас подарочных коробок, в каждую коробку можно положить только три пирожных. При этом требуется, чтобы в коробке были пирожные обоих видов, то есть в одну коробку можно положить два круассана и один эклер или один круассан и два эклера.
Определите, можно ли упаковать все имеющиеся пирожные в коробки и выведите подходящий способ размещения пирожных по коробкам.


Входные данные
Программа получает на вход два целых числа A и B, записанных в отдельных строках. 1 <= A <= 10⁹, 1 <= B <= 10⁹.

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

Примеры

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