On Sat, 9 Jan 2010, Alex Kapranoff wrote:
Всем привет!
Вроде простая совсем задачка: https://www.spoj.pl/problems/SUMITR/
А поди ж ты, на самом плохом тесткейсе в 2 секунды на довольно мощной
машине уложить не могу :(
На Си хватает и половины секунды. В комментах пишут, что и Питон
справляется. Хочет кто-нибудь поиграться?
Моё решение (до сжатия кода, понятно): http://ideone.com/alWtxXxt
Плохой тесткейс: http://dl.dropbox.com/u/360558/input_big.txt.gz
(распакуется в 14 мег)
$cat input_big.txt | LC_ALL=C time perl -le 'while(<STDIN>){ chomp; split("
",$_);}'
1.29user 0.00system 0:01.36elapsed 95%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+464minor)pagefaults 0swaps
У меня не самая мощная машина, но на вычисления остаётся ~ 0.7 сек.
С другой стороны:
$cat input_big.txt | time perl -le 'sysread(STDIN,$dd, 100_000_000); foreach
(split("\n",$dd)){ split(" ", $_);}; print length($dd);'
14853005
1.59user 0.04system 0:01.67elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+8733minor)pagefaults 0swaps
Т.е. ещё хуже.
Для решения input_big.txt нужно выполнить как минимум
1000*99*(99+1)/2 = 4950000 сложений.
$time perl -le 'for(1 .. 4950000) { $a = $b + 1;}'
1.19user 0.00system 0:01.20elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+480minor)pagefaults 0swaps
Подозреваю, что на моём mobile core2 без шансов.
--
Moscow.pm mailing list
[email protected] | http://moscow.pm.org
