ICPC2005 ProblemB

Make Purse Light!

(defun calc-return (money)
  (multiple-value-bind (500-yen rem) (floor money 500)
		      (multiple-value-bind (100-yen rem) (floor rem 100)
					  (multiple-value-bind (50-yen rem) (floor rem 50)
							      (multiple-value-bind (10-yen rem) (floor rem 10)
										  `(,10-yen ,50-yen ,100-yen ,500-yen))))))

(defun calc-money (list)
  (let
      ((10-yen (car list))
       (50-yen (cadr list))
       (100-yen (caddr list))
       (500-yen (cadddr list)))
    (+ (* 500-yen 500) (* 100-yen 100) (* 50-yen 50) (* 10-yen 10))))

(defun calc-bill-pattern (bill money-list)
  (loop for 10-yen from 0 upto (car money-list)
       append
       (loop for 50-yen from 0 upto (cadr money-list)
	    append
	    (loop for 100-yen from 0 upto (caddr money-list)
		 append
		 (loop for 500-yen from 0 upto (cadddr money-list)
		      when (>= (calc-money `(,10-yen ,50-yen ,100-yen ,500-yen)) bill)
		      collect `(,10-yen ,50-yen ,100-yen ,500-yen))))))

(defun calc-rem-money (walet pay)
  (mapcar #'- walet pay))

(defun collect-patternp (pay res)
  (every (lambda (x y) (if (not (zerop x)) (zerop y) t)) pay res))

(defun print-money (money-list)
  (loop
     for money in money-list
     for i in '(10 50 100 500)
     when (not (zerop money))
       do
       (format t "~A ~A~%" i money)))

(defun calc-res (pay walet)
  (caar
   (sort 
    (loop
       for pay-pattern in (calc-bill-pattern pay walet)
       for rem-in-walet = (calc-rem-money walet pay-pattern)
       for return-money = (calc-return (- (calc-money pay-pattern) pay))
       for res-in-walet = (mapcar #'+ rem-in-walet return-money)
       when (collect-patternp pay-pattern return-money)
       collect `(,pay-pattern ,res-in-walet))
    #'< :key (lambda (x) (apply #'+ (cadr x))))))

(defun main ()
  (loop
     for money = (read)
     until (zerop money)
     for res = (calc-res money `(,(read) ,(read) ,(read) ,(read)))
       do
       (progn (print-money res) (format t "~%"))))

これはすこし面倒でした。