crchemistвыше весь код написан, если алгоритм фиговый - напиши в чем
програма тестується на spoj.pl - там скоріше за все нема ніяких бібліотек - чистий пітон - алгоритм напевне фіговий а не бібліотеки
#!/usr/bin/env python
import sys
range_line = range(1000)
res = []
for i in range_line[:input()]:
triangle = []
for j in range_line[:input()]:
line = map(int, sys.stdin.readline().split())
if triangle:
lst_ln = triangle[-1]
line = map(lambda z:line[z] + max(lst_ln[z - 1 if z else z: z + 1]), range_line[:len(line)])
triangle.append(line)
res.append(max(triangle[-1]))
for i in res:
sys.stdout.write(str(i) + '\n')
crchemistя не понимаю по-украински, сорри :)
ага - алгоритм ніби нормальний - я так само колись робив на http://projecteuler.net/ Щодо оптимізації: ти спочатку зчитуєш всі дані в масив а потім рахуєш. Думаю скоріше буде зчитувати трикутник по одній лінії і ту лінію додавати одразу в результат. Плюс використовуй цикл while замість for - він мав би бути набагато швидшим. взагалі мені здається що цикл for буде набагато повільніший map - можна замість for вліпити map. Пізніше кину код
crchemistпо поводу алгоритма - он немного нерабочий, так как input идет с первой строки, а не наоборот
на 10секундах на 0.5 сек швидший за твій#!/usr/bin/env python
import sys
range_line = range(1000)
res = []
for i in range_line[:input()]:
triangle = []
for j in range_line[:input()]:
line = map(int, sys.stdin.readline().split())
if triangle:
lst_ln = triangle[-1]
line = map(lambda z:line[z] + max(lst_ln[z - 1 if z else z: z + 1]), range_line[:len(line)])
triangle.append(line)
res.append(max(triangle[-1]))
for i in res:
sys.stdout.write(str(i) + '\n')
crchemistнашел переводчик, по поводу while, я тоже так думал, но когда сделал - разницы в результате не заметил
ага - алгоритм ніби нормальний - я так само колись робив на http://projecteuler.net/ Щодо оптимізації: ти спочатку зчитуєш всі дані в масив а потім рахуєш. Думаю скоріше буде зчитувати трикутник по одній лінії і ту лінію додавати одразу в результат. Плюс використовуй цикл while замість for - він мав би бути набагато швидшим. взагалі мені здається що цикл for буде набагато повільніший map - можна замість for вліпити map. Пізніше кину код
def f(x):
return x*2
def map_f(n):
map(f, range(n))
def for_f(n):
[f(x) for x in range(n)]
def main():
n = 100000
map_f(n)
for_f(n)
if __name__ == '__main__':
import profile, pstats
profile.run('main()', 'result.prof')
pstats.Stats('result.prof').strip_dirs().sort_stats(-1).print_stats()
cybergrindда на с++ уже решил эту проблему, просто мне интересно как можно было добиться такого же результата на питоне
мое имхо - если настолько критично быстродействие - переписать все на С или плюсы
shizaда, спасибо, я его и имел в виду, просто зачем-то буст сюда приплел :)
boost - это набор сишный билиотек на все случаи жизни.
Есть для питона ускоритель. Называется Psyco (http://psyco.sourceforge.net/).