Halloween Party Problem Solution in Lisp


The problem:

Alex is attending a Halloween party with his girlfriend Silvia. At the party, Silvia spots a giant chocolate bar. If the chocolate can be served as only 1 x 1 sized pieces and Alex can cut the chocolate bar exactly K times, what is the maximum number of chocolate pieces Alex can cut and give Silvia?

My Common Lisp Solution

The key to solve this problem with efficiency is to realize that the value of the Nth element of the series is n^2/4 (rounded down).

(defun calculatePieces (cuts)
        (truncate (/ (* cuts cuts) 4)))

(defun main (tests)
        (if (> tests 0)
                (progn
                (setq line (read-line))
                (format t "~d" (calculatePieces (parse-integer line)))
                (if (> tests 1)
                        (format t "~%"))
                (main (- tests 1)))))

(setq line (read-line))

(main (parse-integer line))

Leave a Reply

Your email address will not be published. Required fields are marked *