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 cnt

module 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.5

ice@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 баг:

-rw-r--r-- 1 ice ice 20000040 2011-01-30 00:04 pali_out

-rw-r--r-- 1 ice ice 30000040 2011-01-30 00:05 test_out

Учитывая, что в файле должно содержаться 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 nums

Prelude> 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

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

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

Интересно получается у нас с работой в УУ но самый востребованный прога это тот который знает 1С8 и умеет писать в ней доработки

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

проверял - писал программу, которая использовала много памяти в куче, за несколько секунд разросталась на 100 мегабайт, при завершении память оставалась забитой.

код в студию, надеюсь, в нем не будет GlobalAlloc'ов и т.п.

могу предложить позапускать несколько раз программульку типо:

#define SZ (2 << 20) * 100

int main()
{
   char * p = new char [SZ];
   return 0;
}

и посмотреть сколько мусора от нее останется.

А разве это не классика кун-фу?

судя по всему - она

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

Agarb

не уберет.

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

usb-creator-gtk -i /path/to/iso

Сочувствую Вашему первому опыту в использовании Linux. Тем не менее, имхо, первое, что Вам необходимо было сделать, прежде чем начинать установку Linux на реальную машину - это проверить совместимость необходимого Вам программного обеспечения. Если Вам необходимо то, что не работает в линукс, то Вы в любом случае отказались бы от него.

Все перечисленные проблемы (кроме совместимости с программным обеспечением), скорее всего, относятся конкретно к выбранному Вами дистрибутиву: Вы, наверняка, мало представляете насколько могут отличаться дистрибутивы и как много их существует, в отличии от сборок windows, которые отличаются, по-большому счету, темами и некоторыми системными настройками

потому что далеко не всегда достаточно пхп

всем привет!!! 9 месяцев назад получила права, и вот только месяц как купила машину. в общем навыки вождения улетучились, словно и не училась, но сейчас спустя месяц вроде как всё вспомнила. но с мужскаим полом ездить это капец... всё наровят учить... помогают объехать ямки((((, хотя понимаю что вожу не идеально, на стараюсь быт аккуратной.

так со всеми абсолютно: и с девушками и с парнями. Всех кто только закончил школу наровят учить "более опытные" водилы. Выход: либо не обращать внимание,

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

Новая беда - ошибки внутри fstream.h/fstream, iostream.h/iostream и istream/istream.h. В общем более 50 штук.

На днях довелось покодить в embarcadero, правда под хрюшу, так вот, использовал fstream, проблем не было никаких

Да уж лучше почитать что-нибудь, что не привязано к языку, типо "мифический человеко-месяц", "искусство программирования" и т.п.

Если, уж очень хочется лучше узнать С++, то "exceptional C++" и "efficient C++"

PS: имхо...

Как всегда: соберешь материалы, переведешь описалово с официального сайта, сделаешь торрент и на тебе:

http://ulanovka.ru/forum/viewtopic.php?t=59264 =)

http://ulanovka.ru/forum/viewtopic.php?t=61132 - а это CeeBot - версия для учебных заведений)

Поофтоплю, чуток:

Недавно, ко мне в руки попала игрушка colobot

http://www.ceebot.com/colobot/index-e.php http://en.wikipedia.org/wiki/Colobot http://habrahabr.ru/blogs/programmers_games/59708/

http://ru.wikipedia.org/wiki/Colobot http://www.3dnews.ru/games/colobot#voting http://v673.com/programmers-games/colobot-and-ceebot/

Суть ее в том, чтобы писав сценарии на Си-подобном языке, выполнить определенные задачи.

Игрушка старенькая, а целевая аудитория - дети 10+ лет, задания не такие уж и сложные (я не много в нее рубился =) )

Но, если искать более обобщенное решение, то вполне получится интересно убить время (:

Так о чем, я - выложить?)

Я буду походить на гея пирата оно мне надо!

Расставь знаки препинания, не смущай народ

The_Ice

Кстати великий и ужасный явит себя миру?

Волендеморт?!)

нарисуй, хотя бы усы