Theory and Tasks for Students - Spring 2019
Сложные задачи

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

E1 Тройки-пятёрки

Определить можно ли с использованием только операций "прибавить 3" и "прибавить 5" получить из числа 1 число N. Разумеется, само число 1 получить можно, просто не применяя никаких операций.

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

Вводится одно натуральное число N ≤ 106.

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

Выведите слово YES, если число N можно получить из числа 1, или NO - в противном случае.

E2 Биномиальные коэффициенты

Для биномиальных коэффициентов (числа сочетаний из n по k) хорошо известна рекуррентная формула: Cnk=Cn-1k-1+Cn-1k, Cn0=Cnn=1. Требуется найти Cnk.

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

Вводится два целых числа - 0 ≤ n, k ≤ 50, k ≤ n.

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

Единственное число - значение Cnk.

E3 Шакал

Дана строка из k маленьких букв английского алфавита. Требуется провести сжатие этой строки путём замены повторяющихся подряд символов следующим образом: "aaaabbbcdaaddd" должна быть преобразована в "4a3bcd2a3d"

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

Вводится строка из k символов, k ≤ 106.

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

Максимально сжатая указанным образом строка.

E4 Платная лестница

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

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

В первой строке вводится одно натуральное число N ≤ 104 - количество ступенек. В следующей строке вводятся N натуральных чисел Сi ≤ 104 (1 ≤ i ≤ N) - стоимость каждой ступеньки (снизу вверх).

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

Выведите одно число - наименьшую возможную стоимость прохода по лесенке.

E5 Седловые точки

Задана матрица содержащая N строк и K столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце. Найдите количество седловых точек заданной матрицы.

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

Первая строка содержит целые числа 1 ≤ N, K ≤ 750. Далее следуют N строк по K чисел в каждой - элементы матрицы Aij ≤ 100 (1 ≤ i ≤ N, 1 ≤ j ≤ K).

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

Единственное число - количество седловых точек.

E6 Ферзи

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

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

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

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

Если ферзи не бьют друг друга, выведите слово NO, иначе выведите YES.