Страница: 1 Отображать по:
#1938
ЕГЭ
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

С целью упрощения ЕГЭ по литературе, было решено оставить в нем вопросы только с ответами «да» или «нет». Бланк ответов представляет клетчатое поле из \(N\) строк и \(M\) столбцов, в котором каждая клеточка соответствует своему вопросу. Ученику необходимо один раз перечеркнуть по диагонали те клеточки, которые, по его мнению, соответствуют вопросам с ответом «нет» (перечеркивать можно по любой из двух диагоналей). При этом во избежание ошибок при сканировании, никакие две диагонали не должны "сливаться", то есть иметь общий конец.

Авторам варианта необходимо знать, какое наибольшее количество вопросов с ответом «нет» можно вставить в вариант, чтобы бланк с правильными ответами мог быть верно распознан компьютером.

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

Вводится два натуральных числа – количество строк \(N\) и количество столбцов \(M\). Количество вопросов в варианте не превосходит 100, то есть \(1 ≤ N ∙ M ≤ 100\).

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

В первую строку выведите одно число — максимальное количество вопросов с ответом «нет», которое можно включить в вариант. В следующие N строк выведите по M символов – пример такого бланка с правильными ответами, верно распознаваемый компьютером. Никакие две диагонали не должны иметь общих концов. Руководствуйтесь следующими обозначениями: . (точка) — пустая клетка, соответствующая ответу «да»; / или \ — перечеркнутые по диагонали справа налево или слева направо клетки, соответствующие ответу «нет». Если существует несколько вариантов заполнения бланка, выведите любой.

Примеры
Входные данные
1 1
Выходные данные
1
/
Входные данные
2 1
Выходные данные
2
/
/
Входные данные
3 3
Выходные данные
6
///
../
\\.
#1942
Авангардная архитектура
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

В приведенном примере показаны привлекательности видов из окна и наилучшее здание из 10 кубиков в данном случае.

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

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

В первой строке входного файла указаны натуральные числа \(N\), \(H\) и \(W\) (1 ≤ \(H\) ≤ 30, 1 ≤ \(W\) ≤ 30, 1 ≤ \(N\) ≤ \(HW\)) — количество имеющихся кубиков, максимальная высота и максимальная ширина здания. Следующие H строк содержат по \(W\) натуральных чисел, задающих привлекательность соответствующего расположения квартиры. Привлекательность измеряется в пределах от 1 до 100 000 включительно.

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

Выведите одно число — наибольшую суммарную привлекательность.

Примеры
Входные данные
10 6 7
9 3 6 4 8 1 3
2 9 2 5 3 2 6
1 1 8 4 6 5 4
1 9 6 5 3 4 5
6 2 5 6 7 1 2
2 6 7 5 6 4 3
Выходные данные
65
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест