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

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 6 7 8 9 10 11 12 >> [Всего задач: 56]      



Задача 98848

 [Счет игры ]
Тема:   [ Площадь ]
Сложность: 3+

Задана квадратная доска размером N×N. Известно, что на ней играли в интеллектуальную игру, вследствие чего клеточки оказались окрашенными в белый, чёрный и зеленый цвета. Раскраска клеточек может быть разной (ведь это интеллектуальная игра!), но все клеточки самого верхнего ряда белые, а самого нижнего - чёрные.

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

Определение чёрной области выглядит аналогично: она ограничена снизу нижней стороной квадрата, с других сторон - чёрной границей, которая проходит только через чёрные клеточки, а концы этой границы - левая нижняя и правая нижняя клеточки квадрата.

Задание

Напишите программу SCORE, которая по раскраске квадрата находит количество клеточек в белой и чёрной областях.

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

Первая строка входного файла SCORE.DAT содержит единственное целое число - размер квадрата (5≤N?250). Каждая из следующих N строк содержит по N символов "G", "W" или "B" (записанных без пробелов), которые обозначают зелёный, белый и чёрный цвет, соответственно.

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

Первая строка выходного файла SCORE.SOL должна содержать количество клеточек в белой области, а вторая строка - количество клеточек в чёрной области.

Пример входных и выходных данных

SCORE.DAT

SCORE.SOL

7

WWWWWWW

WGWWBWG

WWWWGWW

BBGWWWB

GWBBWGB

BBBBGBB

BBBBBBB

22

15

Вид белой и чёрной областей для примера из условия представлен на рисунке.

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

Задача 98853

 [Альтернативные пути ]
Тема:   [ Динамическое программирование (прочее) ]
Сложность: 3+

Задано прямоугольную таблицу размером M строк на N столбиков. В каждой клеточке записано натуральное число, не превышающее 200. Путник должен пройти по этой таблице из левого верхнего угла в правый нижний, на каждом шаге перемещаясь либо на 1 клеточку направо, либо на 1 клеточку вниз. Очевидно, таких путей много. Для каждого пути можно вычислить сумму чисел в пройденных клеточках. Среди этих сумм, очевидно, есть максимальная.

Будем снисходительными к Путнику, считая <хорошими> не только пути, на которых в точности достигается максимально возможная сумма, а еще и пути, сумма которых отличается от максимальной не более чем на K.

Количество <хороших> путей гарантированно не превышает 109.

Задание

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

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

Первая строка входного файла GOODWAYS.DAT содержит три целых числа M (2≤M≤200), N (2≤N≤200) и K (0≤K≤200). Каждая из последующих M строк содержит N чисел, записанных в соответствующих клеточках.

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

Первая строка выходного файла GOODWAYS.SOL должна содержать максимальную возможную сумму; вторая строка - количество маршрутов, сумма чисел которых отличается от максимальной не более чем на K.

Пример входных и выходных данных

GOODWAYS.DAT

GOODWAYS.SOL

2 3 3

1 9 7

2 5 3

20

2

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

Задача 98674

 [Ожерелье]
Тема:   [ Сортировка массива ]
Сложность: 4
Классы: 8,9,10,11

Имя входного файла:

necklace.in

Имя выходного файла:

necklace.out

Максимальное время работы на одном тесте:

1 секунда

Максимальный объем используемой памяти:

64 мегабайта

Максимальная оценка за задачу:

100 баллов

   

В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.

Продавец хочет упорядочить колечки так, чтобы они располагались по возрастанию номеров вдоль нити по часовой стрелке. Снимать ожерелье с манекена нельзя.

Требуется написать программу, которая по заданному начальному расположению колечек находит последовательность протаскиваний колечек одно через другое, приводящую исходное расположение колечек в желаемое.

Формат входных данных

В первой строке входного файла записано число N (2 ≤ N ≤ 50).

Во второй строке через пробел следуют N различных чисел от 1 до N - номера колечек, расположенных вдоль нити по часовой стрелке.

Формат выходных данных

Выходной файл должен содержать описание процесса упорядочения.

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

Количество строк выходного файла не должно превышать 50000.

Если требуемого упорядочения колечек достичь не удается, в выходной файл нужно вывести одно число √1.

Пример

necklace.in

necklace.out

4

3 2 4 1

1 3

2 4

1 4

0

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

Задача 98695

 [Сократи векторы]
Тема:   [ Векторы ]
Сложность: 4
Классы: 8,9,10,11

Максимальное время работы на одном тесте: 1 секунда

На плоскости задано N векторов - направленных отрезков, для каждого из которых известны координаты начала и конца (вектор, у которого начало и конец совпадают, называется нуль-вектором, можно считать, что нуль-вектор лежит на любой прямой, которая через него проходит). Введем следующие три операции над направленными отрезками на плоскости:

1) Направленные отрезки ненулевой длины, лежащие на пересекающихся прямых, можно заменить на их сумму, причем единственным образом. В этом случае отрезки переносятся вдоль своих прямых так, чтобы их начала совпадали с точкой пересечения прямых, и складываются по правилу сложения векторов (правилу параллелограмма, при этом началом результирующего вектора является точка пересечения прямых):

2) Направленные отрезки, лежащие на одной прямой, также можно заменить на их сумму. Для этого один из отрезков (любой) нужно перенести в начало второго из них и сложить по правилу сложения векторов на прямой:

Это правило применимо и в случае, когда один из векторов, или даже оба, являются нуль-векторами.

Заметим, что если складываемые векторы противоположно направлены и имеют одну и ту же длину, то результатом их сложения является нуль-вектор.

3) В любой точке плоскости можно породить два противоположно направленных отрезка равной (в том числе и нулевой) длины:

Будем говорить, что некоторая система векторов B эквивалентна системе A, если от системы A можно перейти к B с помощью конечной последовательности перечисленных выше операций.

Требуется получить любую систему векторов, эквивалентную заданной, состоящую из минимально возможного числа векторов.

Формат входных данных

В первой строке входного файла f.in записано число N - количество заданных векторов (1 < N ≤ 1000). В каждой из следующих N строк через пробел записаны четыре числа, обозначающие координаты начала и конца каждого из векторов соответственно. Все координаты - целые числа, по модулю не превосходящие 1000.

Формат выходных данных

В первой строке входного файла f.out следует записать число M - количество векторов в полученной системе (1 ≤ MN). В каждой из следующих M строк через пробел должны находиться четыре числа, обозначающие координаты начала и конца каждого из векторов соответственно. Все координаты - вещественные числа, записанные с 6 цифрами после точки.

Примеры

f.in

f.out

3

1 1 1 3

3 3 3 1

5 1 7 1

1

3.000000 3.000000 5.000000 3.000000

2

2 4 5 10

-2 -4 -5 -10

1

2.000000 4.000000 2.000000 4.000000

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

Задача 98851

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

В Театре собираются поставить грандиозную пьесу из двух актов, в которой освещение имеет большое значение. Сцена театра имеет форму выпуклого многоугольника, заданного вершинами в декартовой прямоугольной системе координат. Над сценой находится прожектор, который может перемещаться над ней произвольным образом. Находясь в некоторой точке, прожектор освещает круглую область с центром в этой точке и радиусом R.

В первом акте на сцене лежат квадратные ковры размером HxH, стороны которых параллельны осям координат. Ковры могут частично выходить за пределы сцены. Рассмотрим фигуру, которая состоит из всех точек, находясь в которых, прожектор не освещает ни один из ковров и не освещает территорию вне сцены. Обозначим ее площадь как S1.

Перед вторым актом ковры убирают со сцены. Рассмотрим фигуру, которая состоит из всех точек, находясь в которых прожектор не освещает территорию вне сцены. Ее площадь обозначим как S2.

Задание

По предоставленным входным файлам, каждый из которых описывает сцену и размещение на ней ковров в первом акте, создайте соответствующие им выходные файлы, которые содержат площади S1 и S2 описанных выше фигур.

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

На вашем диске в каталоге DATA содержатся 10 файлов, которые имеют названия THEATER.D01, THEATER.D02, : , THEATER.D10, следующего формата.

В первой строке заданы числа R, H, N, M. Где R - радиус области, которую освещает прожектор. - длина стороны квадрата, который представляет ковер. N - количество вершин выпуклого многоугольника, который задает сцену. M - количество ковров. Во второй строке находятся N пар чисел - координаты вершин многоугольника в порядке обхода (по или против часовой стрелки). В третьей строке находятся M пар чисел - координаты центров ковров.

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

Создайте 10 выходных файлов THEATER.S01, THEATER.S02, : , THEATER.S10 в вашем каталоге на дискете. Эти файлы должны содержать ответы для соответствующих входных файлов.

Каждый файл должен содержать два числа - целые части площадей S1 и S2. Вам не нужно сдавать программу! Баллы будут начисляться за файлы с правильными ответами.

Пример входных и выходных данных

THEATER.D00

THEATER.S00

0.5 2 4 1

1 1 5 1 5 4 1 4

3 4

3 6

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

Страница: << 6 7 8 9 10 11 12 >> [Всего задач: 56]      



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

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