Задача: Лотерея.
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [216.73.216.88] |
|
|
правила раздела Алгоритмы

Задача: Лотерея.
|
Сообщ.
#1
,
|
|
|
|
Для проведения лотереи наклонный желоб наполнили N шарами (2 ≤ N ≤ 1000000), пронумерованных
по порядку снизу вверх. Зрители из зала выкрикивают произвольное число k (1 ≤ k ≤ N) . Ведущий лотереи убирает из желоба k-тый шар, отсчитав его снизу желоба. После извлечения шара, верхние шары перемещаются по наклонному желобу вниз. Так повторяется до тех пор, пока шаров не останется. Требуется определить выигрышный номер шара, убранного последним. Входные данные В первой строке входного файла находится число N – количество шаров. Далее располагаются N строк, содержащих числа, которые называют зрители. Выходные данные В выходной файл требуется вывести одно число – номер последнего шара. Входные данные в файле: 5 1 4 3 1 1 Результат работы в файле: 3 Задача вроде несложная, но как сделать не знаю |
|
Сообщ.
#2
,
|
|
|
|
дерево с хранением размеров поддеревьев поможет решить задачу за O(NlogN)
|
|
Сообщ.
#3
,
|
|
|
|
MBo спасибо за идею. Раньше никогда так не делал. Этим способом можно быстро извлекать элементы с определенным порядковым номером.
Итак, моя реализация. Бинарное дерево будем хранить в массиве. Для каждой вершины будем хранить число листьев, которых можно достигнуть из нее. Листья будут соответствовать пронумерованным шарам. После построения дерева начинаем обход. В каждый момент будем хранить отрезок, как при бинарном поиске. Спускаясь вниз, выбираем нужную вершину, сокращаем отрезок. Задача "Лотерея", реализация алгоритма ![]() ![]() const maxN=1048576; var S:array[1..2*maxN] of record N:integer; // номер шара K:integer; // число листьев в поддереве end; N, i, j, K, L, R, cur:integer; procedure doIt(F{число поддеревьев}, i:integer); begin if F=1 then // нашли лист begin S[i].K:=1; // из листа можно достичь только его самого S[i].N:=cur; // устанавливаем номер inc(cur); end else begin S[i].K:=F; // записываем число достижимых листьев doIt(F div 2, i*2); doIt(F-F div 2, i*2+1); end; end; var last:integer; // этот номер был последним begin AssignFile(input, 'input.txt'); Reset(input); ReadLn(N); cur:=1; DoIt(N, 1); // строим дерево for i:=1 to N do begin ReadLn(K); // читаем очередной порядковый номер j:=1; // обход начинаем с корня L:=1; // левая и правая граница R:=S[j].K; // в данном поддереве есть только листья // с порядковым номером от L до R // некоторое подобие бинарного поиска while (S[j].N=0) do if (L+S[2*j].K-1>=K) then begin j:=2*j; // выбираем левого ребенка R:=L+S[j].K-1; // сокращаем отрезок end else begin j:=2*j+1; // выбираем правого ребенка L:=R-S[j].K+1; // сокращаем отрезок end; last:=S[j].N; // запоминаем выбранный номер while j>=1 do // обновляем число листьев begin dec(S[j].K); j:=j shr 1; end; end; CloseFile(input); AssignFile(output, 'output.txt'); ReWrite(output); WriteLn(last); CloseFile(output); end. |