1026 Timus answer/Решение задачи 1026


№1026
http://acm.timus.ru/problem.aspx?space=1&num=1026
ЖМИ ДАЛЕЕ>>>


РЕШЕНИЕ:

PASCAL

Type
TVector = array[1..5000] of LongInt;
Var
A :TVector;
I,J,N,L,S :LongInt;
Begin
FillChar(A,SizeOf(A),0);
Readln(N);
For I:=1 to N do begin
readln(L);
Inc(A[L]);
End;
Readln;
Readln(N);
For I:=1 to N do begin
Readln(L);
S:=0;
J:=0;
While (S<L) do begin
Inc(J);
S:=S+A[J];
End;
Writeln(J);
End;
End.

1026. Вопросы и ответы

Ограничение времени: 2.0 секунды
Ограничение памяти: 16 МБ

Вступление

База данных Пентагона хранит сверхсекретную информацию. Мы не знаем, что это за информация — она ведь сверхсекретная — зато знаем формат её представления. Он удивительно прост. По неизвестным нам соображениям все данные кодируются целыми числами от 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
123
Автор задачи: Леонид Волков
Источник задачи: Второе командное соревнование школьников Свердловской области по программированию, 7 октября 2000 
Ярлыки: