Задача A. Ферзи

Ферзь – самая сильная шахматная фигура, которая за один ход может перемещаться на любое число полей по вертикали, горизонтали или диагонали (при условии, что на его пути нет фигур). Клетка бьется ферзем, если он может попасть на нее одним ходом. На доске N×N расставлено К ферзей. Посчитайте количество пустых клеток доски, которые не бьются ни одним ферзем. Первая строка входного файла содержит два целых числа N и K (1 ≤ N ≤ 10000, 1 ≤ К ≤ 100000). Каждая из следующих К строк содержит по два числа – номера строк и столбцов, на которых стоит соответствующий ферзь (строки и столбцы нумеруются целыми числами от 1 до N). Позиции всех ферзей различны. Числа в строках разделены пробелами. Выведите одно целое число – ответ к задаче. Вход:

3 2 
3 2 
2 3

 Ответ:

1

Задача B. Путешествие

Ваш друг решил отправиться в путешествие по городам страны, которых всего N. Проезд по каждой дороге занимает ровно один день. Каждый день он будет переезжать из города в город (он может возвращаться в город, в котором уже был). Определите, в каких городах он может оказаться через К дней после начала путешествия, если в первый день он выезжает из города 1. Первая строка входного файла содержит три целых числа N, M и K (2 ≤ N ≤ 20, 1 ≤ M ≤ N (N – 1) / 2, 1 ≤ K ≤$10^9$). Следующие М строк содержат описание дорог в виде двух целых чисел – номеров городов, между которыми проходит соответствующая дорога. Города нумеруются целыми числами от 1 до N. Числа в строках разделены пробелами. В выходной файл выведите через пробел номера городов, в которых может оказаться ваш друг через К дней. Все числа должны быть различными. Вход:

7 6 3
1 2
3 2
3 4 
1 5 
5 6
7 6

 Ответ:

2 5 4 7

Вход:

3 2 1 
2 1
2 3

 Ответ:

2

Задача C. Корень

Вычислите корень N-й степени из заданного числа А (то есть такое число Х, что $X^n$ = А). Если ответ – нецелое число, округлите его по обычным правилам округления. Единственная строка входного файла содержит два целых числа А и N, разделенных пробелом ( 1 ≤ А ≤ $10^{200}$, 1 ≤ N ≤ 100). Выведите одно целое число – ответ к задаче. Вход:

4 2

 Ответ:

2

Вход:

31 2

 Ответ:

6

Вход:

30 2

 Ответ:

5

Задача E. Фигуры

Назовем фигурой множество клеток, связанных по стороне. Будем считать фигуры одинаковыми, если их можно совместить поворотами и перемещениями. На листе бумаги в клетку нарисовано множество фигур, посчитайте, сколько из них различных. Первая строка содержит два целых числа N и М (1≤ N, М ≤ 100) – размер листа в клетках. Следующие N строк содержат по М символов каждая. Возможные символы: ’.’, если данная клетка пустая, или ’#’, если она является частью какой-то фигуры. Выходной файл должен содержать одно целое число – количество различных фигур. Вход:

10 10
.......... 
.#...#.... 
.###.#.... 
....##.... 
.......... 
..###..... 
....#..... 
.......#.. 
.......#.. 
.......##.

 Ответ:

2

Задача F. Агентство

Вам поручили работу с базой данных агенства по недвижимости. В базу постоянно вносятся сведения о новых квартирах: их стоимость и удобство, оцененные в целых числах от 1 до 109, и удаляются сведения о проданных квартирах. В произвольный момент времени требуется узнавать номер квартиры с наибольшим удобством среди квартир между і-й и ј-й по увеличению стоимости включительно. Первая строка входного файла содержит число N – количество операций с базой данных (1≤ N ≤ 300000). Следующие N строк содержат описание операций в следующем формате: “+ А В ” – добавить в базу квартиру стоимостью А и удобством В ( 1≤ А, В ≤ 109, все А различны, все В различны); “- Х”- удалить квартиру номер Х (Х ≥ 1, гарантируется, что квартира с номером Х есть в базе); “# і ј”- вывести номер квартиры с наибольшим удобством среди квартир между і-й и ј-й по увеличению стоимости включительно (1≤ і ≤ ј, гарантируется, что количество квартир в базе не меньше ј. Квартиры нумеруются целыми числами с 1 в порядке добавления в базу. Числа и знаки в строках разделены пробелами. В выходной файл на каждый запрос вида “# і ј” выведите одно целое число – номер соответствующей квартиры. Вход:

7
+ 10 1
+11 4
# 1 2
- 2
+ 13 2
# 1 2

 Ответ:

2
3