Взято из Google Code Jam 2013. Отборочный раунд Задача B :
Алиса и Боб имеют лужайку перед своим домом в форме прямоугольника N метра на М метра. Каждый год они пытаются подстричь газон по какой-то интересной схеме. Они делали свою стрижку ножницами, что занимало очень много времени; но теперь у них есть новая автоматическая газонокосилка с несколькими настройками, и они хотят попробовать это.
Новая газонокосилка имеет настройку высоты - вы можете установить ее на любую высоту h от 1 до 100 миллиметров, и она будет подстригать всю траву выше, чем h, с которой она сталкивается, до высоты h. Вы управляете этим, входя в газон в любой части края газона; затем газонокосилка движется по прямой линии, перпендикулярной к краю газона, в который она попала, подрезая траву валком шириной 1 м, пока он не выйдет из газона на другой стороне. Высота газонокосилки может быть установлена только тогда, когда она не на газоне.
У Алисы и Боба есть несколько различных типов травы, которые они могли бы иметь на своем газоне. Для каждого из них они хотят знать, возможно ли срезать траву по этой схеме с помощью новой газонокосилки. Каждый рисунок описывается путем указания высоты травы на каждом квадрате 1 х 1 м газона.
Трава изначально имеет высоту 100 мм на всей лужайке.
Напишите функцию, которая получает двумерный массив целочисленных высот и определяет, можно ли соответствующим образом обрезать газон.
Вот 100 тестовых примеров из Google Code Jam. Первые 35 случаев должны пройти, остальные не должны.
Самый короткий код выигрывает.
Ответы:
J, 15 символов
Не ожидал этого короткого решения.
Краткое объяснение:
Если функция 4 другие функции , как и в растворе:
(f1 f2 f3 f4)
а вход J вычисляет его какf1(input,f3(f2(input),f4(input)))
естьinput f1 ((f2 input) f3 (f4 input))
.источник
APL, 15 символов
Объяснение:
⌈⌿⍵
вычисляет максимум столбцов rhs⌈/⍵
делает то же самое со строками∘.⌊
делает внешнее произведение двух предыдущих относительно функции минимум⍵≡
сравнивает результат с RHSПримеры:
источник
Питон,
112104источник
map(min,z(*r))
вместо того,[min(a)for a in z(*r)]
чтобы сохранить 8 символовУ меня немного более длинный код Python, но он прошел все тестовые примеры, приведенные на Google Code Jam 2013.
источник