May 2011
1 / 3
May 2011
May 2011
mukesh_iiitm
May '11

Hello all
I am trying to solve this problem https://www.spoj.pl/problems/CUBERT7 but getting wrong answer . If some one accepted could post some tricky test cases , it would be great. I used Newton's method [ en.wikipedia.org/wiki/Cube_root7 ] to calculate the cube root . 

import Data.List 
import qualified Data.Char as DC
format :: [[String]] -> [Integer] 
format [] = []
format (x:xs)  = if null x then format xs else  ( map read x ) ++  format xs 
cbrtNewton :: Double -> Double -> Double
cbrtNewton x n  = fst $ until ( \(a, b) -> abs( a - b ) <= 1e-12 )  (\(_ , x0) -> ( x0 , ( (n-1) * x0 + x / x0**(n-1) ) /n ) ) ( x ,x/n )
solve :: Integer -> String 
solve x =  a where
	( y , z ) = break ( =='.') . show . cbrtNewton ( fromIntegral x ) $ 3 
	z' = take 11 ( z ++ "000000000000000000" ) 
        ps = show $ mod ( foldl ( \acc x -> if DC.isDigit x then acc + DC.digitToInt x else acc ) 0 ( y ++ z' ) ) 10
	a = ps ++ " " ++ y ++  z'
main = interact $  unlines.map  solve .  format .map words . tail . lines

  • created

    May '11

  • last reply

    May '11
  • 2

    replies

  • 983

    views

  • 2

    users

  • 2

    links

un_loco
May '11

Hola!
(Problem code: CUBERT)

I haven't solved it yet. Have you checked your code for big enough numbers? (large positive integers of up to 150 decimal digits)

for n = 111111111111111111111111111111111111111111111111111111111111111111111111
Your answer:
4 4.8074985676

mukesh_iiitm
May '11

Hi un_loco
Thank you for reply. Now i changed the method but i am still wrong answer. Here is my method. 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. It would be great if some one accepted can post some test cases for this problem .
Thank you 

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