|
|
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
вот примерчик из ФАКа одного китайского контестера: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.07.2009, 18:51:54 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
VadimPanovТак, не понял... Отчего Код: plaintext выводит мне Код: plaintext ???????(?)компилятор работает только со знаковым 32-битным целым, попробуй явно привести к беззнаковому или 64-битному ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.07.2009, 19:00:35 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
это тоже не помогает ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.07.2009, 19:12:55 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
сейчас глянул на их форуме: http://www.spoj.pl/forum/viewtopic.php?f=3&t=5789 Это же надо было не полениться стругануть фибоначчиеву кучу для этой хрени (shortest path), ыхыхыхых Код: 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. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. 163. 164. 165. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. 180. 181. 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193. 194. 195. 196. 197. 198. 199. 200. 201. 202. 203. 204. 205. 206. 207. 208. 209. 210. 211. 212. 213. 214. 215. 216. 217. 218. 219. 220. 221. 222. 223. 224. 225. 226. 227. 228. 229. 230. 231. 232. 233. 234. 235. 236. 237. 238. 239. 240. 241. 242. 243. 244. 245. 246. 247. 248. 249. 250. 251. 252. 253. 254. 255. 256. 257. 258. 259. 260. 261. 262. 263. 264. 265. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.07.2009, 19:30:19 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
vinoVadimPanov, 1) у тебя на одну проверку больше (условный переход обычно замедляет расчеты) Твой алгоритм на файле с 99999 входными значениями отрабатывает меньше, чем за секунду, а мой - больше, чем за минуту! Отчего такая разница?!!! Давай посмотрим ещё раз циклы (всё остальное, по сути - одинаковое, заполнение массива у меня занимает меньше секунды): Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. происходит следующее: 1 действие: присвоение 2 действие: чтение элемента массива, 4 сложения, 2 умножения, 1 деление, запись элемента 3 действие: проверка с переходом 4 действие: чтение элемента массива, 2 сложения, 1 умножение, 1 деление, запись элемента Итого на итерацию цикла: 1 присвоение, 2 чтения и 2 записи элемента массива, 6 сложений, 3 умножения, 2 деления Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 1 действие: 2 сложения, 1 присвоение 2 действие: проверка, 1 чтение элемента массива, 1 сложение 3 действие: 2 сложения, 1 умножение, 1 присвоение 2 действие: проверка, 1 чтение элемента массива, 1 сложение Итого на итерацию цикла: 4 присвоения, 2 чтения элемента массива, 6 сложений, 1 умножение Видно, что мои вычисления - проще. Отчего такая огромная разница - я не понимаю... Можно, кстати, мой алгоритм и так записать (не думаю, что сильно спасёт): Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. Будет на пару сложений меньше... vino 2) заметил еще {$I-, Q-, R-, S-}, попробуй скомпилится с такими же флагами (это отключение кучи скрытого кода - проверки при расчетах, операциях ввода-вывода...) Оба варианта компилировал в пятых дельфях в одинаковых условиях. Может, конечно, это как-то и влияет, но не настолько же. Скажи, что каждый параметр означает, я поставлю те же дельфозные. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.07.2009, 09:08:24 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
VadimPanov, А разница то здесь Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.07.2009, 09:20:29 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
VadimPanovзаполнение массива у меня занимает меньше секунды А МОЖЕТ ОНО У НИХ ТАМ ЗАНИМАЕТ МНОГО ВРЕМЕНИ??? Хз, чем они там компилят и на какой платформе запускают... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.07.2009, 09:26:19 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
автор В каждой итерации цикла от 4-х до N*10^6 (т.е. тот факт, что от 4-х, а не от 1 - несущественен) Каждая итерация не от 4-х, присмотрись внимательно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.07.2009, 09:27:07 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
clihlt, Да, точно, не заметил сразу... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.07.2009, 12:12:53 |
|
||
|
Каким алгоритмом можно заполнить все озёра рельефа водой?
|
|||
|---|---|---|---|
|
#18+
VadimPanov Твой код для треугольников, на паскале, прекрасно у них работает, а ОН ЖЕ, переведённый с паскаля на С, тоже даёт time limit exceeded!!! И как это понимать? RT183.1чудеса... бум смотреть Не разбирался с этим? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.07.2009, 12:18:09 |
|
||
|
|

start [/forum/topic.php?fid=16&startmsg=36118895&tid=1344339]: |
0ms |
get settings: |
9ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
212ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
54ms |
get tp. blocked users: |
1ms |
| others: | 220ms |
| total: | 528ms |

| 0 / 0 |
