# My Weblog

## SPOJ 291. Cube Root

SPOJ 291. Cube Root ‘s difficulty is about parsing inputs. Haskell provides very neat functions to parse inputs so just concentrate of solving problem . Lets say a is integer and b is fraction part of cube root of n so $( a + b ) ^ 3 = n$. $a^{3} + b^{3} + 3*a*b*(a+b) = n => b^{3} + 3*a*b*(a+b) = n - a^{3}$. First i searched using binary search on Integer values for Integer part of cube root and then again binary search between 0 and 1 to find out b. Here is source code.

```import Data.List
import qualified Data.Char as DC
import Numeric

format :: [[String]] -> [Integer]
format [] = []
format (x:xs)  = if null x then format xs else  ( map read x ) ++  format xs

cbrtNewton :: Double  -> Double -> Double
cbrtNewton 0 _ = 0
cbrtNewton x a = bsearch 0 1 where
bsearch lo hi | abs ( lo - hi ) <= 1e-12 = lo
| mid * ( mid * ( mid + 3*a ) + 3*a**2) <= x = bsearch mid hi
| otherwise = bsearch lo mid
where mid = ( lo + hi ) * ( 0.5 )

--upperbound search
search :: Integer -> Integer
search 1 = 1
search n = bsearch 1  n  where
bsearch lo hi | lo >= hi = ( lo - 1 )
| mid ^ 3 <= n = bsearch ( mid + 1 ) hi
| otherwise = bsearch lo mid
where mid = div ( lo + hi ) 2

solve :: Integer -> String
solve x =  a where
y = search x
z = showFFloat Nothing ( cbrtNewton ( fromIntegral ( x - y^3 ) ) ( fromIntegral y ) ) ""
z' = tail . take 12 \$  z  ++ "0000000000000000000000000000000000000"
ps = show \$ mod ( foldl ( \acc x -> if DC.isDigit x then acc + DC.digitToInt x else acc ) 0 ( show y ++ z' ) ) 10
a = ps ++ " " ++ show y ++  z'

main = interact \$  unlines.map  solve .  format .map words . tail . lines
```