#594

Темы: [Двумерные массивы] [Клеточная геометрия]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2006, 1 день, Задача D ]

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

Восстановите нарисованный Васей многоугольник.

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

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

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

Выведите искомый многоугольник в следующем формате.

Выходные данные должны содержать \(Y\) строк по 2\(X\)-1 символов в каждой (по одному символу на клетку и линию между клетками).

В первой строке выведите вертикальные отрезки в верхнем ряду клеток, обозначая их символом | (вертикальная черта - символ с кодом 124) и горизонтальные отрезки, отделяющие первый ряд клеток от следующего, обозначая их символом _ (подчеркивание). Если соответствующий отрезок в данном многоугольнике отсутствует, выведите вместо него символ . (точка). Во второй строке выведите в том же формате вертикальные отрезки во втором ряду и горизонтальные отрезки, отделяющие второй ряд от третьего. И т.д. В каждой строке на нечетных местах могут стоять только символы точка или подчеркивание, на четных местах - символы точка или вертикальная черта.

Гарантируется, что хотя бы одно решение существует. Если решений несколько, выведите любое из них.

Примеры

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

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

...._..
.._|.|.
.|_._|.
.......

#595

Диета

Темы: [Цикл for] [Вещественные числа]

В некоторой сверхсекретной лаборатории изучаются физические возможности животных. Любой живой организм нуждается в трех компонентах пищи – белках, жирах и углеводах. Известен набор продуктов, имеющийся в распоряжении лаборатории, и меню животных – сколько единиц каждого продукта они получают. Известно также, сколько белков, жиров и углеводов необходимо для нормальной жизнедеятельности животного. Необходимо определить, получает ли животное достаточное количество питательных веществ. Известно, что животному требуется в сутки \(X\) белков, \(Y\) жиров и \(Z\) углеводов.

Известно также, что всего животное получает в сутки \(N\) продуктов питания, и для каждого из них известны \(A_i\), \(B_i\), \(C_i\) и \(Q_i\) – соответственно, энергетическая ценность единицы продукта в белках, жирах и углеводах и количество единиц этого продукта. Все числа – действительные, заданные с точностью до 5 знаков после запятой.

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

На первой строке входных данных записаны числа \(X\) , \(Y\) и \(Z\) . На второй строке записано число \(N\). Далее на \(N\) строках записаны, соответственно, \(A_i\), \(B_i\), \(C_i\) и \(Q_i\).

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

Выведите YES , если данный пищевой рацион является достаточным по всем параметрам, и NO в противном случае.

Примеры

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

1.0 1.0 1.0
3
1 0 0 1
0 0.5 0 2
0 0 0.25 4

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

YES

#596

Утренняя пробежка - 1

Темы: [Цикл while] [Вещественные числа]

В первый день спортсмен пробежал \(x\) километров, а затем он каждый день увеличивал пробег на 70% от предыдущего значения. По данному числу \(y\) определите номер дня, на который пробег спортсмена составит не менее \(y\) километров.

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

На вход программа получает два действительных числа \(x\) и \(y\) . Числа положительные, действительные, не превосходят 1000, заданы с точностью до шести знаков после запятой.

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

Программа должна вывести единственное целое число.

Примеры

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

10 30

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

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

10 50

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

#597

Утренняя пробежка - 2

Темы: [Цикл while] [Вещественные числа]

В первый день спортсмен пробежал \(x\) километров, а затем он каждый день увеличивал пробег на 70% от предыдущего значения. По данному числу \(y\) определите номер дня, на который суммарный пробег спортсмена составит не менее \(y\) километров.

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

На вход программа получает два действительных числа \(x\) и \(y\) . Числа положительные, действительные, не превосходят 1000, заданы с точностью до шести знаков после запятой.
Внимание! В некоторых тестах оба числа находятся на одной строке, а в некоторых — на разных!

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

Программа должна вывести единственное целое число.

Примеры

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

1 20

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

#598

Маджонг

Темы: [Задачи на моделирование] [Очередь]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2007, 1 тур, Задача A ]

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

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

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

Цель игры состоит в том, чтобы сделать как можно больше ходов.

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

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

Первая строка входного файла содержит размеры доски: два целых числа \(m\) и \(n\) (1 ≤ \(m\), \(n\) ≤ 300, хотя бы одно из этих чисел четно). Далее следуют \(m\) строк по \(n\) чисел в каждой, \(j\)-е число в \(i\)-й из этих строк представляет собой номер цвета \(j\)-й слева фишки в \(i\)-й горизонтали. Цвета пронумерованы натуральными числами от 1 до \(n\)*\(m\) / 2. На доске ровно две фишки каждого цвета.

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

В первой строке выходного файла выведите \(k\) — максимальное количество ходов, которое может сделать Петя из заданной начальной позиции. Во второй строке выходного файла выведите разделенные пробелами \(k\) чисел — номера цветов фишек в том порядке, в котором они должны сниматься с доски. Если возможных ответов несколько, выведите любой.

Примеры

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

1 2
1 1

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

1
1

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

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

2
2 1