Областная олимпиада по информатике, 2009-2010 учебный год


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

Ограничение по времени:
2 sec.
Ограничение по памяти:
64MB

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


комментарий/решение(1)

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

Ограничение по времени:
2 sec.
Ограничение по памяти:
64MB

Ваш друг решил отправиться в путешествие по городам страны, которых всего 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. Корень

Ограничение по времени:
2 sec.
Ограничение по памяти:
64MB

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

комментарий/решение

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

Ограничение по времени:
2 sec.
Ограничение по памяти:
64 MB

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

комментарий/решение

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

Ограничение по времени:
2 sec.
Ограничение по памяти:
64MB

Вам поручили работу с базой данных агенства по недвижимости. В базу постоянно вносятся сведения о новых квартирах: их стоимость и удобство, оцененные в целых числах от 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

комментарий/решение