|
|
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
ой, Вадим, даж не знаю что сказать Твой код у меня скомпилился и отработал на отлично. На сподже ограничения по памяти нет (= 256 М) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.07.2009, 18:44:49 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
RT183.1, Можешь сравнить по времени со своим? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.07.2009, 18:55:20 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
[quot RT183.1 На сподже ограничения по памяти нет (= 256 М)[/quot] Ну, у меня максимум будет размер лонга (64 бита - 8 байт) * 1000000 = 8 Мб - "ни о чём" Почему по скорости не проходит - хз, заполнение массива идёт очень быстро, дальнейшие расчёты - минимальны. Почему не проходит по времени - загадка. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.07.2009, 18:59:33 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
у них машинки древние -- PIII 750MHz Так сложилось исторически и менять их нельзя, потому что побьются все рейтинги по скорости, а кто будет заново ри-джаджить миллионы кодов? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.07.2009, 19:07:39 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
RT183.1, о, а если оно сдохнет? Что скажешь по скорости моего алгоритма? Где может быть затык? Как тебе решение в общем? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.07.2009, 19:12:30 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
дык у них в запасе этих машинок вагон :) Насчет твоего решения..... ну мне так лениво возвращаться к этой таске..... Ты уж прости. Ты просто сам подумай ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.07.2009, 19:29:53 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
RT183.1, да я не прошу глубокого анализа :-) Просто, если видишь явный затык (хотя,где тут ему спрятаться) - скажи... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.07.2009, 19:33:16 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
Явного затыка не вижу :) Херово мне просто сейчас, на душе ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.07.2009, 19:52:13 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
RT183.1, опять потравился? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.07.2009, 19:53:18 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
VadimPanovRT183.1, опять потравился? опять НО отравление -- это следствие, а не причина :) А вот что делать с "причиной" -- ХЗ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.07.2009, 20:33:13 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
RT183.1> Мое решение на python самое тяжеловесное по памяти среди остальных питоноводов получилось, хыхы. Там в ранк-листе первые 10-20 такие монстрюки -- "оставь надежду всяк сюда входящий". Получилось с натягом 19-е место. Разница по времени с лидером раза в 2. RT183.1> Я как-то обменялся 4-6 письмами с юзером SPIDY из Индии (он спрашивал у меня как сделать какую-то задачу, не помню какую). Он даже не знал что scanf работает быстрее cin. Но объективно он намного лучший прогер чем я. И вообще, индийцы молодцы. Для меня это в основном развлекуха. Просто жизнь заставила заняться этой хренью. Успехи в спортивном программировании и навыки разработки по мало связаны. На старой работе видел хорошего кодера, филолога по образованию. Сам сейчас балуюсь олимпиадными задачками, чтобы остаток знаний после универа не растерять :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.07.2009, 22:48:41 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
VadimPanovКстати, попытка задать размерность массива (фактически - ограничив максимальную размерность треугольника в 50 тыс. вместо миллиона) - провалилась, :-) программа выдала выход индекса за пределы массива, что означает, что они реально скармливают на вход значения больше этих 50 тыс... Ваша программа осилит эту задачу для N=12345678901234567890123456789012345678901234567890 ? 470419093088414443136679010148821688843634550791843540876783593536197809292222678522457652871506814637418646167210126039437869991452475862419816785 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.07.2009, 22:53:29 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
> Получилось с натягом 19-е место. Разница по времени с лидером раза в 2. Я ващет имел в виду общий ранк-лист, а не конкретно по этой задаче. У меня кажется только в одной задаче первое место, уже много лет: http://www.spoj.pl/ranks/ALIENS/ Но я в нее угрохал очень много писанины. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.07.2009, 06:07:04 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
Кстати, те же много лет для меня остается загадкой почему все решения на первой странице - на ссылке выше -- сделаны на паскале. Я в принципе тоже содрал из тырнета чужой код на С++, переписал его на Паскале, но я его сильно модифицировал. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.07.2009, 06:41:01 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
me_dvedVadimPanovКстати, попытка задать размерность массива (фактически - ограничив максимальную размерность треугольника в 50 тыс. вместо миллиона) - провалилась, :-) программа выдала выход индекса за пределы массива, что означает, что они реально скармливают на вход значения больше этих 50 тыс... Ваша программа осилит эту задачу для N=12345678901234567890123456789012345678901234567890 ? 470419093088414443136679010148821688843634550791843540876783593536197809292222678522457652871506814637418646167210126039437869991452475862419816785 Это что, реальный ответ? Как посчитан? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.07.2009, 07:48:31 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
VadimPanovme_dvedVadimPanovКстати, попытка задать размерность массива (фактически - ограничив максимальную размерность треугольника в 50 тыс. вместо миллиона) - провалилась, :-) программа выдала выход индекса за пределы массива, что означает, что они реально скармливают на вход значения больше этих 50 тыс... Ваша программа осилит эту задачу для N=12345678901234567890123456789012345678901234567890 ? 470419093088414443136679010148821688843634550791843540876783593536197809292222678522457652871506814637418646167210126039437869991452475862419816785 Это что, реальный ответ? Как посчитан? плин конечно же реальный! Это же Питон, в нем нет ограничения на длину целых чисел ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.07.2009, 07:58:32 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
RT183.1> Получилось с натягом 19-е место. Разница по времени с лидером раза в 2. Я ващет имел в виду общий ранк-лист, а не конкретно по этой задаче. У меня кажется только в одной задаче первое место, уже много лет: http://www.spoj.pl/ranks/ALIENS/ Но я в нее угрохал очень много писанины. Если общий, то да... Не среднестатистические умы. По крайней мере, осилили столько задач. RT183.1Кстати, те же много лет для меня остается загадкой почему все решения на первой странице - на ссылке выше -- сделаны на паскале. Странно, почему именно паскаль. Чистый С (не C++) должен шустрее работать. Быстрее только со вставками на asm'е. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.07.2009, 14:41:40 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
1. Что поразительно они (топы) лупят эти задачи сотнями на многих и разных контестерах, не только на сподже (Сподж относительно молодой контестер). 2. asm я уж точно не использовал в ALIENS -- просто добавил солидную предобработку Кстати, как часть контестерного этикета использовать асм считается дурным тоном и не приветствуется ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.07.2009, 15:56:54 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
RT183.1ага конечно могу (код ниже) Я смутно помню что пытался найти точную формулу, но не смог. Всё пытаюсь избавиться от дурацкой привычки всё решать "в голове", вместо того чтобы взять бумагу и ручку и подумать по-настоящему. Код: plaintext Твой код для треугольников, на паскале, прекрасно у них работает, а ОН ЖЕ, переведённый с паскаля на С, тоже даёт time limit exceeded!!! И как это понимать? Интерпретатор стал быстрее компилятора или, может, дело в размерности переменных? Типа, какая-то нестыковка в размерности переменных и всё зависает, а система снимает задачу по превышению времени? Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.07.2009, 17:29:25 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
чудеса... бум смотреть ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.07.2009, 17:42:02 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
All answers will fit within the range of a 64-bit integer где у меня в паскале инт64 в Си должно быть long long и printf("%lld\n", ...) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.07.2009, 18:20:09 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
RT183.1, Щас вот сравнил работу твоего кода на паскале для треугольников со своим кодом (перевёл с С на паскаль), скомпилированно всё было в дельфях. Твой код работает значительно быстрее. А вот за счёт чего - не пойму. Твой код: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. Мой код: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. Отчего же тогда такая разница в производительности? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.07.2009, 14:14:40 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
Так, не понял... Отчего Код: plaintext выводит мне Код: plaintext ???????(?) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.07.2009, 17:34:14 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
VadimPanov, 1) у тебя на одну проверку больше (условный переход обычно замедляет расчеты) 2) заметил еще {$I-, Q-, R-, S-}, попробуй скомпилится с такими же флагами (это отключение кучи скрытого кода - проверки при расчетах, операциях ввода-вывода...) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.07.2009, 18:18:33 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=36114332&tid=1344339]: |
0ms |
get settings: |
8ms |
get forum list: |
21ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
196ms |
get topic data: |
10ms |
get forum data: |
3ms |
get page messages: |
86ms |
get tp. blocked users: |
1ms |
| others: | 196ms |
| total: | 527ms |

| 0 / 0 |
