coins.lisp

;; Spoj code : COINS

(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (multiple-value-bind
              (result exists)
            (gethash args cache)
          (if exists
              result
              (setf (gethash args cache)
                    (apply fn args)))))))

(defun exchange-val (n)
  (cond ((eq n 0) 0)
        ((eq n 1) 1)
        ((eq n 2) 2)
        ((eq n 3) 3)
        ((eq n 4) 4)
        ((eq n 5) 5)
        ((eq n 6) 6)
        ((eq n 7) 7)
        ((eq n 8) 8)
        ((eq n 9) 9)
        ((eq n 10) 10)
        ((eq n 11) 11)
        ((eq n 12) 13)
        (t (+ (exchange-val (floor n 2))
              (exchange-val (floor n 3))
              (exchange-val (floor n 4))))))

(setf (fdefinition 'exchange-val) (memoize #'exchange-val))

(defun run ()
  (loop for line = (read-line *standard-input* nil :eof)
        until (eq line :eof)
        do (format t "~a~%" (exchange-val (parse-integer line)))))

(run)