;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Use DP ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; integer (defparameter *half* 0) (defparameter *n* 0) ; list (defparameter *stack* nil) (defparameter *ints* nil) ; array (defparameter *ws* nil) (defparameter *dp* (make-array (list 101 10001) :initial-element nil)) (defun convert-to-int (c) (cond ((char= c #\ ) (push (parse-integer (coerce (reverse *stack*) 'string)) *ints*) (setf *stack* nil) ) (t (push c *stack*)) ) ) (defun set-ws () (setf s (read-line)) (loop for c across s do (convert-to-int c) finally (push (parse-integer (coerce (reverse *stack*) 'string)) *ints*) ) (setf *ws* (reverse *ints*)) ) (defun input () (setf *n* (parse-integer (read-line))) (set-ws) ) (defun initial-setting () (input) (loop for w in *ws* summing w into total finally (setf *half* (/ total 2)) ) (setf (aref *dp* 0 0) t) (setf *ws* (make-array (length *ws*) :initial-contents *ws*)) ) (defun run-dp () (loop for i from 0 to (1- *n*) do (loop for j from 0 to *half* do (setf (aref *dp* (1+ i) j) (or (aref *dp* (1+ i) j) (aref *dp* i j))) (cond ((>= j (aref *ws* i)) (setf (aref *dp* (1+ i) j) (or (aref *dp* (1+ i) j) (aref *dp* i (- j (aref *ws* i))))))) ) ) (if (aref *dp* *n* *half*) (princ "possible") (princ "impossible") ) ) (defun n4 () (initial-setting) ; A half of total mass must be integer. (cond ((null (integerp *half*)) (princ "impossible") (return-from n4))) (run-dp) ) (n4)