Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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

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

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

У Жарасхана есть 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, 23:10   #2
Serge_Bliznykov
МегаМодератор
СуперМодератор
 
Регистрация: 09.01.2008
Сообщений: 24,601
Репутация: 5352
По умолчанию

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

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

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

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

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

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

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

Тут просто нужно понять порядок обхода массива
Black Fregat вне форума   Ответить с цитированием
Старый 21.11.2018, 11:17   #4
Аватар
Модератор
Заслуженный модератор
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Адрес: Северодонецк.ua
Сообщений: 18,077
Репутация: 6385
По умолчанию

Код:

    //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, 11:37   #5
KiLLtan
Новичок
 
Регистрация: 20.11.2018
Сообщений: 2
Репутация: 10
По умолчанию

А можно полный код, если не трудно?
KiLLtan вне форума   Ответить с цитированием
Старый 21.11.2018, 11:46   #6
Аватар
Модератор
Заслуженный модератор
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Адрес: Северодонецк.ua
Сообщений: 18,077
Репутация: 6385
По умолчанию

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

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

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


15:52.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru