Задача A. Робинзон и крокодилы
Условие
Робинзон живет на острове, который представляет собой прямоугольник размером n × m клеток.
На остров Робинзона выползли погреться на солнышке и задремали несколько крокодилов.
Робинзон хочет прогнать неприятных соседей, не поднимая шума.
Для этого он кидает в дремлющих крокодилов орехи.
В каждой клетке острова находится не более одного крокодила.
Напуганный орехом крокодил быстро бежит строго по прямой, пока не окажется в воде.
Для каждого крокодила известно направление, в котором он побежит, если его напугать.
Направления, в которых будут убегать крокодилы, параллельны сторонам острова.
Если на пути напуганного крокодила окажется другой крокодил, то, столкнувшись,
они разозлятся, и нападут на Робинзона. Поэтому надо тщательно
выбирать очередного крокодила, чтобы на его пути были только пустые клетки.
Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.
Требуется написать программу, определяющую максимальное количество крокодилов,
которых можно прогнать, не разозлив их.
Формат входного файла
В первой строке входного файла записаны числа n и m — размеры острова с севера на юг и с запада на восток.
Последующие n строк по m символов в каждой описывают текущее расположение крокодилов на острове.
Если клетка свободна, то она обозначается точкой, а если
там находится крокодил, то в ней указано направление, в котором побежит этот крокодил.
Направления обозначаются буквами:
N — север,
S — юг,
E — восток,
W — запад.
Формат выходного файла
Выходной файл должен содержать одно число — максимальное количество крокодилов,
которых можно прогнать, не разозлив.
Ограничения
1 ≤ n,m ≤ 2000.
Примеры тестов
| № |
Входной файл (alligator.in) |
Выходной файл (alligator.out) |
|---|
| 1 |
1 5
WN.SE
|
4
|
| 2 |
1 3
E.W
|
0
|
| 3 |
3 4
.N.W
WWSS
EWEW
|
4
|
Задача B. Разбиение абзаца на строки
Условие
Абзац текста состоит из
n слов длиной
l1,
l2, ...,
ln (длина слова - число символов
в нем). Требуется оптимальным образом разбить его на строки длиной не более
M символов. Оптимальность при этом определяется так: посчитаем число
"лишних" пробелов в каждой строке и сложим кубы этих чисел для всех строк,
кроме последней. Чем больше эта сумма (назовем ее
оценочной суммой),
тем хуже абзац.
Формат входного файла
В первой строке находятся числа
n и
M. Далее следует
n чисел
li.
Формат выходного файла
Выходной файл должен содержать единственное число - значение оценочной суммы
абзаца при оптимальном разбиении на строки.
Ограничения
1 <=
n <= 10000,
1 <=
M <= 100000,
1 <=
li <=
M
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
4 6
2 1 2 5
|
72
|
Problem C. Radio Coverage
Statement
Radio station 'ACM Rock' is broadcasting over the circular area with center in point
(x0, y0) and radius R.
In order to increase the auditorium, it were suggested to build several relay stations.
N locations were selected as candidate sites for relay stations.
Relay station placed in i-th location will cover a circular area with center
in point (xi, yi) and radius ri,
where center lies inside the area covered by the base station,
(x0 - xi)2 +
(y0 - yi)2 ≤ R2.
Your task is to select a subset of sites for relay stations so that:
- the covered areas for relays do not intersect (but may touch) one another,
- the total area covered by base station and all relays is maximum possible.
Input file format
Input file contains integer number
N followed by real numbers
x0 y0 R, followed by
N
triples of real numbers
xi yi ri.
Output file format
Output file should contain a single real number — the maximal coverage area with the
absolute error less than 10
−2.
Constraints
1 ≤
N ≤ 10,
0 ≤
xi,
yi,
x0,
y0 ≤ 1000,
1 ≤
ri ≤
R ≤ 1000.
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
1 0 0 10
10 0 10
|
505.4816
|
