ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрана 1 задача
Версия для печати
Убрать все задачи

Генератор случайных карт известной игры Heroes of Might and Magic III создает острова, на которых изначально будут расположены герои. При такой генерации острова получаются различными по величине. Назовем коэффициентом несправедливости отношение площади наибольшего острова к площади наименьшего. Требуется определить этот коэффициент.

Карта задается прямоугольником N × M, в каждой клетке которого записана цифра 0 (вода) или цифра 1 (земля). Островом считается максимальное связное множество клеток, содержащих единички, т.е. такое множество клеток A, что:
    из любой клетки A можно пройти до любой другой клетки A, переходя лишь через клетки A и их стороны;
    при добавлении к A любой другой клетки, содержащей 1, предыдущее условие нарушается.

Входные данные

В первой строке входного файла содержатся числа N и M – размеры карты (1 ≤ N, M ≤ 1000). Далее записана сама карта – M строк по N чисел (0 или 1) в каждой. Числа внутри строки разделяются пробелом.

Выходные данные

В выходной файл вывести коэффициент несправедливости с 5 знаками после десятичной точки. Если на карте нет ни одного острова, вывести 0.

Пример входного файла

7 6
1 1 0 0 0 0 0
0 1 0 1 0 0 0
1 1 0 1 1 0 0
1 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 0 1 0

Пример выходного файла

2.66667

   Решение

Задачи

Страница: 1 2 3 >> [Всего задач: 12]      



