31 мая 2006

Google Code Jam: задачи первого раунда

Зашёл на Google Code Jam Arena посмотреть, как бьются программари. Кстати, много наших там - я и в чате по-русски пообщался, и имена типа Danko или Olegator о многом говорят.

В этом туре задачи на 300, 500 и 1000 очков.

Пример задачи на 300 очков: вы хотите послать несколько продавцов из точки 0 в точку 1. Каждую точку, кроме тт. 0 и 1, должен посетить только один продавец, чтобы иметь возможность продать один и тот же товар несколько раз. Символ j элемента i хранит информацию о том, связаны ли точки i и j симметричной связью (1 - связаны, 0 - нет). Посчитайте максимальное число продавцов, которые могут быть посланы. Явно задача про графы, но что-то не припомню, как такое решается...

Пример задачи на 500 очков: полиндром - это строка, читающаяся одинаково в обе стороны (например, "казак"). Нужно найти максимальный по длине полиндром в строке. Например, строка "acdadc" имеет два максимальных полиндрома - "а" и "сdаdс". Все остальные полиндромы, типа "dаd" или "с", могут быть расширены до "сdаdс", потому не являются максимальными. Ну, полиндромы. Тут ещё можно что-то придумать, хотя моё решение обычно не влезало в 2 секунды ограничения.

Пример задачи на 1000 очков: есть три кучи блоков - две вне склада, одна внутри. Есть кран для переноски блоков, который может переносить один блок за раз. Мы хотим перенести все блоки в склад. Более тяжелый блок нельзя ставить на более легкий. Требуется вычислить минимальное количество перестановок. Ну, тут ясно - ханойские башни, когда-то даже где-то я читал, как это решать.

Точно могу сказать, что за час бы я не уложился - дольше решение искать, чем прогать. Хотя если всё время натаскивать себя на такие задачки, то наверняка потом будешь щёлкать их как орехи...

4 комментов:

Анонимный комментирует...

Ну всё-таки не найти максимальный по длине палиндром, а посчитать количество максимальных по включению палиндромов.

А4 комментирует...

Да, ты прав, я прочитал по диагонали.

Concatenate the elements of str to form one long string, and return the number of maximal palindrome substrings contained in that string.

Анонимный комментирует...

2 задача:а можно узнать длину строки?
у меня такая идея: если перевернуть строку и найти наибольшую общую подпоследовательность нашей строки и перевернутой строки?

kostynru комментирует...

мне тут идея сумосшедшая пришла, строка в одну переменную, исходну строку вносим в другую переменную, затем переворачиваем исходную и сравниваем две строки выделяя от туда одинаковые фразы, затем смотрим какая длиннее и и вуоля

Отправить комментарий