The_Ice

Ну как успехи? Тоже интересует возможность подобной "экскурсии". Неужто обсерваторию БГУ не интересует такой дополнительный доход?

Долго не мог оторваться от фото участницы №8, но когда увидел фото под номером 13, сомнений не осталось

Посмотрите в сторону "Wiki on a stick" http://my-box-371.blogspot.com/2010/03/wiki-on-stick-woas.html , если, конечно, Вы солидарны с форматом вики

Ох уж и намучался я с решением. Судя по всему, spoj.pl тоже меня опрокинул. Твою прогу на С++ принял, а все мои на хаскелл отверг по TLE, я уже было решил плюнуть на хаскелл, коль я не умею писать на нем быстрый код, но, решил сравнить результат прог на своих данных и был и удивлен и разочарован одновременно: Итоговая версия, на которой я решил прекратить попытки аппрува на spoj.pl, работает со строками и не проверяет, является ли число палиндромом (аналог твоей на С++) и выглядит так: import Data.Char import qualified Data.ByteString.Char8 as B next_num:: B.ByteString-> B.ByteString next_num str | B.null str = let !ret = B.pack "1" in ret | otherwise = let !last_c = digitToInt $! B.last str !headed = str `seq` B.init str in if last_c < 9 then let !ret = B.snoc headed $! intToDigit (last_c+1) in ret else let !inc_headed = next_num headed !ret = B.snoc inc_headed '0' in ret next_polindrome:: B.ByteString-> B.ByteString next_polindrome current = let !len = B.length current !half_len = (len `div` 2) + if odd len then 1 else 0 !half = B.take half_len current !rhalf = B.reverse half !tail_ = B.drop half_len current !even_len = if (rhalf > tail_) then let !ret = half `B.append` rhalf in ret else let !inc_half = next_num half !inc_rhalf = if (B.length inc_half > B.length half) then B.tail $! B.reverse inc_half else B.reverse inc_half !ret = inc_half `B.append` inc_rhalf in ret !half_less = B.init half !rhalf_less = B.reverse half_less !odd_len = if (rhalf_less > tail_) then let !ret = half `B.append` (B.reverse half_less) in ret else let !inc_half_raw = next_num half !inc_half = if B.length inc_half_raw > B.length half then B.init inc_half_raw else inc_half_raw !inc_rhalf = B.reverse $ B.init inc_half_raw !ret = inc_half `B.append` inc_rhalf in ret in if even len then even_len else odd_len main = do cnt' <- getLine let !cnt = (read cnt')::Int input 0 = return () input n = do line <- B.getLine let !dropped = B.dropWhile (=='0') line !next = next_polindrome dropped B.putStrLn next input (n-1) input cntmodule Main where Входные данные генерились просто: Prelude> let nums = max_n:[1..max_n] Prelude> let content = unlines $ map show nums Prelude> writeFile "data" content Prelude> let max_n = 100000 Т.е. первая строка - число 100000, а все остальные - это числа от 1 до 100000 включительно Программы собирались такими командами: ghc --make ./Palindrome.hs -o ./pali g++ -O3 ./Test.cpp -o ./test The Glorious Glasgow Haskell Compilation System, version 6.12.1 ice@desktop:~/devel/spoj/palindrom$ g++ --version g++ (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5ice@desktop:~/devel/spoj/palindrom$ ghc --version А запускались такими: $ cat ./data | ./pali > ./pali_out $ cat ./data | ./test > ./test_out Т.е. вывод программы на haskell писался в pali_out, а твоей на С++ - в test_out и diff различий не находил ice@desktop:~/devel/spoj/palindrom$ echo $? 0 ice@desktop:~/devel/spoj/palindrom$ diff ./pali_out ./test_out Но! Самое интересное показали вот результаты вот этих команд: ice@desktop:~/devel/spoj/palindrom$ time `cat ./data | ./test > /dev/null` real 0m37.444s user 0m37.430s sys 0m0.000s ice@desktop:~/devel/spoj/palindrom$ time `cat ./data | ./pali > /dev/null` real 0m2.647s user 0m2.640s sys 0m0.000s Тут я начал сильно сомневаться, но вот это говорит о том, что все правильно: real 0m38.103s user 0m38.080s sys 0m0.010s ice@desktop:~/devel/spoj/palindrom$ time `cat ./data | ./pali > ./pali_out` real 0m2.596s user 0m2.580s sys 0m0.010s ice@desktop:~/devel/spoj/palindrom$ diff ./pali_out ./test_out ice@desktop:~/devel/spoj/palindrom$ echo $? 0 ice@desktop:~/devel/spoj/palindrom$ time `cat ./data | ./test > ./test_out` Для того, кто на протяжении двух дней безуспешно пытался получить аппрув решения, укладывающееся в лимит времени 9 секунд и так его и не получив, это было невероятно. Оставалось только думать, что ситуация меняется при обработке чисел с 1_000_000 цифр, что и требовалось проверить, поэтому составил набор данных с БОЛЬШИМИ числами: Prelude> let min_n = 10 ^ 1000000 Prelude> let max_n = min_n + 20 Prelude> let nums = 20:[min_n .. max_n] Prelude> let content = unlines $ map show nums Prelude> writeFile "huge" content Prelude> Leaving GHCi. Удалил старые результаты, на всякий пожарный: ice@desktop:~/devel/spoj/palindrom$ rm out ice@desktop:~/devel/spoj/palindrom$ rm out1 И, момент истины: ice@desktop:~/devel/spoj/palindrom$ time `cat ./huge | ./pali > ./pali_out` real 0m0.667s user 0m0.410s sys 0m0.290s ice@desktop:~/devel/spoj/palindrom$ time `cat ./huge | ./test > ./test_out` real 0m1.351s user 0m1.010s sys 0m0.370s И, вот с таким вот выражением лица , я осознаю, что за это время я успел и кэш прикрутить и многопоточность и все четно - я по-прежнему получаю time limit exceeded))) Более того, выявился 1 баг: Учитывая, что в файле должно содержаться 20 чисел, состоящих из 1000000 цифр + 20 символов перевода строки, создается впечатление, что программа на С++ содержит багу (: строка char s[MAXLEN+1], l[(MAXLEN/2) + 1], rl[(MAXLEN/2)+1]; решает Ушел на форум spoj.pl со злым выражением лица) UPD: Интересно то, что ленивая версия программы работает еще быстрее: import Data.Char import qualified Data.ByteString.Lazy.Char8 as B next_num:: B.ByteString-> B.ByteString next_num str | B.null str = B.pack "1" | otherwise = let last_c = digitToInt $ B.last str headed = str `seq` B.init str in if last_c < 9 then B.snoc headed $ intToDigit (last_c+1) else let inc_headed = next_num headed in B.snoc inc_headed '0' next_polindrome:: B.ByteString-> B.ByteString next_polindrome current = let len = B.length current half_len = (len `div` 2) + if odd len then 1 else 0 half = B.take half_len current rhalf = B.reverse half tail_ = B.drop half_len current even_len = if (rhalf > tail_) then let ret = half `B.append` rhalf in ret else let inc_half = next_num half inc_rhalf = if (B.length inc_half > B.length half) then B.tail $ B.reverse inc_half else B.reverse inc_half in inc_half `B.append` inc_rhalf half_less = B.init half rhalf_less = B.reverse half_less odd_len = if (rhalf_less > tail_) then half `B.append` (B.reverse half_less) else let inc_half_raw = next_num half inc_half = if B.length inc_half_raw > B.length half then B.init inc_half_raw else inc_half_raw inc_rhalf = B.reverse $ B.init inc_half_raw in inc_half `B.append` inc_rhalf in if even len then even_len else odd_len main = do cnt' <- getLine let cnt = (read cnt')::Int content <- B.getContents let lines = take cnt $ B.lines content output [] = return () output (l:ls) = do let dropped = B.dropWhile (=='0') l B.putStrLn $ next_polindrome dropped output ls output lines module Main where С такими результатами на тех же данных data: real 0m0.964s user 0m0.930s sys 0m0.020s $ time `cat ./data | ./pali_l1> /dev/null` Данные по времени на списке 800 больших чисел: Prelude> let max_n = min_n + 800 Prelude> let nums = 800:[min_n .. max_n] Prelude> let foo num = do{ appendFile "huge" $! (show num)++"\n"} Prelude> mapM_ foo numsPrelude> let min_n = 10 ^ 1000000 real 0m7.150s user 0m5.470s sys 0m3.230s ice@desktop:~/devel/spoj/palindrom$ time `cat ./huge | ./test> /dev/null` real 0m40.444s user 0m38.760s sys 0m4.580s ice@desktop:~/devel/spoj/palindrom$ time `cat ./huge | ./pali> /dev/null` real 0m19.001s user 0m17.010s sys 0m4.350s ice@desktop:~/devel/spoj/palindrom$ time `cat ./huge | ./pali_l1> /dev/null` pali - это строгая версия, pali_l1 - ленивая. А я всегда старался избавиться от ленивости *28 PS: извиняюсь за столь длинный пост - просто я немного озадачен результатом (:

Разговор заставил меня вернуться к spoj.pl и я вспомнил что меня бесит в решении на haskell - это сложность уложиться в лимит времени Вроде, задача не сложная: The Next Palindrome Problem code: PALIN A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros. Input The first line contains integer t, the number of test cases. Integers K are given in the next t lines. Output For each K, output the smallest palindrome larger than K. Example Input: 2 808 2133 Output: 818 2222 Time limit: 9s Source limit: 50000B Пишем первую версию программки, получаем "time limit exceeded", вторую - с тем же результатом, ... приходим к четвертой версии с использованием мемоизации и принудительной строгости примерно такого вида: module Main where {-- смысл кэша: имеем Map (число, следующий палиндром) на каждой итерации смотрим: есть ли в мапе число <= нужного, но палиндром которого больше данного нам числа, если нет - вычисляем, если есть - возвращаем уже вычисленный палиндром -} import System.IO import qualified Data.Map as IMap import Control.Monad.State type PolMap = IMap.Map Int Int type PolS = State PolMap Int tens = [ 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000] -- "рабочая" рекурсивная функция функции is_palindrome _is_pali:: Int -> Int -> Bool _is_pali x n | x < 10 = True -- однозначное число - это палиндром | otherwise = x`seq`n`seq` let last_digit = x `mod` 10 first_digit = div x $! ( tens !! n) next = tailed `div` 10 tailed = mod x $! (first_digit * (tens !! n)) in if last_digit /= first_digit then False -- если первая цифра /= последней - значит не -- палиндром else if n < 3 then True -- если число 2х/3х значное, -- то нет смысла смотреть дальше else next `seq` _is_pali next $! (n-2) -- возвращает True, если переданное число - палиндром is_palindrome:: Int-> Bool is_palindrome x = x `seq` let fcnt = (fromIntegral x)::Float cnt = floor $! logBase 10 fcnt in _is_pali x $! cnt -- собственно - бэк-энд для нахождения следующего палиндрома next_palindrome:: Int-> Int next_palindrome x = if is_palindrome x then x else next_palindrome $! x+1 -- next_palindrome с использованием кэширования вычислинных "следующих" -- палиндромов mem_next_palindrom::Int-> PolS mem_next_palindrom num = do cache <- get -- найдем максимальный вычисленный палиндром let (max_key, max_pali) = case IMap.null cache of True-> (1,2) _ -> IMap.findMax cache if num >= max_pali then do -- если переданное число больше сохраненного палиндрома, то нет -- смысла искать в кэше let next_pali = next_palindrome num put $! IMap.insert num next_pali cache -- сохраняем в кэш return next_pali else do -- функция поиска подхдящей пары в кэше: -- key должен быть меньше или равен переданному числу, а value > его let filter_foo k v = k `seq` v `seq` if k <= num && v > num then True else False filtered = IMap.toList $! IMap.filterWithKey filter_foo cache case filtered of []-> do -- если подходящих значений не найденно - вычисляем и -- добавляем в кэш let next_pali = next_palindrome num put $! IMap.insert num next_pali cache return next_pali ((_,next_pali):_) -> return next_pali -- ура, оптимизация! -- efficient next_palindrome - бэк-энд для next_palindrome с использованием кэша eff_next_palindrome:: Int-> PolMap-> Int eff_next_palindrome num cache = evalState (mem_next_palindrom num) cache main = do cnt' <- getLine let cnt = (read cnt')::Int cache::PolMap cache = IMap.empty input 0 = return () input n = do line <- getLine let some = (read line):: Int print $! eff_next_palindrome (some + 1) cache input $! (n-1) input cnt но, по-прежнему получаем time limit exceeded И приходим к выводу, что я просто использую не самый быстрый алгоритм решения о том, является ли число палиндромом *26 В итоге: --ЧСВ и засыпаю в дурацком настроении))) Конечно, по-хорошему, нужно было бы переписать на Сях и сравнить результат, но мне лень гг

Не, не пробовал) Можно попробовать, хотя я уверен, что буду на дне турнирной таблицы - навыки растерял уже (: Просто вспомнилась фраза про хаскелл из твоего блога, вот и решил поинтересоваться о том, как дела у тебя с ним обстоят

Да, что-то после знакомства с ФЯПами, на C как то писать стало лень))) Пытался на codeforces на нем писать, но, постоянно упирался в ограничение на размер выходного файла, а вот на http://www.spoj.pl/ ограничение не такое суровое (: Хотя, довольно продолжительное время, забиваю я на программирование

Пробежался по тексту и... [off] 0xDEADBEEF haskell ковыряешь или забросил? (: [/off]

recordMyDesktop

Отсутствие подробностей - традиционная черта топиков о фантоме, не зря же её так назвали...

А в наших школах "Школьный Линукс" внедряют? Кто в теме - прокомментируйте (:

на самом деле, ничего интересного...

код в студию, надеюсь, в нем не будет GlobalAlloc'ов и т.п. могу предложить позапускать несколько раз программульку типо: #define SZ (2 << 20) * 100 int main() { char * p = new char [SZ]; return 0; } и посмотреть сколько мусора от нее останется. судя по всему - она

С правилами хорошего тона я согласен, но в винде ресурсы завершенного процесса тоже освобождаются...

, а если не мучатся, выделить 100 метров и завершить выполнение без освобождения? Будем делать ставки? (: