Форум » Задачи » 10-11 класс, задача 2 » Ответить
10-11 класс, задача 2
Заруднев А.Н.: число N - количество персонажей (1<=N<=100000). При описании массива в паскале var x:array[1..100000] of longint; появляется ошибка: Error 29:ordinal type expected; т.е. для хранения данных отводится 64 кб, меньше 100000 ячеек размером даже в 1 байт. Если можно написать алгоритм, не создавая таблицу, подскажите как?
Ответов - 14
hotsnr: Это возникает скорее всего если вы пишете в паскале для ДОСа. Там действительно на программу отводится 64 Кб. Но free pascal, который используют для проверки, компилирует программы под Windows и там позволяется намного больше памяти.
mrTropez: Из условия можно вытянуть, что все персонажи имеют разную силу(хотя это и не написано в технических данных) почему: результат можно предсказать всегда, кроме зеркального боя( когда это один персонаж). Значит если персонажи не одинаковые, то результат предсказать можно. А значит они должны иметь разную силу. В таком случае: очевидно, что когда сравниваем 2 элемента массива -> a1<a2<a3...<an то ai>aj только если i>j ai<aj если i<j ai=aj если i=j отсюда нужно сравнить : k-й с конца и L-й с начала значит надо сравнить n-k+1 и L. Как то так вроде)
Cawa222:
Pochekay: >Значит если персонажи не одинаковые, то результат предсказать можно. А если персонажи одинаковые, то результат предсказать нельзя, so what?
hotsnr: Результат предсказать можно. Только это будет уже за O(NlogN), а не за O(1).
Pochekay: Хоть он описал и правильный алгоритм, но его предположение о том, что в массиве сил персонажей все элементы уникальны - неверно, так как оно базируется на предположении о том, что задача гарантирует то, что результат боя предсказать можно. За О(1) эту задачу решить нельзя в принципе, так как хотя бы на то, чтобы прочитать входные данные нужно О(N) операций. А задачу вообще можно решить за O(N), так как фактически тут нужен L-ый минимум и K-ый максимум. Так что к чему ты это написал вообще не понятно, ми.
hotsnr: это не предположение - так написано в условии. и кстати, идет оценивание сложности алгоритма. ввод не включен в алгоритм.
MrMozg: В условии сказано только, что выбирают L разных персонажей, а не L персонажей с разной силой. И вообще не сказано о разности сил. Да и варианта ответа = не существует при Вашем допущении. А вот контрпример для Pochekay (про L-ый минимум и K-ый максимум). Я изначально отсортирую ввод: 1 2 3 3 3 4 4 L=4, K=5. По-вашему получается ответ = (ведь 3=3) А на само деле сравнивать нужно 2 и 3, ведь после того, как первому персонаж выбран, второй может получить персонажа только из набора: 1 2 3 3 4 4 А 5-ый максимальный тут 2.
Pochekay: MrMozg В условии не сказано, что они не могут выбрать одного и того же персонажа, более того, в условии наоборот подчеркивается, что это можно сделать:"Поэтому они легко могут предсказать результат любого сражения, кроме зеркального боя (когда оба выбирают одного и того же персонажа)", - так что не надо мне тут. hotsnr Даже если не включать ввод, то всё равно, тупое решение за O(NlogN) умное за О(N), как ты собираешься найти соответствующие числа за О(1) ничего не зная о структуре массива? Или что ты вообще хочешь доказать?
mrTropez: Pochekay В "умном" решении все что нужно сделать - сравнить числа L и (N-K+1). Массив нам просто не нужен.
Pochekay: mrTropez Ты опять опираешься на допущение, что силы всех персонажей различны, хотя оно ошибочно.
hotsnr: однако оно сработало
mrTropez: Pochekay 1)Задача на таком решении прошла 2)В чем его ошибочность? 3)Из условия : Все эти числа различны и лежат в диапозоне от 1 до 10^9
Pochekay: Прошла? Олег, ты шоле? Да, не увидел эту строчку, протупил.
полная версия страницы