|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
20.11.2018, 19:28 | #1 |
Новичок
Джуниор
Регистрация: 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] Эти поручения обрабатываются и дальше по такому же порядку. |
20.11.2018, 22:10 | #2 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
удалять не рентабельно. Задача явно олимпиадная, а значит имеет ограничение по времени.
я не мастер решать олимпиадные задачи. Вполне возможно, что придёт настоящий олимпиец и расскажет о том, как лучше решить эту задачу. Думаю, что в каждом конкретном случае надо придумывать, как обойтись без затратных операций, продумывать алгоритм решения. Например, в данном случае, можно использовать динамический список (будут сложности в реализации + не так просто найти средний элемент), но зато нет проблем с удалением. или можно использовать массив, слева и справа использовать две переменные для хранения границ, а в середине массива затирать элементы нулём. А ещё можно попытаться построить алгоритм получения индекса следующего элемента так, чтобы "выпавшие" элементы уже не попадали в выборку. я не берусь утверждать, что это легко (да и вообще, что такая фукнция существует), но, если удасться её найти, то задача решена. p.s. тут явно число 10^5 (10 в 5-й степени) так как и ai (1 ⩽ ai ⩽ 10^9) |
20.11.2018, 23:07 | #3 |
Программист
Участник клуба
Регистрация: 23.06.2009
Сообщений: 1,772
|
Тут просто нужно понять порядок обхода массива
|
21.11.2018, 10:17 | #4 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Код:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
21.11.2018, 10:37 | #5 |
Новичок
Джуниор
Регистрация: 20.11.2018
Сообщений: 2
|
А можно полный код, если не трудно?
|
21.11.2018, 10:46 | #6 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Низзя, какая тогда олимпиада ))
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
помогите с решением задач | 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 |