Задача 102946  (#1)

 [ХитрОе жюRи ]
Тема:   [ Задачи с целыми числами ]
Сложность: 3-

Дана последовательность целых чисел. Известно, что все числа в ней встречаются ровно два раза, кроме одного, которое встречается только один раз. Напишите программу, определяющую это число.

Входные данные

Входной двоичный файл содержит последовательность 32-битовых целых чисел со знаком (File Of LongInt).

Выходные данные

Выведите в выходной текстовый файл искомое число.

Пример входного файла

XXYYXYXYXXYY

Пример выходного файла

1498962264
Прислать комментарий     Решение


Задача 102947  (#2)

 [Острова ]
Тема:   [ Неопределено ]
Сложность: 4

Генератор случайных карт известной игры Heroes of Might and Magic III создает острова, на которых изначально будут расположены герои. При такой генерации острова получаются различными по величине. Назовем коэффициентом несправедливости отношение площади наибольшего острова к площади наименьшего. Требуется определить этот коэффициент.

Карта задается прямоугольником N × M, в каждой клетке которого записана цифра 0 (вода) или цифра 1 (земля). Островом считается максимальное связное множество клеток, содержащих единички, т.е. такое множество клеток A, что:
    из любой клетки A можно пройти до любой другой клетки A, переходя лишь через клетки A и их стороны;
    при добавлении к A любой другой клетки, содержащей 1, предыдущее условие нарушается.

Входные данные

В первой строке входного файла содержатся числа N и M – размеры карты (1 ≤ N, M ≤ 1000). Далее записана сама карта – M строк по N чисел (0 или 1) в каждой. Числа внутри строки разделяются пробелом.

Выходные данные

В выходной файл вывести коэффициент несправедливости с 5 знаками после десятичной точки. Если на карте нет ни одного острова, вывести 0.

Пример входного файла

7 6
1 1 0 0 0 0 0
0 1 0 1 0 0 0
1 1 0 1 1 0 0
1 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 0 1 0

Пример выходного файла

2.66667
Прислать комментарий     Решение


Задача 102948  (#3)

 [Микрофония ]
Тема:   [ Конечные автоматы ]
Сложность: 4+

В драматическом театре им. Пушкина к юбилею Александра Сергеевича решили поставить оперу «Евгений Онегин». Артисты театра обладают красивыми, но не очень сильными голосами. По этой причине руководство театра дало указание приобрести радиомикрофоны. В начале и в конце спектакля все артисты находятся за кулисами. Артисты выходят на сцену и покидают ее через правую или левую кулису. Для того, чтобы петь на сцене, артист берет с собой один микрофон. Артист может выходить на сцену с микрофоном (одним), даже если ему не надо петь в этом выходе. Взяв микрофон, артист не может оставить его на сцене или передать другому артисту. При уходе артиста за кулисы микрофон остается за соответствующей кулисой до тех пор, пока его снова не возьмет какой-либо артист, выходящий на сцену.

Очередность выходов артистов на сцену и их уходов за кулисы указывается в режиссерском плане. Кроме того, в этом плане указывается, через какие кулисы выходит (или уходит) артист и поет ли он в данном выходе. 

Напишите программу, которая по заданному режиссерскому плану определяет минимальное количество требуемых для постановки оперы микрофонов, их начальное размещение по кулисам и для каждого выхода указывает, брать или не брать микрофон.

Входные данные

Первая строка входного файла содержит целое число N – количество артистов, участвующих в спектакле (1 ≤ N ≤ 1000). Во второй строке записано целое число K – количество выходов артистов на сцену (1 ≤ K ≤ 3000). Далее идут 2K строк, описывающих режиссерский план спектакля. Каждая из них содержит четверку AiBiCiDi (1 ≤ i ≤ 2K):
Ai – символ +, если в данный момент артист выходит на сцену, или символ -, если артист со сцены уходит;
Bi – номер артиста (целое число от 1 до N);
Ci – символ Л, если артист выходит (уходит) через левые кулисы, или символ П, если он выходит (уходит) через правые кулисы;
Di – символ Д, если артист поет в данном выходе (пел перед данным уходом), или символ Н, если он не поет (не пел).

Выходные данные

Первая строка выходного файла должна содержать два целых числа. Первое число – количество микрофонов перед началом оперы с левой стороны, второе число – количество микрофонов с правой стороны. В каждой из последующих K строк необходимо вывести 1 или 0 в зависимости от того, берет ли с собой микрофон очередной выходящий на сцену артист (1 - берет, 0 - не берет).

Пример входного файла

3
4
+ 1 Л Д
- 1 Л Д
+ 2 Л Н
+ 3 Л Н
- 3 П Н
+ 1 П Д
- 1 Л Д
- 2 П Н

Пример выходного файла

1 0
1
0
1
1
Прислать комментарий     Решение


Задача 102949  (#4)

 [Миротворцы ]
Тема:   [ Вычислительная геометрия (прочее) ]
Сложность: 3

N миротворцев из российского корпуса KFOR десантировались в окрестности аэропорта Слатина. Точка приземления каждого миротворца задается парой целочисленных координат (x, y). За один шаг каждый из десантников может переместиться на соседнюю целочисленную позицию вдоль оси X или Y (т.е. одна из его координат меняется на 1 по абсолютной величине). Шаги делаются по очереди, никакие два миротворца при этом не могут находиться в одной позиции одновременно. 

Десантники хотят выстроиться в шеренгу – линию, параллельную одной из осей координат, в которой они стояли бы в подряд идущих целочисленных позициях. Напишите программу, которая определяет минимальное суммарное число шагов, необходимое миротворцам для того, чтобы образовать шеренгу.

Входные данные

Первая строка входного файла содержит целое число N – количество миротворцев (1 ≤ N ≤ 10000). Каждая из последующих N строк содержит
координаты десантника – два целых числа из диапазона [-32768, 32767], разделенные пробелом.

Выходные данные

Выведите в выходной файл искомое количество шагов.

Пример входного файла

3
-1 -1
0 0
1 1

Пример выходного файла

2
Прислать комментарий     Решение


Задача 102950  (#5)

 [Булевы функции ]
Тема:   [ Задачи на полный перебор ]
Сложность: 3+

Булевой функцией называется функция, принимающая одно из логических значений TRUE или FALSE и зависящая от некоторого (быть может, нулевого) количества аргументов, каждый из которых также может принимать любое из значений TRUE или FALSE.

Любая булева функция однозначно задается своей таблицей истинности, в которой для каждого возможного набора значений аргументов указано значение функции. Например, x AND y – булева функция от двух аргументов. Ее таблица истинности выглядит так: 

Если договориться, что наборы значений аргументов в таблице располагаются в лексикографическом порядке, то функция AND однозначно задается третьим столбцом таблицы – строкой 0001. Аналогично, каждой булевой функции от k аргументов можно поставить в соответствие строку из нулей и единиц длины 2k.

Задан набор из N+1 булевой функции (f, f1, f2, ..., fN). Напишите программу, которая определяет, можно ли функцию f выразить через функции f1, f2, ..., fN, и если такие представления возможны, то находит кратчайшее по числу символов среди них.

Входные данные

В первой строке входного файла записано целое число N (1 ≤ N ≤ 9). Последующие N+1 строк содержат описания функций f, f1, f2, ..., fN соответственно. Каждая из функций описывается строкой символов так, как указано выше. Число аргументов у функции f будет не более двух, а у остальных функций – не более трех.

Выходные данные

Первая строка выходного файла должна содержать искомое символьное представление, либо строку «Impossible», если такого представления не
существует. После функции с нулевым числом аргументов скобки не ставятся. Если у функции f один аргумент, то он обозначается x, а если два, то они обозначаются x и y.

Пример входного файла

2
1
1010
0

Пример выходного файла

f1(f2,f2)
Прислать комментарий     Решение


Страница: 1 2 3 >> [Всего задач: 12]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .