|
|
|
|
|
|
|
| 21 Денис Розимовский, 16 мая 2015 г. 17:33:24 |
| Так же можно решить через более элегантное BST (бинарное древо поиска).
|
|
|
| 22 Денис Розимовский, 16 мая 2015 г. 11:58:47 |
| Использовал структуру данных vector. При каждом новом солдате искал неким подобием бинарного поиска его место в этом векторе. Потом добавлял к финальном результату число равное количеству чисел, которые идут после j-того солдата.
|
|
|
| 23 Егоров Владимир Тимофеевич, 24 августа 2014 г. 8:35:51 |
| Гы, моё решение за 0,047 прошло.
|
|
|
| 24 Аман Жарасхан Алматович, 07 декабря 2012 г. 16:49:35 |
5 2
1 5 2 4 3 => (5 - 2) + (5 - 4) + (5 - 3) = 3 + 1 + 2 = 6
2 3 1 5 4 => (3 - 1) + (5 - 4) = 2 + 1 = 3
6 + 3 = 9
Почему ответ 7
Мне вообще не понятны ваши записи. На самом деле дело обстоит так: в первом ряду отжимаются 3 солдата: 2 солдата с ростом 2 и 4 отжимаются по 1 разу (т.к. всего один солдат слева от них выше их самих, это солдат с ростом 5), солдат с ростом 3 отжимается 2 раза, т.к. солдаты с ростом 4 и 5 выше его и находятся левее. Итого в первом ряду мы имеем 1+1+2=4 отжимания. Со вторым рядом еще проще, там отжимаются всего 2 солдата - это солдаты с ростом 1 (2 раза отжимается, т.к. слева солдаты с ростом 2 и 3) и ростом 4 (1 раз отжимается, т.к. только один солдат с ростом 5 левее). Итого во втором ряду мы имеем 1+2=3 отжиманий. В результате получаем, что сумма отжиманий по всем рядам равна 4+3=7. Что и требовалось объяснить :)
|
|
|
| 25 Глембоцкий Владислав Олегович, 22 апреля 2012 г. 1:56:34 |
Шефтелевич Павел Аркадьевич
У меня слияние прошло на 0,14 (все зависит от сервера)
|
|
|
| 26 Беляев Игорь, 14 июня 2011 г. 11:49:04 |
| 2Шефтелевич Павел: Ассимптотики одинаковые, а константы разные. У merge sort константа больше из-за того, что там приходится создавать временный массив, куда сливаются два подмассива.
|
|
|
| 27 Шефтелевич Павел Аркадьевич, 03 июня 2011 г. 19:49:22 |
| merge sort проходит последниq тест за 0.45-0.5c имея сложность n*(log n). для подсчета инверсий это оптимальная сложность, как же народ сдает быстрее чем за 0.15(сумматоры ведь тоже n*(log n))?
|
|
|
| 28 Ким Игорь, 13 мая 2011 г. 9:42:34 |
Опять-опять из-за медленности Java приходится переписывать код на Pascal.
Может, изменить ограничения для Java ?
|
|
|
| 29 Фурко Роман Владимирович, 26 февраля 2011 г. 13:12:14 |
| а причём тут сортировка??? я писал Дерево Фенвика!
|
|
|
| 30 Пересадин Илья, 09 февраля 2011 г. 0:14:00 |
| мучался, пытался за nk...так и не придумал, сдал слиянием, ну явно можно сорт подсчетом...
|
|
|
| 31 Менщиков Александр, 06 октября 2010 г. 17:11:52 |
Интересно какие еще есть методы кроме дерева и слияния?
Еще можно подсчетом, похоже на решение задачи Stars на тимусе.
|
|
|
| 32 Лизунов Михаил, 31 августа 2010 г. 15:55:10 |
mergesort?
это один из возможных способов решения задачи, далеко не самый короткий...
|
|
|
| 33 Ладик Артём, 28 августа 2010 г. 3:46:24 |
те кто решает бин. деревом, не сбалансированным, решение превращается в квадрат, но такого теста нет и решения проходят
Вряд ли чистый квадрат проходит. По крайней мере банальное решение или использование сортировки пузырьком не проходят. А то несбалансированное бинарное дерево все же не совсем квадрат. Только если спец. тесты создать. Это так же, как и быстрая сортировка может быть квадратом. Считаю, что если человек использовал дерево, то он уже молодец :)
|
|
|
| 34 Ладик Артём, 28 августа 2010 г. 3:43:43 |
Обновите тесты!!!
На этом сайте ее можно сдать и за квадрат
добавьте тесты похожие на этот
10000 20
1 2 3 4 5....
10000 9999 ....
......
|
|
|
| 35 КаБэ `15 кодит, 28 мая 2010 г. 12:36:23 |
то есть "вычеркивание минимального элемента последовательности, у которого инверсий ровно столько, сколько элеметов перед ним" здесь никак не пройдёт? тогда я сдаюсь(((
все свои учебники по алгебре перекопал, не нашёл иного более-менее программируегого метода подсчета числа инверсий. сдать бы эту задачу на Мэпл)))
|
|
|
| 36 Никитин Андрей Иванович, 20 февраля 2010 г. 12:02:35 |
Извините, но я считаю, что у вас во втором тесте ошибочка - 5 2, 4 3, 5 3,
3 1, 2 1, 5 4. Там будет 6! Или я не доконца понял?
Вы просто невнимательный, там в обоих рядах 5 4, а тут вы один раз только перечислили.
|
|
|
| 37 Самаль Александр Васильевич, 06 января 2010 г. 16:48:13 |
| Интересная задачка! Очень похожа на задачу 1090 с тимуса. И там, и тут решал с помощью сортировки слиянием.
|
|
|
| 38 Лалетин Вадим Викторович, 06 октября 2009 г. 19:56:25 |
| Отличная задача:)
|
|
|
| 39 Bogdanova Ira, 22 февраля 2009 г. 23:52:34 |
Как в первом примере получается 4?
3 3
1 2 3 - 0
2 1 3 - 1
3 2 1 - 2
Итого: 3, а почему в OUTPUT-е 4?
Вы просто считать не умеете. В последнем ряду 3, а не 2 приседания: 2й приседает 1 раз, т.к. слева 3ка, большая его, а 1ка приседает дважды, т.к. 2 человека выше. А как известно, 1+2=3, а 3<>2. Таким образом, получается, что 0+1+3=4. Что и требовалось доказать.
|
|
|
| 40 Кулик Сергей Дмитриевич, 07 февраля 2009 г. 15:22:37 |
какая сортировка??? тут же сумматор
тут есть по крайней мере 3 решения задачи, в том числе и сортировкой можно.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
