Недавно наткнулся на одну задачи и до сих пор никак не решу!
В общем, вот она:
Ограничение по времени: 5 секунд
Ограничение по памяти: 1000K


Теория
База данных Пентагона хранит сверхсекретную информацию. Мы не знаем, что это за информация — она ведь сверхсекретная — зато знаем формат ее представления. Он удивительно прост. По неизвестным нам соображениям все данные кодируются натуральными числами от 1 до 5000. Размер основной базы (обозначим его через N) довольно велик — в ней может содержаться до 100000 таких чисел. База данных должна уметь быстро обрабатывать любые запросы, а самым распространенным из запросов является такой: "какой элемент является i-тым по величине", где i — натуральное число от 1 до N.
Задача
Ваша программа должна выступить в роли диспетчера этой базы данных; другими словами она должна уметь быстро обрабатывать запросы описанного вида.
Исходные данные
Входной файл для этой задачи состоит из двух частей. Сначала в нем записана база данных, потом серия запросов к ней. Формат представления базы данных очень прост: в первой строке записано число N, затем в N следующих строках числа из этой базы по одному в строке и в произвольном порядке. Серия запросов записывается также просто: в первой строке этой серии записано количество запросов K, 1 <= K <= 100, и далее в K строках по одному в строке идут запросы. Запрос «какой элемент является i-тым по величине» записывается для краткости просто одним числом i. База данных отделяется от серии запросов строкой из трех решеток "#".
Результат
Выходной файл должен состоять из K строк, в каждой из этих строк должен быть записан ответ на соответствующий запрос. Ответом за запрос "i" является элемент из базы, который идет в ней i-тым по величине, считая с наименьшего.
Пример исходных данных
5
7
121
123
7
121
###
4
3
3
2
5

Пример результата
121
121
7

Если кто знает ак к ней подойти подскажите, пожалуйста.

1. Что делает задача на паскале в форуме по асму, если ей место в "Технологии и алгоритмы"?
2. Проблема в скорости, памяти или решении вообще?

Что-то я не очень понял условие. Верно ли то, что задача сводится к выбору из неотсортированного массива целых чисел от 1 до 5000, например такого (те это и есть база данных ? Одна запись базы - одно число ?):

...
48 ; k-ая запись базы
15 ; k+1-ая запись базы
256
4371
15
165
...

элемента с номером i, причем выбор нужно уже осуществлять из как бы отсортированного массива ?

Если массив отсортирован, то выборка (запрос) однозначен. Или все не так ?

Если я правильно понял постановку, то задача заключается в том чтобы упорядочить входную последовательность (базу). Задача значительно упрощается поскольку значения входных чисел лежат в диапазрне 1-5000. Т.е. нам достаточно выделить некий первичный массив размерностью в 5000, индексами в котором будут служить входные числа, а значениями - кол-во вхождений конкретного числа. За первый проход у нас уже получиться упорядоченная, но разреженная последовательность (в ней будут дырки, и еще будут не известны реальные позиции, поскольку некоторые элементы могут встречаться несколько раз). За второй проход мы строим из этого массива второй (на первом проходе мы подсчитываем общее количество элементов, т.е. размерность второго - по ограничениям задачи он не должен быть больше 2 * 100000 = 200000 byte), в котором расставляем элементы по своим местам простым обходом первого массива.