Задача Task 1.
В компьютерной игре "Страшная месть 2" главного героя – бесстрашного рыцаря –
схватили злые и коварные колдуны и спрятали в темном подземелье. Но, к счастью, у славного рыцаря нашлась карта подземелья и несколько ящиков динамита. Каждый ящик динамита может разрушить одну стену. Какое наименьшее количество ящиков динамита должен израсходовать герой, чтобы выбраться из подземелья? Карта лабиринта – лист бумаги в клетку из
M
строк и
N
столбцов. Клетка может быть свободной либо занятой стеной. Герой может перемещаться по свободным клеткам по горизонтали и вертикали. Ящик динамита разрушает стену в одной клетке. Чтобы выбраться из подземелья, герою достаточно достигнуть границы карты.
Технические условия
Вы вводите с клавиатуры два числа
M
(
2<M<100)
и
N (2<N<100) –
количество строк и столбцов в лабиринте, далее в
M
строках по
N
чисел в каждой вы вводите карту лабиринта: 0 – свободная клетка, 1 – стена, 2 – начальное положение героя. Вы выводите на экран искомое количество ящиков динамита.
Пример
Ввод:
6 7
1
1
1
1
1
1
1
1 0 1
1
1
0 1
1
1
0 2 1
1
1
1 0 1 0 1 0 1
1 0
0
1
1
0 1
1
1
1
1
1
1
1
Вывод:
2
В данном примере герою необходимо разрушить две стены, чтобы выбраться из подземелья.
Задача
Task
2.
Дано натуральное число, большее 1. Определить, является ли оно степенью какого-нибудь натурального числа. Считается, что показатель степени больше 1.
Технические условия
Вы вводите с клавиатуры количество контрольных примеров
n
, затем через пробел
n
чисел, каждое из которых не превышает 1000000000. Вы выводите на экран 1, если число является степенью и 0 в противном случае.
Пример
Ввод: 3 4 5 27
Вывод: 101
Задача Task 3. В продажу поступили новые доски для шахматной игры: стандартный размер 8х8, однако с прямоугольным симметричным вырезом в центре. За какое минимальное количество ходов и каким образом ферзь может попасть из одной клетки такой доски в другую?
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Пример
Ввод: 4 2 4 7 8 3
Вывод: 2 4 7 8 7 8 3
Задача
Task
4.
В
компьютерн
o
й
игре "Страшная месть 2" главному герою – бесстрашному рыцарю – необходимо спуститься по шаткой лестнице, состоящей из
N
ступенек, в темное подземелье. Герой может спуститься, переступая на соседнюю ступеньку, перепрыгивая через одну либо две ступеньки. Но злые колдуны подпилили некоторые ступеньки, поэтому на них становиться опасно. Сколькими разными способами рыцарь может пройти с первой ступеньки на
N
-ю
?
Технические условия
Вы вводите с клавиатуры количество ступенек
N (1<N<40)
и через пробел
N
чисел: 1, если ступенька не повреждена и 0, если ступенька повреждена. Вы выводите на экран искомое количество способов. Исходные данные таковы, что герой может пройти на
N
-ю
ступеньку хотя бы одним способом.
Пример
Ввод:
6 1 0 1
1
0 1
Вывод
: 3
В данном примере лестница состоит из 6 ступенек, причем вторая и пятая ступеньки подпилены. Пройти с первой ступеньки на шестую можно тремя способами.
Первый способ: прыжок через одну ступеньку, шаг на следующую и прыжок через ступеньку.
Второй способ: прыжок через ступеньку и прыжок через 2 ступеньки. Третий способ: прыжок через 2 ступеньки и прыжок через 1 ступеньку.
Задача
Task
5.
Перестановку
π
назовем инволюцией, если π2
=
ι
, где
ι
— тождественная перестановка (т.е. 1
2
…
N
). Упорядочим все перестановки из
N
элементов в лексикографическом порядке. Напишите программу, которая по заданной перестановке найдет первую инволюцию, следующую в этом упорядочении после данной перестановки.
Технические условия
C
начала вы вводите с клавиатуры число
N
(2 ≤
N
≤ 100), а затем
N
различных целых чисел из диапазона от 1 до
N
, задающих перестановку.
Вы выводите на экран число
N
, а затем искомую инволюцию. Если искомой инволюции не существует, выведите одно число 0.
Примеры
Ввод: 5 3 1 2 4 5
Вывод:
5 3 2 1 4 5
Ввод: 3
3
2 1
Вывод: 0
Задача
Task
6.
На плоскости нарисованы круг и выпуклый многоугольник. Необходимо найти площадь их пересечения.
Технические условия
Вы вводите с клавиатуры через пробел три числа: X, Y и R – координаты центра и радиус круга. Затем через пробел вводится целое число N – количество вершин многоугольника (3≤N≤100), затем координаты вершин многоугольника в порядке их обхода против часовой стрелки. Все координаты и радиус – вещественные числа, не превышающие 10 000 по абсолютной величине. Длины всех сторон многоугольника не меньше 10-4, никакие три последовательные вершины многоугольника не лежат на одной прямой. Вы выводите на экран единственное вещественное число – площадь пересечения
заданных
круга и многоугольника. Выведенное число должно отличаться от правильного ответа не более чем на 10-4.
Примеры
Ввод:
0.0
0.0
1.0 4 -4.0 -4.0 4.0 -4.0 4.0
4.0
-4.0 4.0
Вывод:
3.14159265358979324
Ввод:
0.0
0.0
8.0 4 -4.0 -4.0 4.0 -4.0 4.0
4.0
-4.0 4.0
Вывод:
63.999999999999999
Задача
Task
7.
Рассмотрим правильные скобочные последовательности, состоящие из трех видов скобок: круглых (), квадратных [] и угловых <>. Назовем последовательность хорошей, если между любой парой соответствующих друг другу открывающейся и закрывающейся круглых скобок не встречается квадратных скобок.
Напишите программу, которая по числу
N
вычисляет число хороших последовательностей длины 2N (то есть состоящих из N пар скобок).
Технические условия
Вы вводите с клавиатуры одно целое число N (0≤
N
≤100). Вы выводите на экран количество хороших последовательностей.
Примеры
Ввод: 1
Вывод:
3
Ввод: 2
Вывод:
17
Задача
Task
8.
Даны числа
А
и В. Найти остаток при делении А на В.
Технические условия
Вы вводите с клавиатуры через пробел числа
А
(1≤А<10255) и В (1≤А<109). Вы выводите на экран искомый остаток.
Пример
Ввод: 510 4
Вывод: 2