Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 20.11.2018, 19:28   #1
KiLLtan
Новичок
Джуниор
 
Регистрация: 20.11.2018
Сообщений: 2
По умолчанию Помогите с решением подобных задач (Олимпиадная задача на получение элементов линейного массива в заданном порядке)

Помогите, пожалуйста, с решением подобных задач. Как выбирать числа из массива и удалять их?

У Жарасхана есть n документов выложенных в ряд. В каждом документе содержится секретное
число ai. Также у Жарасхана есть некоторые поручения от начальника. Есть 3 типа поручений:
В поручениях первого типа начальник просит сообщить секретное число в самом левом доку-
менте, а затем уничтожить этот документ.
В поручениях второго типа начальник просит сообщить секретное число в самом правом документе, а затем уничтожить этот документ.
В поручениях третьего типа начальник просит сообщить секретное число в документе который лежит в середине всех документов, а затем уничтожить этот документ. Если у списка
документов нет серединного документа, выбрать документ который лежит слева от середины.
Но Жарасхан заранее знает что начальство даст все поручения в повторяющемся порядке. А
именно начальник даст поручение первого типа, затем второго, затем третьего, и еще раз первого,
второго, третьего и так далее пока список документов не окажется пуст.
Жарасхан очень занят другими поручениями. Он просит вас помочь, иначе он лишится работы.
Формат входных данных
В первой строке входных данных содержит единственное целое положительное число n
(1 ⩽ n ⩽ 105) — количество документов в списке.
Вторая строка содержит n целых чисел ai (1 ⩽ ai ⩽ 109) — секретные числа в документах.
Формат выходных данных
Выведите n чисел — секретные числа которых должен Жарасхан сообщить начальнику после
каждой операции.
Пример
стандартный ввод
6
4 5 9 8 6 7
стандартный вывод
4 7 9 5 6 8

Замечание
В первом тестовом примере удаляется первое число. Оставшиеся документы: [5, 9, 8, 6, 7] Затем
удаляется последнее число. Оставшиеся документы: [5, 9, 8, 6] Так как список не имеет серединного
документа, следует выбрать число которое лежит слева от середины. Оставшиеся документы: [5, 8,
6] Эти поручения обрабатываются и дальше по такому же порядку.
KiLLtan вне форума Ответить с цитированием
Старый 20.11.2018, 22:10   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

удалять не рентабельно. Задача явно олимпиадная, а значит имеет ограничение по времени.

я не мастер решать олимпиадные задачи.
Вполне возможно, что придёт настоящий олимпиец и расскажет о том,
как лучше решить эту задачу.

Думаю, что в каждом конкретном случае надо придумывать, как обойтись без затратных операций, продумывать алгоритм решения.

Например, в данном случае, можно использовать динамический список (будут сложности в реализации + не так просто найти средний элемент), но зато нет проблем с удалением.

или можно использовать массив, слева и справа использовать две переменные для хранения границ, а в середине массива затирать элементы нулём.

А ещё можно попытаться построить алгоритм получения индекса следующего элемента так, чтобы "выпавшие" элементы уже не попадали в выборку. я не берусь утверждать, что это легко (да и вообще, что такая фукнция существует), но, если удасться её найти, то задача решена.

p.s.
Цитата:
Сообщение от KiLLtan Посмотреть сообщение
(1 ⩽ n ⩽ 105) — количество документов в списке.
тут явно число 10^5 (10 в 5-й степени)
так как и
ai (1 ⩽ ai ⩽ 10^9)
Serge_Bliznykov вне форума Ответить с цитированием
Старый 20.11.2018, 23:07   #3
Black Fregat
Программист
Участник клуба
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,772
По умолчанию

Тут просто нужно понять порядок обхода массива
Black Fregat вне форума Ответить с цитированием
Старый 21.11.2018, 10:17   #4
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Код:
    //m: array[1..100000] of Longint;
  s:='';
  k:=((n and 1) shl 1)-1;
  j:=(n+1) div 2;
  for i:=1 to n div 3 do begin
    s:=s+IntToStr(m[i])+' '+IntToStr(m[n-i+1])+' '+IntToStr(m[j])+' ';
    k:=-k;
    Inc(j,i*k);
  end;
  case n mod 3 of
  1: s:=s+IntToStr(m[j]);
  2: s:=s+IntToStr(m[(n div 3)+1])+' '+IntToStr(m[n-(n div 3)]);
  end;
Сделай свой IntToStr если нет в твоем паскале. Вместо накопления в строку можно сразу вывод в консоль сделать, тогда и IntToStr не нужно
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 21.11.2018, 10:37   #5
KiLLtan
Новичок
Джуниор
 
Регистрация: 20.11.2018
Сообщений: 2
По умолчанию

А можно полный код, если не трудно?
KiLLtan вне форума Ответить с цитированием
Старый 21.11.2018, 10:46   #6
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Низзя, какая тогда олимпиада ))
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
помогите с решением задач amn007 Помощь студентам 2 28.12.2016 09:36
составить программу ввода квадратной матрицы и печати в строку всех ее элементов в заданном ниже порядке следования Ben_Franklin Общие вопросы C/C++ 1 29.04.2016 04:38
Сколько элементов массива лежат в заданном интервале Faton 11 Общие вопросы C/C++ 1 18.11.2012 20:27
Создать программу замены четных элементов линейного массива на заданное число d MrJohanson Помощь студентам 3 26.01.2010 12:25