Bittijono

input/code.hs:3:1: Warning:
    The import of `Data.List' is redundant
      except perhaps to import instances from `Data.List'
    To import instances alone, use: import Data.List()

input/code.hs:6:1: Warning:
    The import of `Data.Fixed' is redundant
      except perhaps to import instances from `Data.Fixed'
    To import instances alone, use: import Data.Fixed()

input/code.hs:7:1: Warning:
    The import of `showHex' from module `Numeric' is redundant

input/code.hs:12:16: Warning:
    Defaulting the following constraint(s) to type `Double'
      (Floating a0) arising from a use of `log' at input/code.hs:12:16-18
      (Fractional a0) arising from a use of `/' at input/code.hs:12:38
      (Num a0)
        arising from a use of `fromIntegral' at input/code.hs:12:21-32
      (RealFrac a0)
        arising from a use of `floor' at input/code.hs:12:8-12
    In the first argument of `(/)', namely `(log (fromIntegral a))'
    In the first argument of `floor', namely
      `((log (fro...

{- Tuli cachetusta koodista vähän likainen olo, varsinkin kun siinä oli ollut se Python. Tässä sama performanssi todellisella Haskellilla ilman esilaskentaa. -}

import Data.List
import Data.Map
import Data.Set
import Data.Fixed
import Numeric (showHex, showIntAtBase)
import Data.Char (intToDigit)

{- integer base 2 logarythm -}
lb :: Int -> Int
lb a = floor ((log (fromIntegral a)) / (log (fromIntegral 2)))

{- Given the cache, look up the combinations for a given element -}

countCombinations cache index = sum (Prelude.map (length) hit)
    where hit = snd (Data.Map.elemAt (Data.Map.findIndex index cache) cache)



{- Get the set for length 1 elements in a given number -}

basePairs 0 = Data.Set.fromList [0]
basePairs bitstring = zeroElem `Data.Set.union` oneElem

    {- If all the bits of the bitstring are on, the bitstring + 1 is a power of two => if the bitstring + 1 is a power of two, then there are no zeroes in the bitstring -}

    where zeroElem = if 2^(lb (bitstring + 1))/= bitstring + 1 then Data.Set.fromList [0] else Data.Set.empty

    {- If the bistring is non-zero, it has at least one bit on -}

          oneElem = if bitstring == 0 then Data.Set.empty else Data.Set.fromList [1]




{- Find the union of the new combinations brought by the addition of the new possible bit and the combinations alreeady known -}

newCombinations previous current newBit = current `Data.Set.union` new
    where new = Data.Set.map (computeCombination) previous
          computeCombination base = 2*base + newBit



{- Construct a chain from an ancestors -}


fromAncestor (first:second:ancestors) newBit = (newCombinations first second newBit):(fromAncestor (second:ancestors) newBit)
fromAncestor (ancestor:[]) newBit = [newCombinations ancestor Data.Set.empty newBit]


{- Compute the combinations for a bitstring with a known ancestor -}

iterateOnce 1 ancestor = [(Data.Set.fromList [1])]
iterateOnce current ancestor = ((basePairs current):(fromAncestor ancestor newBit))
    where newBit = current `rem` 2

{- Compute the combinations from the new number alone -}

body 1 cache = ((iterateOnce 1 []), cache)
body bitstring cache = if Data.Map.member bitstring cache then (snd (Data.Map.elemAt (Data.Map.findIndex bitstring cache) cache), cache) else ((iterateOnce bitstring ancestor), resultCache)
    where (ancestor, returnedCache) = body (bitstring `div` 2) cache
          newCache = (returnedCache `Data.Map.union` cache)
          result = iterateOnce bitstring ancestor
          resultCache = newCache `Data.Map.union` (Data.Map.fromList [(bitstring, result)])

{- Compute the number of combinations for a number -}

combinationCount bitstring cache = (sum (Prelude.map (Data.Set.size) construct), newCache)
    where (construct, newCache) = body bitstring cache

{- Compute the starting point with a given target -}


startingPoint current target cache = if base < target then (if combinationsA > combinationsB then startingPoint a target newCache else startingPoint b target newCache) else (lb current, newCache)
    where a = current * 2
          b = a + 1
          (base, cache2) = combinationCount current cache
          (combinationsA, cacheA) = combinationCount a cache2
          (combinationsB, newCache) = combinationCount b cacheA

{- Compute the smallest number to have a given number of combinations -}

solution target = testForwards (2^start) target cache2
    where (start, cache2) = startingPoint 1 target (Data.Map.fromList [])
          testForwards i target cache = if combinations == target then i else testForwards (i+1) target nextCache
            where (combinations, nextCache) = combinationCount i cache

main :: IO ()
main = do
    num <- getLine
    let target = read num :: Int
    putStrLn (showIntAtBase 2 intToDigit (solution target) "")

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 29

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 31

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 33

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 34

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 36

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 37

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 40

Group: 4

Verdict: TIME LIMIT EXCEEDED