spoj_COINS.fsx

open System
open System.Collections.Generic 

module Memo = 
  let empty () = new Dictionary<int64,int64>()

  let add k v (memo:Dictionary<int64,int64>) = 
    memo.[k] <- v; memo 

  let tryFind k (memo:Dictionary<int64,int64>) = 
    match memo.TryGetValue(k) with 
    | true, v -> Some(v) 
    | false,_ -> None


let computeMaxDollars (n:int) (memo:Dictionary<int64,int64>)=    
  let rec computeMaxDollars' (ni:int64) = 
    if ni = 0L || ni = 1L then // base case 
      ni
    else
      match memo|> Memo.tryFind ni with 
      | Some (nx) -> nx  // found in memo. Returning Result. 
      | None     -> 
        let f  = computeMaxDollars' 
        let nx = 
          (ni/2L, ni/3L, ni/4L)
          |> (fun (x,y,z) -> (f x) + (f y) + (f z)) 
          |> (fun nx -> Math.Max(ni,nx))

        memo|> Memo.add ni nx |> ignore // storing the result in memo
        nx
  computeMaxDollars' (n|>int64) 
(*
 * IO STUFF 
 * ------------------
 *  Reads inputs and writes relevant outputs after performing
 *  necessary computations.  
 *)
let solve_SPOJCOINS() = 
  let memo = Memo.empty()
  let parseCase () : int option= 
    let s = System.Console.ReadLine()
    if s <> null  then 
      s.Trim()
      |> fun x -> match Int32.TryParse x  with | true, xs -> Some(xs) | false,_ -> None
    else 
      None
  let rec solveCases () = 
    match parseCase() with
    | None -> () 
    | Some(x) -> 
        memo 
        |> computeMaxDollars x
        |> printfn "%d" 
        solveCases () 
  solveCases()

solve_SPOJCOINS()