На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Задача: Лотерея.
    Для проведения лотереи наклонный желоб наполнили N шарами (2 ≤ N ≤ 1000000), пронумерованных
    по порядку снизу вверх. Зрители из зала выкрикивают произвольное число k (1 ≤ k ≤ N) . Ведущий
    лотереи убирает из желоба k-тый шар, отсчитав его снизу желоба. После извлечения шара, верхние
    шары перемещаются по наклонному желобу вниз. Так повторяется до тех пор, пока шаров не
    останется. Требуется определить выигрышный номер шара, убранного последним.
    Входные данные
    В первой строке входного файла находится число N – количество шаров. Далее располагаются N
    строк, содержащих числа, которые называют зрители.
    Выходные данные
    В выходной файл требуется вывести одно число – номер последнего шара.

    Входные данные в файле:
    5
    1
    4
    3
    1
    1
    Результат работы в файле:
    3


    Задача вроде несложная, но как сделать не знаю
    Сообщение отредактировано: schooler -
      дерево с хранением размеров поддеревьев поможет решить задачу за O(NlogN)
        MBo спасибо за идею. Раньше никогда так не делал. Этим способом можно быстро извлекать элементы с определенным порядковым номером.

        Итак, моя реализация. Бинарное дерево будем хранить в массиве. Для каждой вершины будем хранить число листьев, которых можно достигнуть из нее. Листья будут соответствовать пронумерованным шарам.
        После построения дерева начинаем обход. В каждый момент будем хранить отрезок, как при бинарном поиске. Спускаясь вниз, выбираем нужную вершину, сокращаем отрезок.
        Задача "Лотерея", реализация алгоритма
        ExpandedWrap disabled
          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.
        0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
        0 пользователей:


        Рейтинг@Mail.ru
        [ Script execution time: 0.0634 ]   [ 15 queries used ]   [ Generated: 8.11.26, 14:57 GMT ]