--->
118 задач
<---
Источники
#1131
Темы:
[Перебор с отсечением]
[Двумерные массивы]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
«Что за свинья прошла здесь - корова, что ли?»
Под дворцом царя Миноса размером NxM построен одноэтажный лабиринт размером NxMx1. Некоторые из кубов 1x1x1 в этом лабиринте пустые, а некоторые — гранитные (сквозь них ходить нельзя). Количество пустых кубов в лабиринте S. Минотавр, гуляя в этом лабиринте только по пустым кубам, может дойти от любого пустого куба до любого другого пустого.
К сожалению, минотавр очень громко топает, поэтому выбранная им жертва успевает испугаться и убежать. Для того, чтобы этого избежать, фирма «Минос, минотавр and Co» закупила ковролин, которым собирается застелить пол пустых кубов, чтобы минотавр мог подбираться к жертве бесшумно. Рулон ковролина имеет размеры 1хS.
Рабочие хотят застелить пол лабиринта, сделав как можно меньше разрезов ковролина (разрезы разрешается делать только параллельно стороне рулона, имеющей длину 1).
Напишите программу, вычисляющую это минимальное число разрезов.
Входные данные
Во входном файле записано сначала число N, затем число M, задающие размеры лабиринта (1N10, 1M10). Далее идет N строк, по M чисел в каждой, задающих лабиринт. Каждое из этих чисел 0 или 1 — 0 означает пустой куб, а 1 — гранитный.
Выходные данные
В выходной файл выведите одно число — минимальное возможное количество разрезов, которое нужно сделать в рулоне, чтобы застелить все пустые клетки лабиринта.
Примеры
Входные данные
1 10 1 1 1 1 1 0 0 0 0 0
Выходные данные
0
Входные данные
2 2 1 0 0 0
Выходные данные
1
#1132
Темы:
[Двумерные массивы]
[Задачи на моделирование]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
На шахматной доске стоит несколько офицеров и ладей. Требуется посчитать количество свободных клеток, которые не находятся под боем ни одной из фигур.
Замечание для тех, кто не умеет играть в шахматы:
Шахматная доска имеет размеры 8*8. Ладья бьет все клетки горизонтали и вертикали, проходящих через клетку, где она стоит, до первой встретившейся фигуры. Офицер бьет все клетки обеих диагоналей, проходящих через клетку, где он стоит, до первой встретившейся фигуры.
Входные данные
В первых восьми строках входного файла описывается шахматная доска. Первые восемь символов каждой из этих строк описывают состояние соответствующей горизонтали: символ B (заглавная латинская буква) означает, что в клетке стоит офицер, символ R — ладья, символ * — что клетка пуста. После описания горизонтали в строке могут идти пробелы, однако длина каждой строки не превышает 250 символов. После описания доски в файле могут быть пустые строки.
Выходные данные
В выходной файл выведите количество пустых клеток, которые не бьются ни одной из фигур.
Примеры
Входные данные
******** ******** *R****** ******** ******** ******** ******** ********
Выходные данные
49
Входные данные
******** ******** ******B* ******** ******** ******** ******** ********
Выходные данные
54
#1205
Темы:
[Двумерные массивы]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Региональный этап,
2009,
1 день,
Задача A
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной 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 балла.
Примеры
Входные данные
5 3 01000 11110 01000 10110 00010 10110 0110
Выходные данные
11110 11100 11110
#1206
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Региональный этап,
2009,
1 день,
Задача B
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.
В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.
Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x3, y3) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x3, y3) не превышало r.
Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?
Требуется написать программу, которая позволит дать ответ на вопрос Ивана.
Входные данные
В первой строке входного файла содержатся четыре целых числа x1, y1, x2, y2 (−100 000 ≤ x1 < x2 ≤ 100 000; −100 000 ≤ y1 < y2 ≤ 100 000).
Во второй строке входного файла содержатся три целых числа x3, y3, r (−100 000 ≤ x3, y3 ≤ 100 000; 1 ≤ r ≤ 100 000)
Выходные данные
В выходной файл необходимо вывести одно целое число — число пучков травы, которые были и пострижены, и политы.
Иллюстрация к примеру
Разбалловка для личной олимпиады
Тест 1 — из условия. Оценивается в 0 баллов.
Тесты 2-21 — дополнительных ограничений нет. Группа тестов оценивается в 100 баллов.
Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп.
Примеры
Входные данные
0 0 5 4 4 0 3
Выходные данные
14
#1242
Темы:
[Задачи на моделирование]
[Двумерные массивы]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Темное царство представляет собой лабиринт NxM, некоторые клетки которого окружены зеркальными стенами, а остальные — пустые. Весь лабиринт также окружен зеркальной стеной. В одной из пустых клеток лабиринта поставили светофор, который испускает лучи в 4 направлениях: под 45 градусов относительно стен лабиринта. Требуется изобразить траекторию этих лучей.
Когда луч приходит в угол, через который проходят зеркальные стены, дальше он идет так, как показано на рисунках (серым цветом показаны клетки, которые окружены зеркальными стенами). Аналогичным образом луч ведет себя, когда приходит на границу лабиринта.
Входные данные
В первой строке входного файла записаны два натуральных числа N и M — число строк и столбцов в лабиринте (каждое из чисел не меньше 1 и не больше 100). В следующих N строках записано ровно по M символов в каждой — карта лабиринта. Символ * (звездочка) обозначает клетку, окруженную зеркальными стенками, . (точка) — пустую клетку, символ X (заглавная латинская буква X) — клетку, в которой расположен светофор (такая клетка ровно одна).
Выходные данные
В выходной файл выведите N строк по M символов в каждой — изображение лабиринта с траекториями лучей. Здесь, как и раньше, * (звездочка) должна обозначать клетки, окруженные зеркальными стенами, . (точка) — пустые клетки, через которые лучи света не проходят, / (слеш) — клетки, через которые луч света проходит из левого нижнего угла в правый верхний (или обратно — из правого верхнего в левый нижний), \ (обратный слеш) — клетки, через которые луч проходит из левого верхнего угла в правый нижний (или обратно), а символ X (заглавная латинская буква X) — клетки, через которые лучи проходят по обеим диагоналям.
Примеры
Входные данные
3 5 X.... ..... .....
Выходные данные
XXXXX XXXXX XXXXX
Входные данные
3 3 ... ..X ...
Выходные данные
/X\ X.X \X/
Выбрано
:
|