Skip to content

Instantly share code, notes, and snippets.

@adilakhter adilakhter/spoj_COINS.fsx
Last active Dec 14, 2015

Embed
What would you like to do?
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.