Метка: google

Водоразделы (Watersheds) - Задача B квалификационного раунда Google Code Jam 2009.

Задача

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

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

• Для каждой ячейки вода стекает не более, чем в одну из четырех соседних ячеек.
• Для каждой ячейки, у которой ни одна из четырех соседних ячеек не имеет меньшей высоты, вода никуда не утекает. Такая ячейка называется низиной.
• В противном случае, вода утекает из ячейки в соседнюю с минимальной высотой.
• В случае, если несколько соседних ячеек имеют одну и ту же минимальную высоту, вода течет по первому возможному направлению из следующего списка: север, запад, восток, юг.

Каждая ячейка, стекающая, прямо или косвенно, в одну и туже низину, принадлежит к одному водосборному бассейну. Каждый бассейн помечается уникальной строчной буквой таким образом, что строки карты, будучи соединенными в одну большую сверху вниз, образующаяся строка является лексикографически наименьшей из всех возможных. (В частности, бассейн самой северо-западной ячейки помечается 'a'.)
...читать далее "Водоразделы"

"Язык пришельцев" (Alien Language) - Задача А предварительного раунда Google Code Jam 2009.

Задача

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

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

Шаблон состоит ровно из L токенов. Каждый токен является либо одной строчной буквой (и ученые уверены, что это именно та буква), либо группой различных строчных букв, заключенной в скобки ( и ). Например: (ab)d(dc) означает, что первая буква или a, или b, вторая буква точно d, а последняя буква либо d, либо c. Таким образом шаблон (ab)d(dc) соответствует одному из этих четырех возможных: add, adc, bdd, bdc.
...читать далее "Язык пришельцев"