Задача 1. FizzBuzz ≡

Условие

Требуется написать программу, которая считывает число и выводит Fizz, если число делится на 3, Buzz, если число делится на 5, и FizzBuzz, если оно делится и на 3, и на 5. Если число не делится ни на 3, ни на 5, вывести пустую строку (перевод строки).

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

23

25

Buzz

30

FizzBuzz

Задача 2. Олины торты ≡

Условие

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

Формат входных данных

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

Формат выходных данных

Необходимо вывести единственное число — максимальное количество сахара.

Ограничения

1 < N, M < 10000

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

10
2

5

6
4

1.5

Задача 3. Энтое слово ≡

Условие

Вам даны фраза и положительное число — позиция слова. Необходимо вывести слово, находящееся в фразе на этой позиции. Если данное число больше, чем количество слов в фразе, то вывести последнее слово.

Формат входных данных

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

Формат выходных данных

Выходные данные должны содержать искомое слово.

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

FEFU was established in 1899 as the Eastern Institute
5

1899

FEFU was established
5

established

Задача 4. Палиндром? ≡

Условие

Палиндром — это слово или фраза, которые одинаково читаются слева направо и справа налево (без учета пробелов и регистра символов).

Формат входных данных

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

Формат выходных данных

Выходные данные должны содержать True, если фраза — палиндром, и False в противном случае.

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

А роза упала на лапу Азора

True

Роза не упала на лапу Азора

False

Задача 5. Солнечный день ≡

Условие

Ваша лодка потерпела крушение! Но вы и не против, сидите себе спокойно и каждые 10 минут выливаете за борт X литров воды. При этом каждую минуту через пробоину поступает Y литров воды. При условии, что в таком темпе вы никогда не вычерпаете воду полностью, сколько литров воды будет в вашей лодке через T минут?

Формат входных данных

Входные данные содержат целые числа X, Y и T, по одному числу в строке.

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

10
1
15

5

1000
9
9

81

Задача 6. Key sort ≡

Условие

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

Формат входных данных

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

Формат выходных данных

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

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

azx zab ddd

zab ddd azx

Задача 7. Убрать соседа ≡

Условие

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

Формат входных данных

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

Формат выходных данных

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

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

1 2 0 3 4 0 5 10

1 0 3 0 5 10

11 0 0 12

0 12

Задача 8. Dot первого и последнего столбцов матрицы ≡

Условие

Требуется написать программу, которая скалярно перемножает первый и последний столбец матрицы. Скалярным произведением двух векторов будет скалярная величина, равная сумме попарного произведения координат векторов (Например (1, 2, 3) ⋅ (3, 4, 5) = 1 * 3 + 2 * 4 + 3 * 5 = 26).

Формат входных данных

Первая строка содержит числа N и M — количество строк и столбцов матрицы. Следующие N строк содержат M чисел каждая — элементы матрицы.

Формат выходных данных

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

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

2 2
1 3
4 5

23

Задача 9. Количество каждого числа (курс Python) ≡

Условие

Вася записал в файл input.txt N чисел. Когда Петя открыл этот файл, он решил посчитать, сколько раз в файле записано каждое число.

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

Заметим, что это позволяет выполнить сортировку массива чисел по возрастанию при помощи простого подсчёта.

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

Входной файл содержит целое число N, за которым следуют N целых чисел a_i.

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

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

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

Ограничения

1 ≤ N ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

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

4
1 2 1 0

0 1
1 2
2 1

7
9 1 3 2 3 -2 7

-2 1
1 1
2 1
3 2
7 1
9 1

Задача A1. Amazon ≡

Условие

Сказочные шахматы — раздел шахматной композиции. В произведениях этого раздела присутствуют изменения некоторых из общепринятых правил игры или применяются необычные фигуры или доски.

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

На обычной шахматной доске находятся белая амазонка и черный король. Определите, объявлен ли мат королю.

Формат входных данных

Первая строка входных данных содержит два натуральных числа, записанных через пробел: x₁ и y₁ — координаты белой амазонки. Во второй строке в том же формате содержатся координаты чёрного короля x₂ и y₂. Гарантируется, что позиции фигур различны.

Формат выходных данных

Выведите Yes или No — ответ на вопрос задачи.

Ограничения

1 ≤ x₁, x₂, y₁, y₂ ≤ 8

Пояснение к примерам

Смотри рисунок. Во втором примере король может атаковать амазонку.

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

7 6
7 8

Yes

6 7
7 8

No

Задача A3. Circulation of try-square ≡

Условие

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

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

Формат входных данных

Входные данные содержат три натуральных числа a, b и n — длины деревянной и металлической внутренних сторон угольника и координата точки. Гарантируется, что a и b — катеты Пифагорова треугольника (то есть гипотенуза является целым числом).

Формат выходных данных

Выход должен содержать одно слово:

• wood, если точка соприкоснется с деревянной ручкой,
• metal, если точка соприкоснется с металлической доской,
• empty, если угольник не коснется точки.

Ограничения

3 ≤ a < b ≤ 1000

1 ≤ n ≤ 10⁹

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

3 4 11

wood

Задача A4. Attacking rooks ≡

Условие

На шахматной доске стоит пешка в координатах x, y (x — номер вертикали, y — номер горизонтали).

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

Формат входных данных

Входные данные содержат целые числа x и y.

Формат выходных данных

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

Ограничения

1 ≤ x, y ≤ 8

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

1 1

8

Задача A5. Just do it! ≡

Условие

Все, что от вас требуется, это вывести все возможные вариации фразы Just do it!, различающиеся лишь регистром отдельных символов (например jUst DO it!).

Формат выходных данных

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

Problem A6. Matrix detour: Spiral ≡

Statement

• 1 must be in the top left corner;
• increasing seqeunce of numbers must form a spiral, twisted clockwise and inside.

Input file format

Output file format

Constraints

Sample tests

2

1 2
4 3

3

1 2 3
8 9 4
7 6 5

Задача A7. Inner triangles ≡

Условие

Как-то раз Тимофей сидел на контрольной работе по математике. И свой вариант, и вариант соседки по парте, красавицы Алёны, давно были решены. От скуки Тимофей стал рисовать на клетчатом листочке-черновике.

Сперва от нарисовал большой квадрат со сторонами, лежащими на линиях клетчатой сетки и отметил все его вершины. Потом дополнительно отметил a точек на одной стороне квадрата, b на второй, c на третьей и d на четвертой. Теперь его интересует вопрос — сколько существует различных невырожденных треугольников с вершинами, лежащими в отмеченных точках?

Формат входных данных

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

Формат выходных данных

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

Ограничения

0 ≤ a + b + c + d ≤ 1000

Пояснение к первому примеру

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

1 0 0 0

9

1 2 3 4

329

Задача A8. Right triangle ≡

Условие

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

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

Формат входных данных

В первой строке входных данных заданы целые числа x₁ и y₁, во второй строке заданы целые числа x₂ и y₂, в третьей строке заданы целые числа x₃ и y₃ — координаты трех точек. Все точка попарно различные.

Формат выходных данных

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

Ограничения

 − 10⁴ ≤ x_i, y_i ≤ 10⁴

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

0 0
0 8
6 0

YES

1 2
3 2
4 1

NO

Задача A9. Fine segments ≡

Условие

Юному программисту Илье подарили на день рождения последовательность чисел a_i длиной n. Илья решил выделить из этой последовательности хорошие отрезки. Хорошим отрезком называется последовательность подряд идущих элементов a_i, содержащая внутри себя элемент, равный сумме своего первого и последнего элементов. Например, последовательность [1, 2, 5, 4] является хорошей, так как сумма самого левого и самого правого элементов равна 5, а число 5 есть в данной последовательности; последовательность [1, 2, 3, 4] не является хорошей, так как сумма самого левого и самого правого элементов дает нам 5, а числа 5 нет в данной последовательности. Требуется программу, которая посчитает количество хороших отрезков в данной последовательности.

Формат входных данных

В первой строке содержится целое число n — длина последовательности. Во второй строке содержится n целых чисел a_i — элементы последовательности. Все элементы последовательности различны.

Формат выходных данных

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

Ограничения

1 ≤ n ≤ 10³

1 ≤ a_i ≤ 10⁵

Пояснение к примерам

В первом примере один хорошой отрезок: [3, 7, 5, 4].

Во втором примере два хороших отрезка: [1, 5, 4] и [1, 5, 4, 7, 6].

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

5
3 7 5 4 8

1

5
1 5 4 7 6

2

Задача B1. Аргайл ≡

Условие

Аргайл — узор из ромбов или квадратов, расположенных в шахматном порядке и образующих параллельные и поперечные полосы разных цветов. Название происходит от имени шотландского клана Кампбел в графстве Аргайл. Особенную популярность этот орнамент получил в XX веке. Это случилось благодаря компании «Pringle of Scotland», которая стала выпускать элитный трикотаж с орнаментом «Аргайл», после чего он стал визитной картой аристократии. С тех пор узор не выходит из моды. Существует огромное количество цветовых решений этого орнамента. Особенно популярен этот узор на свитерах, жилетах, кардиганах, платьях, шарфах, носках и гетрах, сообщает Википедия.

Определите количество квадратов красного и зелёного цветов на ткани размером n × n.

Формат входных данных

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

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

Ограничения

1 ≤ n ≤ 10⁹

Пояснение к примерам

Смотри рисунок.

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

3

1
1

4

1
4

Задача B2. Большой куш Бендера ≡

Условие

Пти-шво (фр. маленькие лошадки) — старинная настольная азартная игра, появившаяся в Европе в XVIII веке. Игра представляла собой своеобразную имитацию скачек на ипподроме: пронумерованные рысаки, прикрепленные к спицам рулетки, вращались по кругу. На таких искусственных лошадей игроками делались ставки. Победителем становился тот из игроков, чья лошадь останавливалась на отметке «Финиш».

В организованном Остапом Бендером подпольном игровом клубе, каждый вечер собираются любители азартных развлечений. Жемчужиной заведения по праву считается копия московского ипподрома с движущимися по кругу игрушечными лошадками. Всего их n и каждая обладает своей угловой скоростью d_i, позволяющей ей за 1 секунду перемещаться по дуге d_i°.

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

Формат входных данных

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

Формат выходных данных

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

Ограничения

2 ≤ n ≤ 359

1 ≤ t ≤ 10⁹

1 ≤ d_i ≤ 359

Пояснение к примеру

В примере дано три лошадки. Забег длится 10 секунд, угловые скорости бегунов 25, 40 и 90 соответственно. Смотри рисунок. На момент окончания забега первой лошади до линии финиша останется пробежать дугу 360° − 10 × 25° = 110°. Вторая лошадка сделает один полный круг и остановится на расстоянии до финиша 320°. Третья сделает два полных круга и остановится точно на середине дорожки (180°). Победит первая лошадь, для неё угловое расстояние до финиша наименьшее.

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

3
10
25
40
90

1

Задача B3. Взвешивание матрёшек ≡

Условие

У Тимофея есть набор матрёшек, пронумерованных последовательными числами от 1 до n. Вес каждой матрёшки равен её номеру и любую матрёшку с номером a можно спрятать в матрёшку с номером b, если a < b.

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

Формат входных данных

Первая строка входных данных содержит натуральное число n — количество матрёшек у мальчика и одновременно номер матрёшки, стоящей на левой чаше весов. Вторая строка содержит натуральное число m — номер матрёшки, стоящей на правой чаше весов.

Формат выходных данных

Выведите True или False — ответ на вопрос, возможно ли расставить все n матрёшек описанным образом.

Ограничения

1 ≤ m < n ≤ 10⁹

Пояснения к примерам

Смотри рисунок. В первом примере на левой чаше стоит матрёшка с номером 4, на правой — с номером 3.

Если в левую матрёшку спрятать матрёшку с номером 1, а в правую — с номером 2, то все четыре матрёшки окажутся на весах и весы будут находиться в равновесии.

Во втором примере на левой чаше стоит матрёшка с номером 5, на правой — с номером 4.

Из восьми способов расположения остальных матрёшек на двух чашах ни один не даёт требуемого равновесия:

1) 5 + 3 + 2 + 1 ≠ 4

2) 5 + 3 + 2 ≠ 4 + 1

3) 5 + 3 + 1 ≠ 4 + 2

4) 5 + 3 ≠ 4 + 2 + 1

5) 5 + 2 + 1 ≠ 4 + 3

6) 5 + 2 ≠ 4 + 3 + 1

7) 5 + 1 ≠ 4 + 3 + 2

8) 5 ≠ 4 + 3 + 2 + 1

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

4
3

True

5
4

False

Задача B4. Горизонтальные слои квадратов ≡

Условие

Тимофей решил нарисовать прямоугольник по следующим правилам:

Сверху идёт горизонтальный слой квадратов со стороной 1;

Под ним располагается горизонтальный слой квадратов со стороной 2;

...

Последним будет горизонтальный слой квадратов со стороной n.

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

Формат входных данных

Единственная строка входных данных содержит натуральное число n — сторону наибольшего квадрата.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

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

Ограничения

2 ≤ n ≤ 40

Пояснение к примерам

Смотри рисунок.

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

2

3 2

3

6 6

4

10 12

Задача B5. Дорожка из плиток ≡

Условие

Тимофею необходимо уложить на узкой парковой дорожке размером 6 × n тротуарную плитку. У него есть неограниченное количество плиток двух типов: 2 × 2 и 3 × 3. Сколько существует различных способов заполнения дорожки? Заказчик требует качественной работы, поэтому плитки нельзя ломать, каждая плитка должна плотно прилегать к соседней без наложений, дорожка должна быть заполнена полностью, края плитки не могут выходить за пределы дорожки.

Формат входных данных

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

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

Ограничения

2 ≤ n ≤ 150

Пояснение к примеру

В примере дано n = 5. Смотри рисунок.

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

5

2

Задача C1. Вектор ≡

Условие

Дан целочисленный вектор P₁, P₂, …, P_N. Над любым вектором, состоящим из двух и более элементов, определим операцию сжатия, состоящую в замене произвольной пары соседних элементов на их сумму. Например, вектор 123 в результате сжатия может превратиться в вектор 33 либо 15.

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

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

Входной файл содержит тройку чисел N A B, за которой следует N чисел P₁, P₂, …, P_N.

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

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

Ограничения

Все числа во входном файле целые.

1 ≤ N ≤ 1000, 0 ≤ A, B, p_i ≤ 10⁶.

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

7 3 6
3 1 1 1 2 2 2

3
5 3 4

7 3 3
3 1 1 1 2 2 2

0

6 20 50
29 5 19 37 43 5

4
29 24 37 48

Задача C2. 0 - a, 1 - ab ≡

Условие

Дана строка s, состоящая из N символов 0 или 1, а также строка t, состоящая из M символов a или b,

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

• заменять символ 0 на строку из одного или более символов a
• заменять символ 1 на строку из одного или более символов a, либо на строку из одного или более символов b

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

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

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

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

Третья строка входного файла содержит строку t.

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

Ограничения

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

3 3
101
bab

Y

4 3
1001
bab

N

Задача C3. Имена файлов ≡

Условие

I wish we had some way to handle it sanely, but I don't think a sane solution to case-insensitivity exists.

Linus Torvalds

На компьютере под управлением операционной системы Linux имеется каталог, содержащий N файлов. Пользователю требуется скопировать эти файлы на компьютер, работающий под управлением ОС Windows. К сожалению, файловая система Windows имеет странное свойство. Несмотря на то, что она сохраняет большие и малые буквы в именах файлов, имена, отличающиеся только регистром букв, считаются одинаковыми. Например, файлы с именами ChangeLog, CHANGELOG и changelog при копировании на файловую систему Windows попадут в один и тот же файл.

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

1. Файлы копируются в порядке перечисления в исходном каталоге.
2. Имена файлов считаются одинаковыми, если они совпадают с точностью до регистра.
3. Если при копировании очередного файла выяснилось, что файл с таким именем уже был скопирован, то к имени текущего файла добавляется суффикс "1".
4. Если имя, полученное после присоединения суффикса, также уже встречалось, то перебираются суффиксы "2", "3", ..., "10", "11", ... до тех пор, пока не найдётся суффикс, дающий уникальное имя.

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

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

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

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

Ограничения

1 ≤ N ≤ 10000, 1 ≤ M ≤ 255

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

4
aA
Aa
aa
AA1

aA
Aa1
aa2
AA11