Отправлено: 04.12.11 16:49. Заголовок: 10-11 класс, задача 2

число N - количество персонажей (1<=N<=100000). При описании массива в паскале
var x:array[1..100000] of longint;
появляется ошибка: Error 29:ordinal type expected; т.е. для хранения данных отводится 64 кб, меньше 100000 ячеек размером даже в 1 байт.
Если можно написать алгоритм, не создавая таблицу, подскажите как?

 Отправлено: 04.12.11 16:53. Заголовок: Это возникает скорее..

Это возникает скорее всего если вы пишете в паскале для ДОСа. Там действительно на программу отводится 64 Кб. Но free pascal, который используют для проверки, компилирует программы под Windows и там позволяется намного больше памяти.

 Отправлено: 04.12.11 18:54. Заголовок: Алгоритм

Из условия можно вытянуть, что все персонажи имеют разную силу(хотя это и не написано в технических данных)
почему:
результат можно предсказать всегда, кроме зеркального боя( когда это один персонаж).
Значит если персонажи не одинаковые, то результат предсказать можно. А значит они должны иметь разную силу.

В таком случае:
очевидно, что когда сравниваем 2 элемента массива -> a1<a2<a3...<an
то ai>aj только если i>j
ai<aj если i<j
ai=aj если i=j
отсюда нужно сравнить : k-й с конца и L-й с начала
значит надо сравнить n-k+1 и L.

Как то так вроде)

 Отправлено: 07.12.11 23:55. Заголовок: хех так и сделал:)

 Отправлено: 08.12.11 23:28. Заголовок: >Значит если пер..

>Значит если персонажи не одинаковые, то результат предсказать можно.

А если персонажи одинаковые, то результат предсказать нельзя, so what?

 Отправлено: 08.12.11 23:33. Заголовок: Результат предсказат..

Результат предсказать можно. Только это будет уже за O(NlogN), а не за O(1).

 Отправлено: 08.12.11 23:41. Заголовок: Хоть он описал и пра..

Хоть он описал и правильный алгоритм, но его предположение о том, что в массиве сил персонажей все элементы уникальны - неверно, так как оно базируется на предположении о том, что задача гарантирует то, что результат боя предсказать можно. За О(1) эту задачу решить нельзя в принципе, так как хотя бы на то, чтобы прочитать входные данные нужно О(N) операций. А задачу вообще можно решить за O(N), так как фактически тут нужен L-ый минимум и K-ый максимум.
Так что к чему ты это написал вообще не понятно, ми.

 Отправлено: 09.12.11 00:21. Заголовок: это не предположение..

это не предположение - так написано в условии. и кстати, идет оценивание сложности алгоритма. ввод не включен в алгоритм.

 Отправлено: 12.12.11 00:12. Заголовок: В условии сказано то..

В условии сказано только, что выбирают 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.

 Отправлено: 12.12.11 15:19. Заголовок: MrMozg В условии не..

MrMozg
В условии не сказано, что они не могут выбрать одного и того же персонажа, более того, в условии наоборот подчеркивается, что это можно сделать:"Поэтому они легко могут предсказать результат любого сражения, кроме зеркального боя (когда оба выбирают одного и того же персонажа)", - так что не надо мне тут.
hotsnr
Даже если не включать ввод, то всё равно, тупое решение за O(NlogN) умное за О(N), как ты собираешься найти соответствующие числа за О(1) ничего не зная о структуре массива? Или что ты вообще хочешь доказать?

 Отправлено: 12.12.11 21:52. Заголовок: Pochekay В "умн..

Pochekay
В "умном" решении все что нужно сделать - сравнить числа L и (N-K+1).
Массив нам просто не нужен.

 Отправлено: 12.12.11 23:39. Заголовок: mrTropez Ты опять о..

mrTropez
Ты опять опираешься на допущение, что силы всех персонажей различны, хотя оно ошибочно.

 Отправлено: 13.12.11 21:11. Заголовок: однако оно сработало..

однако оно сработало

 Отправлено: 13.12.11 21:46. Заголовок: Однако

Pochekay
1)Задача на таком решении прошла
2)В чем его ошибочность?
3)Из условия :
Все эти числа различны и лежат в диапозоне от 1 до 10^9

 Отправлено: 13.12.11 22:08. Заголовок: Прошла? Олег, ты шол..

Прошла? Олег, ты шоле? Да, не увидел эту строчку, протупил.