GCJ 2010: Fair Warning in Common Lisp (Qualification Round)

The maximum possible factor is determined by the GCD between the Great Events in the past. Sorry for the unclear explanation. Anyway, the way I solved this is: I first sort the sequence of ages of past events in descending order. Then I normalize them with respect to the most recent of these events, by subtracting the smallest of these ages. I take the GCD of the other (non-smallest) event ages. This GCD defines a kind of cycle. The apocalypse (or party) will happen at the next possible cycle boundary after OR AT the current time.

Thankfully, Common Lisp has a variadic GCD function and efficient bignum implementations.

(defun solve (file)
  (with-open-file (in file)
    (let ((ncases (read in)))
      (dotimes (caseno ncases)
 (solve-case in caseno)))))

(defun solve-case (in caseno)
  (let ((nevents (read in)))
    (let ((events (make-array (list nevents))))
      (dotimes (k nevents)
 (setf (aref events k)
   (read in)))
      ;; We would like these to be in canonical order, let's say decreasing
      (setq events (sort events #'>))
      (let ((solution (time-to-apocalypse events)))
 (format t "Case #~D: ~D~%" (1+ caseno) solution)))))

(defun time-to-apocalypse (events)
  (let ((reckon (aref events (1- (length events))))) ;time since last event
    (dotimes (k (length events))
      (decf (aref events k) reckon))
    (let ((gcd (apply #'gcd (coerce (subseq events 0 (1- (length events))) 'list))))
      (if (= gcd 1)
   0
 (rem (- gcd (rem reckon gcd)) gcd)))))