Задача A. Робинзон и крокодилы

Автор:Жюри XXVI Всероссийской олимпиады школьников по информатике
Входной файл: alligator.in   Ограничение времени:2 сек
Выходной файл: alligator.out   Ограничение памяти:256 Мб

Условие

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

Автор:Т. Кормен, Ч. Лейзерсон, Р. Ривест, Т. Чистяков
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:200 Мб

Условие

Абзац текста состоит из 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

Author:B. Vasilyev, A. Klenin
Input file: input.txt   Time limit:5 sec
Output file: output.txt   Memory limit:4 Mb

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)2R2.

Your task is to select a subset of sites for relay stations so that:

  1. the covered areas for relays do not intersect (but may touch) one another,
  2. 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 ≤ riR ≤ 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1 0 0 10
10 0 10
505.4816

0.033s 0.004s 13