Игра в "морской бой" происходит на поле размером 10 на 10 клеток. Некоторые клетки могут быть заняты
кораблями. Каждый корабль занимает от 1 до 4 клеток, расположенных подряд по вертикали или горизонтали.
Перед очередным ходом игрок пытается определить, где на поле расположен корабль противника,
состоящий из K клеток. При этом игроку уже известно, что некоторые клетки не могут быть
заняты искомым кораблём, поскольку в них либо уже был произведён выстрел,
либо на них или рядом находится потопленный корабль.
Требуется определить количество возможных вариантов расположения корабля длиной K на оставшихся клетках.
Отправка решения и тестирование
Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты.
Этот файл можно скачать ЗДЕСЬ.
В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче
в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").
Баллы будут начисляться пропорционально количеству правильных ответов в выходном файле.
Решение будет полностью проверяться сразу после отправки,
и участникам будут видны набранные за данную задачу баллы.
Формат входного файла
Первая строка входного файла содержит целое число N — количество тестов в данном файле
Далее N идёт блоков с описанием тестов:
Первая строка теста содержит целое число K.
Следующие 10 строк по 10 символов содержат описание поля.
Клетки, на которых искомого корабля нет, обозначаются символом 'X' (ASCII 88),
свободные клетки обозначается символом '.' (ASCII 46).
Каждый тест заканчивается пустой строкой
Формат выходного файла
Выходной файл должен содержать N целых чисел, по одному в строке — ответы на каждый тест.
Аполлинарий Матвеевич — старый, седой библиотекарь. Сегодня он в очень хорошем
настроении, потому что библиотеке подарили компьютер.
Помощники Аполлинария Матвеевича составили базу данных книг библиотеки.
Все книги, хранящиеся в библиотеке, разбиты по областям знаний, и
в каждой книге затронут ряд тем. При этом и каждая тема, и каждая
книга могут принадлежать только одной области знаний.
В базе данных хранится список областей знаний и содержится
информация о книгах, относящихся к каждой области знаний.
Кроме того, для каждой книги составлен список тем, затронутых в ней.
Однажды в библиотеку зашёл читатель. Он дал Аполлинарию Матвеевичу список тем и
попросил его подобрать книги по этим темам. Аполлинарий Матвеевич обрадовался:
у него есть база данных! Но стоп: как найти в базе данных нужную информацию?
Для этого нужна программа.
Помогите Аполлинарию Матвеевичу. Напишите программу, позволяющую определить, к каким
областям относятся заданные темы и в каких книгах можно найти информацию по этим
темам.
Формат входного файла
Первая строка входного файла содержит целое число N — количество областей знаний.
Далее для каждой области знаний входной файл содержит название области знаний,
за которым следует количество книг, относящихся к данной области знаний.
Далее для каждой книги входной файл содержит название книги, за которым
следует количество тем, затронутых в данной книге.
Далее следует список тем.
Далее входной файл содержит целое число M — количество тем в списке, подготовленном
читателем. Далее следует список тем.
Формат выходного файла
Для каждой темы требуется вывести строку "Topic: название темы".
Далее должна следовать строка "Subject: название области знаний".
Далее должна следовать строка "Books:" (без пробелов).
Далее должен следовать список книг в том порядке, в котором они
перечислены во входном файле.
Ограничения
1 ≤ N ≤ 50
1 ≤ M ≤ 10
Количество книг, относящихся к определённой области знаний, от 1 до 100.
Количество тем, затронутых в определённой книге, от 1 до 10.
Все названия во входном файле имеют длину от 1 до 50 символов и состоят из
маленьких латинских букв.
Входные данные таковы, что каждая тема из списка, подготовленного читателем,
затронута хотя бы в одной книге.
Примеры тестов
№
Входной файл (input.txt)
Выходной файл (output.txt)
1
2
mathematics
2
algebra
3
lines
equations
coordinates
geometry
3
triangles
coordinates
lines
physics
2
mechanics
3
force
velocity
mass
gravitation
2
force
mass
5
force
triangles
velocity
coordinates
mass
Скоро Новый год, и Марфа Геннадьевна послала своих сыновей срубить
несколько ёлок на продажу.
Хорошие, толстые, густые ёлки стоят на рынке 5000 руб., а ёлки похуже,
тонкие, менее густые стоят 2000 руб.
На всё про всё у ребят есть ровно T минут. Хорошие ёлки растут подальше,
и рубить их дольше. Ёлки похуже растут поближе, и рубить их быстрее.
На то, чтобы дойти до i-й ёлки, срубить её и вернуться домой, нужно затратить
ti минут.
У ребят есть электронная карта участка леса, на которой отмечены ёлки.
Сейчас им ой как нужна программа, вычисляющая максимально возможную
выручку.
Формат входного файла
Входной файл содержит целое число T.
Далее идёт целое число N — количество хороших ёлок,
за которым следуют N целых чисел ti.
Далее следует число M — количество ёлок похуже. За ним следуют
M целых чисел ti.
Формат выходного файла
Требуется вывести в выходной файл целое число — максимально возможную
выручку.
Эллипс — геометрическое место точек, сумма расстояний для которых от двух заданных постоянна и равна 2a.
Две заданных точки называются фокусами эллипса и в нашей задаче их координаты обозначаются как
x1, y1, x2, y2. Число a называется большой полуосью эллипса.
Окружность — геометрическое место точек, расстояние для которых от заданной постоянно и равно R.
Заданная точка называется центром окружности и в нашей задаче её координаты обозначаются как x, y.
Число R называется радиусом окружности.
И для окружности, и для эллипса можно определить их внутреннюю часть —
площадь, ограниченную окружностью или эллипсом соответственно.
Напишите программу, которая по заданным окружности и эллипсу находит площадь пересечения их внутренних частей.
Формат входного файла
Во входном файле находятся целые числа x, y, R, x1, y1, x2, y2, a в этом порядке.
Формат выходного файла
Выведите единственное число - площадь пересечения с точностью до 10−2.
