Задача 1. «Кегельбан»

N кеглей выставили в один ряд, занумеровав их слева направо числами от 1 до N. Затем по этому ряду бросили K шаров, при этом i-й шар сбил все кегли с номерами от li до ri включительно. Определите, какие кегли остались стоять на месте.

Программа получает на вход количество кеглей N и количество бросков K. Далее идет K пар чисел li, ri, при этом 1≤ li≤ ri≤ N.

Программа должна вывести последовательность из N символов, где j-й символ есть “I”, если j-я кегля осталась стоять, или “.”, если j-я кегля была сбита.

Пока можно не заботиться об эффективности программы.

Задача 2. «Ферзи»

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

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

Задача 3. «Флаги»

Сделайте упражнение I (флаги) отсюда Флаги следующим способом:

Задача 4. «Рациональные числа: Сумма ряда»

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

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

Сравните результат и время работы с обычным суммированием во float — как минимум, для N, равному 5, 100, 1000, 10000, 100000.

Задача 5. «Рациональные числа: Хитрая последовательность»

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

Пользуясь этими функциями, вычислите первые N членов последовательности точно и выведите их с небольшой погрешностью, деля числитель на знаменатель.
Последовательность задана рекуррентно:

  • a1 = 4
  • a2 = 4.25
  • an = 108 − (815 − 1500 / an−2) / an−1

    Сравните результат и время работы с обычными вычислениями во float — как минимум, для N, равному 5, 10, 15, 25, 30.

    Задача 6. «Несократимая дробь»

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

    Всё, кроме ввода-вывода, оформите в виде функций.

    Пример

    Ввод Вывод 
    -5 6
    7 21
    		 
    -1 2

    Задача 7. «Подсчёт препятствий»

    Известно, что Робот, “живущий” на клетчатом поле, находится у левой стены, и где-то справа от него тоже есть стена. Над этим горизонтальным коридором могут быть расположены несколько стен с проходами вверх между ними. Стена от одного прохода до другого называется препятствием сверху (если стен сверху нет, то нет ни одного препятствия, а есть один проход). Препятствия могут прилегать, а могут и не прилегать к левой и правой стенам.

    Напишите программу, которая проведёт Робота до правой стены, подсчитает по пути число препятствий сверху и число проходов вверх и выведет два посчитанных числа.

    При решении задачи можно пользоваться всеми средствами Python (в том числе переменными) и следующими функциями Робота:
    Возвращают True, если можно сделать шаг в данном направлении (то есть, нет стены) Делают шаг на соседнюю клетку в данном направлении
    is_right_empty()
    is_left_empty()
    is_up_empty()
    is_down_empty()    		 step_right()
    step_left()
    step_up()
    step_down()

    Задача 8. «Заполнение диагоналями»

    Даны натуральные N и M. Заполните двумерный массив размером N×M числами от 1 до N×M диагоналями, как показано на примере. Выведите полученный массив, отводя на вывод каждого элемента наименьшее возможное, одинаковое для всех элементов число символов.

    Пример

    Ввод Вывод 
    3 5
    		 
      1  2  4  7 10
      3  5  8 11 13
      6  9 12 14 15

    Задача 9. «Ходы коня и ходы ферзя»

    На шахматной доске стоит конь или ферзь. Отметьте положение фигуры на доске и все клетки, которые бьёт фигура. Клетку, где стоит конь или ферзь, отметьте буквой “K” или “Q” соответственно, клетки, которые бьёт фигура, отметьте символами “*”, остальные клетки заполните точками.

    Программа получает на вход координаты фигуры на шахматной доске в шахматной нотации, то есть в виде “Ke4” или “Qb6”, где сначала идёт латинская буква, задающая фигуру, затем — номер столбца (буква от “a” до “h”, слева направо), затем — номер строки (цифра от 1 до 8, снизу вверх).

    Выведите количество клеток, которое бьёт фигура, и изображение доски. Изображение для красоты можно “разбавить” пробелами.

    Преобразование входного положения в координаты, если оно есть, должно быть в виде функции, запись звёздочки в клетку — тоже, причём в этой же функции должна быть проверка, принадлежит ли клетка шахматной доске (желательно, чтобы эта функция показывала своим возвращаемым значением — True или False, — была ли проставлена звёздочка).
    Генерация клеток-кандидатов для каждой возможной фигуры и подсчёт окончательного их количества тоже должны выполняться в функции (по одной на фигуру).

    Примеры

    Ввод Вывод 
    Ke4
    		 
    8
. . . . . . . . 
. . . . . . . . 
. . . * . * . . 
. . * . . . * . 
. . . . K . . . 
. . * . . . * . 
. . . * . * . . 
. . . . . . . . 
    Qb6
    		 
    23
. * . * . . . . 
* * * . . . . . 
* Q * * * * * * 
* * * . . . . . 
. * . * . . . . 
. * . . * . . . 
. * . . . * . . 
. * . . . . * .

    Задача 10. «Распаковка строчки»

    Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из латинских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки.

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

    Вводится одна строка. В строке могут встречаться только конструкции вида nA, где n — количество повторений символа (целое число от 2 до 99), а A — заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.

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

    Примеры

    Ввод Вывод 
    3A4B7D
    		 
    AAABBBBDDDDDDD
    		 
    22D7AC18FGD
    		 
    DDDDDDDDDDDDDDDDDDDDDDAAAAAAACFFFFFFFFFF
FFFFFFFFGD
    		 
    95AB
    		 
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAB
    		 
    40AB39A
    		 
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

    Задача 11. «Шарики»

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

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

    Сначала вводится количество шариков в цепочке и цвета шариков (от 0 до 9, каждому цвету соответствует своё целое число).

    Требуется вывести количество шариков, которое будет “уничтожено”.

    Примеры

    Ввод Вывод 
    5 1 3 3 3 2
    		 
    3
    		 
    9 6 0 0 5 5 5 0 0 7
    		 
    7
    		 
    10 1 1 9 9 9 1 8 8 8 1
    		 
    9
    Если в последнем примере для варианта б) мы бы сначала “уничтожили” цепочку 8 8 8, то ответ был бы 10.

    Задача 12. «Симметричная последовательность»

    Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными: 

    1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1

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

    В первой строке вводится число N — количество элементов исходной последовательности. Во второй строке через пробел идут N чисел — элементы этой последовательности, натуральные числа от 1 до 9.

    Выведите сначала число M — минимальное количество элементов, которое надо дописать к последовательности, а потом M чисел, которые надо дописать к последовательности.

    Примеры

    Ввод Вывод 
    9
1 2 3 4 5 4 3 2 1
    		 
    0
    		 
    5
1 2 1 2 2
    		 
    3
1 2 1
    		 
    5
1 2 3 4 5
    		 
    4
4 3 2 1

    Задача 13. «Заполнение по спирали»

    Дано целое N > 0. Заполните двумерный массив размером N×N числами от 1 до N×N по спирали, как показано в примерах. Выведите полученный массив, отводя на вывод каждого элемента ровно 4 символа.

    Примеры

    Ввод Вывод 
    3
    		 
       1   2   3
       8   9   4
       7   6   5
    		 
    4
    		 
       1   2   3   4
      12  13  14   5
      11  16  15   6
      10   9   8   7