Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
alligator.in
Ограничение памяти:
256 Мб
Выходной файл:
alligator.out
Максимальный балл:
100
Условие
Робинзон живет на острове, который представляет собой прямоугольник размером n × m клеток.
На остров Робинзона выползли погреться на солнышке и задремали несколько крокодилов.
Робинзон хочет прогнать неприятных соседей, не поднимая шума.
Для этого он кидает в дремлющих крокодилов орехи.
В каждой клетке острова находится не более одного крокодила.
Напуганный орехом крокодил быстро бежит строго по прямой, пока не окажется в воде.
Для каждого крокодила известно направление, в котором он побежит, если его напугать.
Направления, в которых будут убегать крокодилы, параллельны сторонам острова.
Если на пути напуганного крокодила окажется другой крокодил, то, столкнувшись,
они разозлятся, и нападут на Робинзона.
Поэтому надо тщательно выбирать очередного крокодила, чтобы на его пути были только пустые клетки.
Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.
Требуется написать программу, определяющую максимальное количество крокодилов,
которых можно прогнать, не разозлив их.
Пояснения к примеру
Рисунок показывает исходное расположение крокодилов в третьем примере.
Система оценивания
Данная задача содержит три подзадачи. Баллы за подзадачу начисляются только в том случае,
если все тесты этой подзадачи успешно пройдены.
Подзадача 1 (30 баллов)
1 ≤ n, m ≤ 30
Подзадача 2 (30 баллов)
1 ≤ n, m ≤ 500
Подзадача 3 (40 баллов)
1 ≤ n, m ≤ 2000
Получение информации о результатах окончательной проверки
По запросу сообщается результат окончательной проверки на каждом тесте.
Формат входного файла
В первой строке входного файла записаны числа n и m — размеры острова
с севера на юг и с запада на восток. Последующие n строк по m символов в каждой
описывают текущее расположение крокодилов на острове. Если клетка свободна,
то она обозначается точкой ".", а если там находится крокодил,
то в ней указано направление, в котором побежит этот крокодил.
Направления обозначаются буквами: "N" — север, "S" — юг, "E" — восток, "W" — запад.
Формат выходного файла
Выходной файл должен содержать одно число — максимальное количество крокодилов,
которых можно прогнать, не разозлив.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
1 сек
Входной файл:
sweets.in
Ограничение памяти:
256 Мб
Выходной файл:
sweets.out
Максимальный балл:
100
Условие
Кондитерская фабрика города П, в котором живет Петя, делает очень вкусные конфеты.
Как-то раз, Петя собрался в гости к своему другу Васе, который живет в городе М.
От города П до города М Петя решил доехать на поезде и взять с собой в подарок
как можно больше коробок вкусных конфет.
Каждая коробка конфет имеет размеры a × b × c сантиметров,
где a — длина, b — ширина и c — высота коробки.
Для перевозки конфет Петя хочет использовать один большой ящик в форме прямоугольного параллелепипеда.
В ящик должны быть уложены все коробки конфет.
Для того чтобы не повредить их, все коробки в ящике должны сохранять исходную ориентацию и
располагаться в одном направлении.
Петя может использовать ящик любого размера,
но по правилам железнодорожных перевозок размер ящика по сумме трех измерений не может превышать N сантиметров.
Требуется написать программу, которая по заданным числам N, a, b и c определяет размер ящика,
который должен использовать Петя, чтобы в него поместилось максимальное количество коробок конфет.
Пояснения к примерам
В первом примере выгоднее всего взять ящик размером 3 × 4 × 3 сантиметров,
в который поместится три коробки конфет в длину, две коробки конфет в ширину и одна коробка конфет в высоту.
Во втором примере для того, чтобы разместить хотя бы две коробки конфет,
нужен ящик размером хотя бы 8 × 3 × 4, у которого сумма измерений равна 15.
В подходящий ящик поместится максимум одна коробка конфет.
Подходящим также является ящик размером 9 × 3 × 2, хотя он и не является минимальным.
Система оценивания
Подзадача 1 (20 баллов)
1 ≤ N ≤ 300
В этой подзадаче 10 тестов, каждый тест оценивается в 2 балла.
Баллы за каждый тест начисляются независимо.
Подзадача 2 (20 баллов)
1 ≤ N ≤ 5000
В этой подзадаче 10 тестов, каждый тест оценивается в 2 балла.
Баллы за каждый тест начисляются независимо.
Подзадача 3 (30 баллов)
1 ≤ N ≤ 100000
В этой подзадаче 15 тестов, каждый тест оценивается в 2 балла.
Баллы за каждый тест начисляются независимо.
Подзадача 4 (30 баллов)
1 ≤ N ≤ 109
В этой подзадаче 15 тестов, каждый тест оценивается в 2 балла.
Баллы за каждый тест начисляются независимо.
Получение информации о результатах окончательной проверки
По запросу сообщаются баллы за каждую подзадачу.
Формат входного файла
Первая строка входного файла содержит разделенные пробелами четыре целых числа: N, a, b, с.
Формат выходного файла
Выходной файл должен содержать три целых неотрицательных числа — длину, ширину и высоту ящика,
который должен выбрать Петя и в который поместится максимальное количество коробок конфет.
Если подходящих ответов несколько, необходимо вывести любой.
