Задача - создать программу для подсказки населенных пунктов по введенной подстроке.
Подобная система действует сейчас ВКонтакте при вводе названия города в определенной стране.
Отличие данной задачи состоит в том, что в ней должны подсказываться населенные пункты из всех стран с учетом названия страны и названия родительского населенного пункта (района, области).
Задание состоит из двух подзадач.
I. Создать программу, которая импортирует названия всех населенных пунктов
В целях выполнения задачи нужны следующие данные:
- 1. Наименование населенного пункта.
- 2. Наименование родительского населенного пункта, если он указан (например, наименование области).
- 3. Население населенное пункта, если оно указано.
- 4. Наименование страны.
Данные, которые не относятся к населенных пунктам (названия рек, гор, озер и т.д.) импортировать не нужно.
II. Создать программу, которая подсказывает список населенных пунктов по введенной подстроке
Программа должна подсказывать список населенных пунктов, в которых любое из слов начинается на введенное сочетание букв.
Кроме того, нужно учитывать англоязычное название страны и ее двухбуквенный код, а также наименование родительского населенного пункта. Если введено несколько слов, то их порядок не имеет значения.
Все следующие запросы должны в ответ выдавать New York City:
New York City United States
York New City States
York US
States United York New City
Запрос "Aspen Pitkin County Colorado United States" должен возвращать город Aspen из графства Pitkin штата Colorado.
Список подходящих населенных пунктов выводить в порядке уменьшения населения.
Принимаются архивы .tar.gz, содержащие необходимые *.c, *.h и Makefile.
После распаковки архива нужные программы будут собираться программой make на 32-битной системе linux debian etch с ядром 2.6 с использованием GCC 4.3. Допускается использование расширений C, поддерживаемых этим компилятором, но не режимы C99 или C++. Желательно, но не обязательно, чтобы программы компилировались и на 64-битной системе.
Должны собраться как минимум две программы:
- import <binary-file-name> -- запускается в каталоге, где распакованы указанные выше архивы, и создает двоичный файл <binary-file-name> в произвольном формате.
- query <binary-file-name> -- открывает указанный двоичный файл, после чего читает стандартный ввод и выполняет указанные там запросы, выдавая ответ в стандартный вывод.
Каждая строка ввода будет содержать список ключевых слов, перечисленных через пробел, в кодировке utf8.
Для каждой непустой строки ввода надо выдать найденные ответы (но не более 10 штук) в порядке убывания населения, по одному на строку, после чего выдать пустую строку.
Каждая строка должна иметь вид
city_id\tcity_name\n
Запросы должны выполняться последовательно в режиме online (в порядке поступления), а не в пакетном режиме
Программа может создавать один двоичный файл размером не более 16 гигабайт, и использовать при работе не более 2 гигабайт оперативной памяти. В случае необходимости при работе можно обращаться к диску.
- Стиль и понятность кода (подробные комментарии не требуются, особенно если код написан таким образом, чтобы почти все места были понятны сами собой, названия функций и глобальных переменных осмысленны и т.п.)
- Соответствие выдаваемых результатов ожиданиям потенциального пользователя.
- Эффективность алгоритма
- Скорость работы на фактических наборах тестов
- Скорость загрузки (время с момента запуска программы query до готовности к выполнению первого запроса)
- Размер файла на диске
- Количество используемой оперативной памяти
- Количество обращений к диску и объем считываемых данных, в том случае, если программа query обращается к диску во время работы.
От разработчика требуется умение писать программы по не слишком конкретизированному заданию, руководствуясь здравым смыслом; выдаваемый результат должен выглядеть естественно с точки зрения обычного пользователя, и в то же время иногда имеет смысл пожертвовать ненужными возможностями, если это упростит код и ускорит программу.
Крайне желательно написать полностью свой код, не подключая библиотеки, отличные от стандартных вроде libc, и не используя модули, написанные другими людьми (например, доступные по GPL).
- Первое место: Sony Vaio Z или 60 000 руб.
- Второе место: Apple iPhone 3Gs или 30 000 руб.
Участников, занявших первое или второе место, может быть больше одного.
Участники, справившиеся с задачей наилучшим образом, получат бессрочное приглашение присоединиться к команде разработчиков ВКонтакте в Петербурге.
- Начало: 18.02.2010
- Окончание: 1.03.2010 (18:00)
