Олимпиады

Задача “Прикладная педагогика”

У мальчика Феди есть прадедушка, который твердо решил научиться работать на компьютере. Несмотря на то, что прадедушке перевалило за 100 лет, он находится в здравом уме и трезвой памяти. Однако возраст все-таки сказывается: прадедушка подслеповат. Федя взялся побороть эту проблему и первым делом начал увеличивать изображение на экране, чтобы прадедушка мог его разглядеть.

Федя решил, что каждый пиксель монитора надо увеличить в K раз (т.е. представить в виде квадрата со стороной K). Так как монитор почти ровесник прадедушки, он умеет отображать только черный и белый цвета. Изображение представляет собой квадрат размером N х N пикселей, черный цвет кодируется 1, белый — 0.

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

В первой строке записано два натуральных числа N и K (1 N 100, 1K10). В N следующих строках записано по N единиц и нулей, не разделенных пробелами.

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

Выведите увеличенное изображение.

Решение

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

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

Таким образом, мы можем увеличивать одну строку с помощью трех вложенных циклов: по “высоте”, по исходной строке и по “длине”. Еще один, четвертый, внешний цикл будет идти по всем строкам исходной таблицы.

var

n, k, i, j, x, y : longint;

s : string;

begin

readln(n, k);

for i := 1 to n do begin

// цикл по строкам

readln(s);

for y := 1 to k do begin

// увеличиваем в высоту

for j := 1 to n do

// каждый символ строки

for x := 1 to k do

// увеличиваем в длину

write(s[j]);

writeln

end

end

end.

Из шахматной доски по границам клеток выпилили связную (не распадающуюся на части) фигуру без дыр. Требуется определить ее периметр.

Сначала вводится число N (1 N 64) — количество выпиленных клеток. В следующих N строках вводятся координаты выпиленных клеток, разделенные пробелом (номер строки и столбца — числа от 1 до 8). Каждая выпиленная клетка указывается один раз.

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

Выведите одно число — периметр выпиленной фигуры (сторона клетки равна единице).

Примеры

Решение

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

Таким образом, все вырезанные клетки будут помечены true. Периметр вырезанной фигуры будет складываться из единичных сторон клеток, которые разделяют вырезанную и не вырезанную клетки. Для решения достаточно пройти по всей таблице и, если ячейка вырезана, посмотреть четырех ее “соседей”. Если соседняя ячейка не вырезана, то мы нашли границу вырезанной фигуры и прибавляем к счетчику единицу. Все остальные случаи соседства (вырезанная с вырезанной и не вырезанная с не вырезанной) никак не влияют на искомый периметр.

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

var

n, s, i, j, x, y : longint;

table : array [0..9, 0..9] of boolean;

begin

s := 0; // периметр

for i := 0 to 9 do

for j := 1 to 9 do

table[i, j] := false;

// вначале не вырезанных нет

read(n);

for i := 1 to n do begin

read(x, y); // читаем

table[x, y] := true; // и сразу вырезаем

end;

for i := 1 to 8 do // рассматриваем таблицу без барьера

for j := 1 to 8 do

if table[i, j] = true then begin

// ячейка вырезана

// смотрим соседей

if table[i - 1, j] = false then inc(s);

if table[i + 1, j] = false then inc(s);

if table[i, j - 1] = false then inc(s);

if table[i, j + 1] = false then inc(s);

end;

writeln(s)

end.