G. Гроб

Ограничение времени: 2 с
Ограничение памяти: 256 M


Выходили из избы
Здоровенные жлобы
Порубили все дубы на гробы 

В.С. Высоцкий

Ни для кого не секрет, что студенты ОНУ любят и умеют зарабатывать деньги. Но мало кто знает, что Сигизмунд Гобсеков, студент кафедры Наноэкономики, устроился на лето разнорабочим в бюро ритуальных услуг «Милости Просим». Это бюро знаменито тем, что выпиливает гробы самых причудливых форм. Но вот незадача! Из-за вычурности форм гробов, их бывает непросто уложить в обычные прямоугольные ямы. Сейчас на клетчатом фанерном листе размера MxN мастер начертал эскиз своего очередного шедевра. Задача Сигизмунда – определить, можно ли будет уместить его после изготовления в яму размера AxB. Как это часто водится, задачу Сигизмунда будет решать отнюдь не Сигизмунд. Помните, что фэн-шуй запрещает укладывать гробы в ямы так, чтобы стороны гроба не были параллельны сторонам ямы.

Ввод. Первая строка ввода содержит числа M и N (1 ≤ M, N ≤ 100), разделённые пробелами. Далее в M строках содержится по N символов – ‘+’, если клетка принадлежит эскизу гроба и ‘.’ В противном случае. В последних двух строках содержатся числа A и B (1 ≤ A, B ≤ 100), разделённые пробелами.

Вывод. Если гроб можно уместить в яму, выведите строку “Inhumation” без кавычек. Иначе выведите строку “Cremation” также без кавычек.

Идея – Александр Сергеевич Антоненко

Примеры

Входные данные Результат работы
3 3
.+.
++.
...
2 2
Inhumation
3 3
.+.
++.
...
3 1
Cremation

Решение

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

Подсказка 1: минимальный охватывающий прямоугольник Select
Подсказка 2: ищем первый(последний) '+' в строке Select
Подсказка 3: два способа укладки - вдоль и поперек Select
Решение на Java: OK Select

Все получилось? Переходим к другим задачам. Я бы посоветовал чуть более сложную задачу B. Популяция - её решила четверть участников. Или поразмышляйте над задачей I. Свидание. Её никто не смог решить, но она отнюдь не такая страшная.

Анализ

Задачи A и G самые легкие на контесте. Обе легкие, но разные. В задаче А почти и кодировать нечего - одна простая формула. Вот только ее нужно найти. В задаче G кода намного больше, но придумывать особо ничего не нужно. То что задача с более сложным кодом, но не требующая размышлений, оказалась для участников несколько легче, говорит об особенностях подготовки. Действительно, во многих ситуациях в процессе обучения программированию акцент делается на синтаксис языка и шаблоны проектирования. Размышления над задачей уходят на второй план. В результате, получив задачу, программист начинает практически сразу нажимать клавиши. Т.е. применять освоенный инструментарий и шаблоны мышления. А подумать?
В задаче G думать не нужно. Вот и у меня она прошла с первой попытки... А простенькая задача А - только с 4-й...

About the post author Igor Mazurok (5 Posts)

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine KBIS Software Developer

Author Info

Igor Mazurok

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine
KBIS Software Developer

Добавить комментарий