Working on https://www.spoj.com/problems/TUG/

tugofwar.lisp

(defun tug-of-war (people)
  (declare (optimize (speed 3))
           ((simple-array fixnum (*)) people))
  (setf people (sort people #'>))
  (let ((sum (reduce #'+ people)))
    (declare (fixnum sum))
    (if (evenp sum)
        (let ((sum (floor sum 2)))
          (labels ((recursive-walk (upto currentsum)
                     (declare (fixnum currentsum))
                     (cond ((>= upto (length people)) nil)

                           ((> sum (+ currentsum (aref people upto)))
                            (loop :for i :from 1 :upto (- (length people) upto 1)
                                    :thereis (recursive-walk
                                              (+ i upto)
                                              (+ currentsum (aref people upto)))))

                           ((< sum (+ currentsum (aref people upto)))
                            (recursive-walk
                             (+ 1 upto)
                             currentsum))

                           (t
                            (return-from recursive-walk t)))))

             (recursive-walk 0 0))))))


(defun main (stream)
  (loop :with tests := (read stream)
        :repeat tests
        :for len := (read stream)
        :for people := (make-array len
                                   :element-type 'fixnum
                                   :initial-contents (loop :repeat len
                                                           :collect (read stream)))
        :collect (tug-of-war people) :into answers
        :finally (mapcar (lambda (answer) (format t "~:[NO~;YES~]~%" answer)) answers)))



(defun generate-test (testnum testlength range)
  (with-open-file (stream "~/Desktop/Coding/Lisp/tugofwartests.txt"
                          :direction :output :if-does-not-exist :create
                          :if-exists :supersede)
    (format stream "~s~%" testnum)
    (loop :repeat testnum
          :do (let ((len (+ 1 (random testlength))))
                (format stream "~s~%" len)
                (loop :repeat len :do (format stream "~s " (+ 1 (random (- range 1)))))
                (terpri stream)))))
  ;(uiop:run-program `("cat tugofwartests.txt | curl -F 'f:1=<-' ix.io")))


(generate-test 30 1000 100)

(with-open-file (stream "~/Desktop/Coding/Lisp/tugofwartests.txt"
                              :direction :input)
        (main stream))