Темы --> Информатика --> Язык программирования --> Массивы --> Двумерные массивы
---> 20 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 1 2 3 4 >> Отображать по:
#1101
Стрелочки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Поле заполнено стрелочками, которые задают направление перехода из этой клетки. Требуется определить количество клеток поля, начиная движение с которых фишка никогда не покинет поля.

На бумаге нарисовали клетчатое поле NxM клеток. В каждой клетке нарисовали стрелочку в одном из четырех направлений «вправо», «вверх», «влево» или «вниз».

←

→

→

↓

↑

→

↑

↓

←

→

↓

↑

→

→

↓

→

↑

←

←

←

←

→

↓

↓

↓

↑

↑

←

↓

↑

Дальше в некоторую клетку этого поля ставят фишку. Затем эту фишку сдвигают в соседнюю клетку в направлении стрелочки, нарисованной в клетке, где стоит фишка. Затем ее снова сдвигают по стрелке, нарисованной в той клетке, где она оказалась. Так продолжается до тех пор, пока фишка не окажется за пределами поля. Однако возможно, что фишка будет бесконечно ходить по полю и никогда не выйдет за его пределы.

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

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

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

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

В выходной файл выведите одно число – количество клеток, начав с которых фишка никогда не покинет пределы поля.

Комментарии к примерам тестов.

Пример №1.Соответствует приведенному рисунку. Клетки, начавс которых, фишка никогда не покинет пределов поля на рисунке выделены серым цветом.

Примеры
Входные данные
6 5
3 1 1 4 2
1 2 4 3 1
4 2 1 1 4
1 2 3 3 3
3 1 4 4 4
2 2 3 4 2
Выходные данные
23
Входные данные
2 2
1 2
3 4
Выходные данные
0
#1205
Черно-белая графика
  
ограничение по времени на тест
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
Газон
  
ограничение по времени на тест
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
#1926
Миша и негатив
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
3 4
WBBW
BBBB
WBBW

BWWW
WWWB
BWWB
Выходные данные
2
Входные данные
2 2
BW
BB

WW
BW
Выходные данные
2
#3890
Шарики
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Фирма, в которой работает ваш друг, решила установить на конечной остановке своих маршруток большую абстрактную скульптуру со своим логотипом. Скульптура будет представлять собой прямоугольную сетку из \(N\) строк и \(M\) столбцов, в некоторых узлах которой будут располагаться разноцветные шары. Для обеспечения жёсткости конструкции шары, расположенные в узлах, соседних по вертикали, горизонтали или диагонали, необходимо соединить металлическими стержнями. Более строго, два шара должны быть соединены стержнем, если разность номеров строк, в которых расположены эти шары, не превосходит по модулю единицы, и разность номеров столбцов тоже не превосходит по модулю единицы.

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

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

В первой строке входного файла находятся два натуральных числа \(N\) и \(M\) — размеры конструкции (\(1\leq N,M\leq 100\)). Далее следуют \(N\) строк по \(M\) символов в каждой. Каждый символ — это или “#” (решетка), обозначающий, что в соответствующем узле будет находиться шарик, или “.” (точка), обозначающий, что соответствующий узел будет пустой.

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

Выведите в выходной файл \(2N-1\) строку по \(2M-1\) символов в каждой, изображающие как сами шары, так и соединяющие их стержни. А именно, в нечётных позициях нечётных строк выведите символ “#” или “.”, в зависимости от того, заполнен этот узел шариком или нет, а в остальных позициях выведите один из символов “ ” (пробел), “-” (минус), “|” (вертикальная палочка, ASCII #124), “/” (дробь, ASCII #47), “\” (обратный слеш, ASCII #92) или “X” (латинская заглавная буква X, ASCII #88), отражающий конфигурацию стержней в соответствующем месте структуры.

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

Примечание

Первый пример соответствует рисунку.

Примеры
Входные данные
3 4
##.#
#.##
####
Выходные данные
#-# . #
|/ \ /|
# . #-#
|\ /|X|
#-#-#-#
Входные данные
3 4
.#..
#.#.
.#..
Выходные данные
. # . .
/ \
# . # .
\ /
. # . .
Страница: << 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест