Задача 1. Цензура ≡

Условие

В государстве Алюкобондии введена цензура на всех письменных СМИ. В соответствии с новым законом, все строки S1 во всех текстах должны быть заменены на строки S2. Помогите редактору Густаву автоматизировать этот процесс.

Формат входного файла

Входной файл содержит три строки: исходный текст, текст, который нужно заменить, текст на который нужно заменить.

Формат выходного файла

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

Ограничения

1 ≤ length(S) ≤ 1000 1 ≤ length(S 1), length(S 2) ≤ 50

Примеры тестов

Hello World
Hello
Hell

Hell World

Задача 2. Миллион Z ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
A 1 50
X 90 1000
D 30 1000000

2

Задача 3. Knapsack problem ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 7
1 5 6

1 0 1

Задача 4. Частичная дефрагментация ≡

Условие

Оперативная память компьютера имеет объём V байт, пронумерованных от 0 до V − 1. Выделенные блоки памяти задаются последовательностью адресов (a₁, b₁), (a₂, b₂), … (a_N, b_N). Блоки отсортированы по адресам и не перекрываются, т. е. 0 ≤ a_i ≤ b_i < a_{i + 1} < V.

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

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

Формат входного файла

Формат выходного файла

• номер блока, который нужно перемещать;
• 0, если блоки перемещать не нужно (непрерывный участок нужного объёма есть сразу);
• −1, если решения нет (пространство нужного объёма освободить не удаётся).

Ограничения

Примеры тестов

10 2 4
1 5 7 7

2

Задача 5. Барбара ≡

Условие

На некотором языке все слова записываются заглавными латинскими буквами, и состоят из слогов. Слогом называется непустая последовательность согласных, заканчивающаяся гласной. Все остальные последовательности букв словами этого языка не являются. Например, слово BARBARA состоит из трех слогов — BA, RBA и RA. Последовательности букв ААХ, Е, К, АНА словами не являются. Осмысленными считаются слова, в которых все согласные различны.

По данной последовательности из N заглавных латинских букв определить, является ли она осмысленным словом и, если да, то сколько различных слогов можно составить из букв этого слова. Например, из слова BARAKA можно составить 15 слогов — BA, KA, RA, BKA, KBA, BRA, RBA, KRA, RKA, BKRA, BRKA, RBKA, RKBA, KBRA, KRBA.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

BARAKA

15

Задача 6. Слово из кубиков ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS

2 5 3 4

Задача 7. Лабиринт ≡

Условие

Лабиринт размером N x N клеток задан массивом символов. Символ '#' обозначеет стену, символ '.' — проход. Передвигаться по лабиринту можно шагами по горизонтали или вертикали, но не по диагонали.

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

Формат входного файла

Первая строка входного файла содержит размер лабиринта N.

Следующие N строк содержат по N символов — описание лабиринта.

Формат выходного файла

Выходной файл должен содержать единственное целое число — длину кратчайшего пути, либо −1, если пути не существует

Ограничения

Примеры тестов

2
.#
..

2

2
.#
#.

-1

Задача 8. Бармаглот под одеялом ≡

Условие

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

Одеяло и Бармаглот имеют форму ломаных, заданных целочисленными координатами вершин (x₁, y₁), (x₂, y₂), … (x_N, y_N) для одеяла, (u₁, v₁), (u₂, v₂), … (u_M, v_M) для Бармаглота. При этом x_{i + 1} > x_i и u_{i + 1} > u_i для всех i.

Чтобы спрятаться под одеялом, Бармаглот должен полностью под него поместиться, т.е. описывающая его ломаная должна целиком находиться ниже ломаной, описывающей одеяло. Касания ломаных разрешены.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 0 0 5 5 6 0
4 0 0 2 1 5 5 6 0

CRY

Задача 9. Столкновение шариков ≡

Условие

По горизонтальной плоской поверхности катятся два шарика радиуса R метров каждый. В начальный момент времени шарики имеют координаты центров (x₁, y₁) и (x₂, y₂) метров, а также проекции скоростей на координатные оси (dx₁, dy₁) и (dx₂, dy₂) метров в секунду соответственно.

Требуется найти время в секундах, спустя которое шарики столкнутся, или определить, что этого не произойдёт.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

1
0 0 10 0
50 0 -10 0

2.4

Задача A. День рождения ≡

Условие

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

Формат входного файла

Входной файл содержит три целых числа N, M, K

Формат выходного файла

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

Ограничения

1 ≤ N, M ≤ 1000 0 ≤ K ≤ 1000

Примеры тестов

1 1 1

0 1

3 4 5

2 0

Задача B. Мутанты с планеты Икс ≡

Условие

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

Формат входного файла

Входной файл содержит два целых числа N и M.

Формат выходного файла

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

Ограничения

0 ≤ N, M ≤ 1000000

Примеры тестов

1 1

1000000001

Задача C. Студенты ≡

Условие

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

Формат входного файла

Входной файл содержит три целых числа (A, B, C) - количество студентов в каждой из трех групп.

Формат выходного файла

Выходной файл должен содержать одно целое число - количество "лишних" студентов.

Ограничения

0 ≤ A, B, C ≤ 1000000

Примеры тестов

40 25 30

5

Задача D. Квадратное уравнение ≡

Условие

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

Формат входного файла

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

Формат выходного файла

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

Ограничения

0 ≤ a, b, c ≤ 1000

Примеры тестов

3 5 2

-0.6667 -1.0000

0 7.245 -5.222

0.7208 0.7208

Задача E. Задача на ветвление 1 ≡

Условие

Даны три числа a, b, c. Если их сумма - четное число, то вывести самое меньшее из них, если сумма - нечетное, то – наибольшее.

Формат входного файла

Входной файл содержит три целых числа

Формат выходного файла

Выходной файл должен содержать одно целое число

Ограничения

0 ≤ a, b, c ≤ 1000

Примеры тестов

1 2 3

1

Задача F. Задача на ветвление 2 ≡

Условие

Даны четыре числа a, b, c, d. Если их сумма - четное число и произведение неотрицательное, то вывести наибольшее из них, если сумма - нечетное число и произведение неотрицательное , то вывести наименьшее из них,если произведение - отрицательное число, то вывести сумму всех четных чисел.

Формат входного файла

Входной файл содержит четыре целых числа

Формат выходного файла

Выходной файл должен содержать одно целое число

Ограничения

 − 1000 ≤ a, b, c, d ≤ 1000

Примеры тестов

1 2 3 4

4

Задача G. Целочисленный калькулятор ≡

Условие

Необходимо написать целочисленный калькулятор. Даны два числа и знак операции: "+" "-" "*" "/". Необходимо произвести целочисленную операцию над числами соответственно знаку и вывести результат в файл. В случае деления на ноль вывести "-1 -1".

Формат входного файла

Входной файл через пробел содержит два целых числа и знак операции.

Формат выходного файла

Выходной файл должен содержать одно целое число.

Ограничения

 − 1000 ≤ a, b ≤ 1000

Примеры тестов

5 5 +

10

5 0 /

-1 -1

Задача H. Студенты и деканат ≡

Условие

Условия задачи C "Студенты". Теперь необходимо помимо того, что вывести «лишних студентов», еще и вывести указания для деканата. Из какой группы в какую сколько студентов нужно перевести, чтобы в общем количество «лишних» студентов оказалось минимальным.

Формат входного файла

Входной файл содержит три целых неотрицательных числа a,b,c.

Формат выходного файла

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

Ограничения

2 ≤ a, b, c ≤ 1000

Примеры тестов

45 25 30

10 
1 2 5 

25 30 30

0

Задача I. Целочисленный намотайзер ≡

Условие

Во входном файле даны целые числа (количество - произвольное). Необходимо считать из файла столько чисел, чтобы их сумма была больше 10. Вывести в выходной файл количество считанных чисел. Если же сумма всех чисел в файле не превосходит 10, то вывести в выходной файл "-1".

Формат входного файла

Входной файл содержит произвольное количество целых чисел

Формат выходного файла

Выходной файл должен содержать одно целое число.

Ограничения

0 ≤ Количество ≤ 1000 0 ≤ Числа ≤ 1000000

Примеры тестов

5 6

2

5 5

-1

Задача J. Фибоначчи ≡

Условие

Необходимо вывести N первых чисел Фибоначчи, начиная с 0.

Формат входного файла

Входной файл содержит одно целое неотрицательное число N.

Формат выходного файла

Выходной файл должен содержать N первых чисел последовательности Фибоначчи.

Ограничения

0 ≤ N ≤ 94

Примеры тестов

2

0 1

Задача K. НОД и НОК ≡

Условие

Необходимо вычислить НОД и НОК для пары целых положительных чисел a и b.

Формат входного файла

Входной файл содержит два целых положительных числа.

Формат выходного файла

Выходной файл должен содержать НОД и НОК пары чисел.

Ограничения

1 ≤ a,b ≤ 10⁶

Примеры тестов

2 3

1 6

24 28

4 168

Задача L. Простые числа ≡

Условие

Необходимо вывести N простых чисел в порядке их возрастания.

Формат входного файла

Входной файл содержит одно целое неотрицательное число N.

Формат выходного файла

Выходной файл должен содержать N первых простых чисел в порядке их возрастания.

Ограничения

0 ≤ N ≤ 1000

Примеры тестов

1

2

3

2 3 5

Задача M. Туда - Сюда ≡

Условие

Дана последовательность из N целых чисел. Нужно вывести эту последовательность в обратном порядке.

Формат входного файла

В первой строчке входной файл содержит целое неотрицательное число N. В следующей строке идут N целых чисел.

Формат выходного файла

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

Ограничения

0 ≤ N ≤ 1000  − 1000000 ≤ Числа ≤ 1000000

Примеры тестов

1
1

1

5
1 2 3 4 5

5 4 3 2 1

Задача O. Гороскоп и другая ерунда ≡

Условие

В группе учатся N студентов, но ребята никак не могут решить, кому с кем дружить. Недавно выяснилось, что это можно наверняка узнать с помощью гороскопа. Знак зодиака задается числом от 1 до 12 и называется числом зодиака. Если остаток от деления на три суммы чисел зодиака двух людей равен нулю, то ребята подружаться. Если остаток от деления равен единице, то будут нейтрально общаться, если же остаток – двойка, то вражды не миновать. Зная имена и числа знака каждого из учеников группы, определите кто с кем в каких будет отношениях. Для этого необходимо составить таблицу совместимости. Таблица совместимости – квадратная матрица NxN, где в i,j ячейке – остаток от деления на три суммы чисел зодиака I-ого и J-ого ученика.

Формат входного файла

Входной файл содержит число N и далее N чисел зодиака каждого из студентов.

Формат выходного файла

Выходной файл должен содержать таблицу совместимости в виде квадратной матрицы NxN.

Ограничения

2 ≤ N ≤ 1000

Примеры тестов

2
1 2

2 0 
0 1 

5
5
12
2
7
8

1 2 1 0 1 
2 0 2 1 2 
1 2 1 0 1 
0 1 0 2 0 
1 2 1 0 1 

Задача P. Морской бой ≡

Условие

Игра «Морской Бой». Дано поле размером NxM. На поле единицей отмечены позиции палуб, нулем - отсутствие палубы. Нужно определить размер самого большого возможного корабля на поле по количеству палуб. Корабли на поле могут «соприкасаться» друг с другом как по горизонтали так и по вертикали. Кораблем считается только сочетание нескольких палуб в ряд или по строке (без изгибов и диагоналей)

Формат входного файла

Входной файл содержит два целых положительных числа N и M. Далее идут N*M чисел, означающие матрицу N*M, каждое из чисел может принимать значения 0 либо 1.

Формат выходного файла

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

Ограничения

0 ≤ N, M ≤ 100

Примеры тестов

5 5
0 0 1 1 1
0 1 0 0 0
0 1 0 0 1
0 1 0 0 1
0 1 0 0 0

4

7 10
0 0 0 1 0 0 0 1 0 1 
1 0 1 1 0 0 1 0 0 1 
0 0 0 1 1 0 0 0 1 0 
1 0 1 1 0 1 0 0 1 0 
0 1 1 1 1 1 0 0 0 0 
0 0 1 0 0 0 0 1 1 0 
0 0 1 0 1 1 0 0 0 0 

5

Задача Q. Светофор ≡

Условие

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

Формат входного файла

Входной файл состоит из одной строки, задающей цвет светофора — RED, YELLOW, GREEN.

Формат выходного файла

В выходном файле должна быть одна строка - YES или NO.

Примеры тестов

RED

NO

Задача R. В ожидании Нового года ≡

Условие

31 декабря. Марфа Геннадьевна и Глафира Сергеевна уже приготовили новогодний ужин, и теперь они с нетерпением ждут Нового года.

Каждые 5-10 минут они смотрят на часы и вычисляют, сколько часов и минут осталось до Нового года. При этом на вычисление у них уходит много времени.

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

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

Формат входного файла

Входной файл содержит текущее время — часы и минуты.

Формат выходного файла

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

Ограничения

Часы от 0 до 23. Минуты от 0 до 59.

Примеры тестов

12 0

12 0

23 59

0 1

22 25

1 35

Задача S. Время в пути ≡

Условие

Время отправления и время прибытия поезда задаются в виде Ч М, где Ч - час от 0 до 23, М - минута от 0 до 59. Время в пути задаётся аналогично в формате Ч М, где Ч - количество часов от 0 до 999, а М - количество минут от 0 до 59.

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

Формат входного файла

Формат выходного файла

Примеры тестов

18 25
7 37

2 2

Задача T. Сложение массива чисел ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
1 2 3

6

Задача U. Уравнение для 5 класса ≡

Условие

Уравнение для пятиклассников представляет собой строку длиной 5 символов. Второй символ строки является либо знаком '+' (плюс) либо '-' (минус), четвёртый символ — знак '=' (равно). Из первого, третьего и пятого символов ровно два являются цифрами из диапазона от 0 до 9, и один — буквой x, обозначающей неизвестное.

Требуется решить данное уравнение относительно x.

Формат входного файла

Формат выходного файла

Примеры тестов

x+5=7

2

3-x=9

-6

Задача V. Сложение неотрицательных длинных чисел ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
5

8

100000000000000000000
29

100000000000000000029

Задача W. Перевод длинных чисел ≡

Условие

Дано неотрицательное целое число a, записанное в системе счисления по основанию p. Требуется перевести это число в систему счисления по основанию q. Для представления цифр больше 9 используются заглавные латинские буквы (A — 10, B — 11, …, Z — 35).

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2 10
10010

18

31 17
AF2J5

6DG3BE

Задача X. Обход матрицы: обход 'змейкой' ≡

Условие

• в левом верхнем углу находится число 1
• далее числа распологаются "змейкой", т.е. по возрастанию слева направо в нечётных строках, и справа налево — в чётных

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2

1 2
4 3

3

1 2 3
6 5 4
7 8 9

Задача Y. Обход матрицы: спиральный обход ≡

Условие

• в левом верхнем углу находится число 1
• далее числа располагаются по спирали, закрученной вправо и внутрь

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2

1 2
4 3

3

1 2 3
8 9 4
7 6 5

Задача Z. Умножение неотрицательных длинных чисел ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
5

15

100000000000000000000
29

2900000000000000000000