#1205

Черно-белая графика

Темы: [Двумерные массивы]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2009, 1 день, Задача A ]

Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной w и высотой h, разбитых на w×h единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.

Во многих областях очень часто возникает задача комбинации изображений. Одним из простейших методов комбинации, который используется при работе с черно-белыми изображениями, является попиксельное применение некоторой логической операции. Это означает, что значение пиксела результата получается применением этой логической операции к соответствующим пикселам аргументов. Логическая операция от двух аргументов обычно задается таблицей истинности, которая содержит значения операции для всех возможных комбинаций аргументов. Например, для операции «исключающее ИЛИ» эта таблица выглядит так.

Первый аргумент	Второй аргумент	Результат
0	0	0
0	1	1
1	0	1
1	1	0

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

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

Первая строка входного файла содержит два целых числа w и h (1 ≤ w, h ≤ 100). Последующие h строк описывают первое изображение и каждая из этих строк содержит w символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка входного файла содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента – нули, второе – результат в случае, если первый аргумент – ноль, второй – единица, третье – результат в случае, если первый аргумент – единица, второй – ноль, а четвертый – в случае, если оба аргумента – единицы.

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

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

Разбалловка для личной олимпиады

Тест 1 — из условия. Оценивается в 0 баллов.

Тесты 2-26 — дополнительных ограничений нет. Группа тестов оценивается в 100 баллов.

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

Примеры

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

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

11110
11100
11110

#1206

Газон

Темы: [Пересечение множеств] [Задачи на моделирование] [Двумерные массивы]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2009, 1 день, Задача B ]

Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.

В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x₁, y₁) и (x₂, y₂). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.

Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x₃, y₃) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x₃, y₃) не превышало r.

Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?

Требуется написать программу, которая позволит дать ответ на вопрос Ивана.

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

В первой строке входного файла содержатся четыре целых числа x₁, y₁, x₂, y₂ (−100 000 ≤ x₁ < x₂≤ 100 000; −100 000 ≤ y₁ < y₂≤ 100 000).

Во второй строке входного файла содержатся три целых числа x₃, y₃, r (−100 000 ≤ x₃, y₃ ≤ 100 000; 1 ≤ r≤ 100 000)

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

В выходной файл необходимо вывести одно целое число — число пучков травы, которые были и пострижены, и политы.

Иллюстрация к примеру

Разбалловка для личной олимпиады

Тест 1 — из условия. Оценивается в 0 баллов.

Тесты 2-21 — дополнительных ограничений нет. Группа тестов оценивается в 100 баллов.

Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп.

Примеры

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

0 0 5 4
4 0 3

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

#1926

Миша и негатив

Темы: [Строки] [Двумерные массивы] [Условный оператор (if)]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2010, 2 день, Задача A ]

Миша уже научился хорошо фотографировать и недавно увлекся программированием. Первая программа, которую он написал, позволяет формировать негатив чёрно-белого изображения.

Бинарное чёрно-белое изображение — это прямоугольник, состоящий из пикселей, каждый из которых может быть либо чёрным, либо белым. Негатив такого изображения получается путём замены каждого чёрного пикселя на белый, а каждого белого пикселя — на чёрный.

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

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

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

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

Первая строка входного файла содержит целые числа \(n\) и \(m\) (\(1\le n,m\le100\)) — высоту и ширину исходного изображения (в пикселях).

Последующие \(n\) строк содержат описание исходного изображения. Каждая строка состоит из \(m\) символов «B» и «W». Символ «B» соответствует чёрному пикселю, а символ «W» — белому.

Далее следует пустая строка, а после неё — описание выведенного Мишиной программой изображения в том же формате, что и исходное изображение.

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

В выходной файл необходимо вывести число пикселей негатива, которые неправильно сформированы Мишиной программой.

Примеры

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

3 4
WBBW
BBBB
WBBW

BWWW
WWWB
BWWB

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

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

2 2
BW
BB

WW
BW

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

#111489

Города

Темы: [Двумерные массивы] [Жадный алгоритм]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2013, 1 день, Задача B ]

Юный программист решил придумать собственную игру. Игра происходит на поле размером \(N \times N\) клеток, в некоторых клетках которого расположены города (каждый город занимает одну клетку; в каждой клетке может располагаться не более одного города). Всего должно быть чётное количество городов.

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

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

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

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

Первая строка входного файла содержит одно целое положительное число N, задающее размер игрового поля (\(1 \leq N \leq 50\)).

Последующие N строк содержат по \(N\) заглавных латинских букв (без пробелов), кодирующих соответствующие клетки игрового поля: ‘C’ обозначает клетку, занятую городом, ‘D’ – пустую клетку. Гарантируется, что на поле есть хотя бы два города и всего их четное число.

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

Выходной файл должен содержать \(N\) строк по \(N\) цифр (без пробелов) в каждой, кодирующих соответствующие клетки. Цифра 1 обозначает, что данная клетка принадлежит первому государству, цифра 2 – данная клетка принадлежит второму государству. Если решений несколько, необходимо вывести любое из них.

Система оценивания

Правильные решения для тестов, в которых всего два города, будут оцениваться из 40 баллов.

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

Примеры

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

3
DDD
DDC
DDC

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

111
111
112

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

5
DDDDD
CDCDC
DCCDC
DDDDD
DDDDD

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

#111990

Тетрадка

Темы: [Двумерные массивы]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2013, 10-11 классы, Тетрадка ]

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

Формально, дана двухмерная таблица из нулей и единиц — часть тетрадки, которую видит Вася. Единицей обозначается закрашенный участок, а нулем — незакрашенный. Назовём вертикальной линией столбец таблицы, все элементы которого — единицы, а горизонтальной линией — строку таблицы, все элементы которой — единицы. Гарантируется, что каждая единица в таблице содержится в какой-либо линии.

Тетрадкой в клетку называется тетрадка, в которой содержатся вертикальные и горизонтальные линии. Тетрадкой в линейку называется тетрадка, в которой содержатся только горизонтальные линии. Тетрадкой в вертикальную линейку называется тетрадка, в которой содержатся только вертикальные линии.

Известно, что в целой тетрадке все расстояния между линиями одинаковы (то есть все клетки — квадраты, все линейки одинаковой ширины). Гарантируется, что линии не могут располагаться рядом (между ними всегда есть промежуток).

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

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

В первой строке входных данных даны целые числа n и m (1 ≤ n, m ≤ 1 000) — количество строк и столбцов в таблице. Следующие n строк по m чисел содержат целые числа a_i, j (0 ≤ a_i, j ≤ 1) — элементы таблицы, задающие видимую часть тетради.

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

Требуется вывести одну из строк:

«Square», если заданная тетрадка расчерчена в клетку;
«Line», если тетрадка расчерчена в линейку;
«Vertical line», если тетрадка расчерчена в вертикальную линейку;
«?», если невозможно однозначно определить, к какому типу относится данная тетрадь.

Примеры тестов

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

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

Square

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

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

Line

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

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

Примечание

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

Страница: 1 Отображать по: