Задача 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

Problem A1. Amazon ≡

Statement

Fantasy chess is a variant of chess composition. Puzzles of this variant contain changes to some of the accepted rules of the game or utilize unusual pieces or boards.

Amazon is a fantasy chess piece which can move as either a queen or a knight. It is usually represented on diagrams as a horse with the crown. You can see all possible moves of this piece on a picture below. Amazon is so strong and independent that it can checkmate the enemy king without the help of another friendly piece.

White amazon and black king are positioned on a normal chess board. Determine whether the king is checkmated.

Input format

First line of input contains two integers separated by space: x₁ and y₁ — coordinates of the white amazon. Second line contains coordinates of the black king x₂ and y₂ in the same format. Piece positions are guaranteed to be different.

Output format

Output Yes or No — answer to the problem's question.

Constraints

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

Notes on the samples

See the picture. In the second sample the king can capture the amazon.

Sample tests

7 6
7 8

Yes

6 7
7 8

No

Problem A3. Circulation of try-square ≡

Statement

During a woodwork lesson at school, Timofey got his hands onto the try-square with wooden handle and metallic blade. Since Timofey has already finished his assignment (producing a stool), he started to roll the try-square along the coordinate axis. Starting position and movement direction are shown on the picture.

Your program must, given the coordinate of the point on the axis, determine which part of the try-square touched it.

Input format

Input contains three integers a, b and n — lengths of the wooden and metallic internal sides of the try-square and the coordinate of point. It is guaranteed that a and b are catheti of Pythagorean triangle (that is, hypotenuse is a whole integer).

Output format

Output must contain a single word:

• wood, if point is touched by the wooden handle,
• metal, if point is touched by the metal blade,
• empty, if point is not touched by the try-square.

Constraints

3 ≤ a < b ≤ 1000

1 ≤ n ≤ 10⁹

Sample tests

3 4 11

wood

Problem A4. Attacking rooks ≡

Statement

A pawn is located on a chess board at coordinates x, y (x is a column number, y is a row number).

You must write a program to determine maximum number of rooks which can be placed on this board so that not a one of them will attack another.

Input format

Input contains integers x and y.

Output format

Output must contain a single integer — maximum number of rooks.

Constraints

1 ≤ x, y ≤ 8

Sample tests

1 1

8

Problem A5. Just do it! ≡

Statement

All you need to do is to output all possible variations of the phrase Just do it!, differing only by the case of some letters (for example jUst DO it!).

Output format

Output must contain all possible variations of the phrase, one per line. Order of lines is not important.

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

Problem A8. Right triangle ≡

Statement

Sasha graduated from high school and decided to enroll as a programmer at a local university. One of the first subjects in his course was «Geometry and Topology of Numbers». At the very first lecture, the whole group was asked to derive and prove a theorem that would make it possible to determine by three points on the plane whether the triangle formed by them is a right-angled.

Sasha was able to come up with several theorems, but for some reason his theorems give different answers. Write a program that, given the coordinates of three points, can correctly determine whether these points form a right-angled triangle.

Input format

First line of input contains integers x₁ and y₁, second line contains integers x₂ and y₂, third line contains integers x₃ and y₃ — coordinates of three points. All points are pairwise different.

Output format

Output must contain YES, if given points form right triangle or NO otherwise.

Constraints

 − 10⁴ ≤ x_i, y_i ≤ 10⁴

Sample tests

0 0
0 8
6 0

YES

1 2
3 2
4 1

NO

Problem A9. Fine segments ≡

Statement

The young programmer Ilya was presented with a sequence of numbers a_i of length n for his birthday. Ilya decided to select fine segments from this sequence. A fine segment is a sequence of successive elements of a_i containing some element equal to the sum of its first and last elements. For example, the sequence [1, 2, 5, 4] is fine because the sum of the leftmost and rightmost elements is 5, and the number 5 is in this sequence; the sequence [1, 2, 3, 4] is not fine because the sum of the leftmost and rightmost elements is 5, and the number 5 is not in this sequence. Your program must count the number of fine segments in a given sequence.

Input format

The first line contains an integer n — the length of the sequence. The second line contains n integers a_i — the elements of the sequence. All elements of the sequence are different.

Output format

Output a single integer — number of fine segments in the sequence.

Constraints

1 ≤ n ≤ 10³

1 ≤ a_i ≤ 10⁵

Notes on samples

First sample has one fine segment: [3, 7, 5, 4].

Second sample has two fine segments: [1, 5, 4] и [1, 5, 4, 7, 6].

Sample tests

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