Problem 85 - 長方形の組合せ

結構面白い。

Problem 85 - PukiWiki

x * yの枠があって、その中に入る長方形の組合せの数を求める。

1 * 1から順に組合せ数を求めてみると面白いルールが浮かび上がってくる。ルールは内緒。

で、そこからがちと面倒で、2,000,000に一番近い解をどうやって求めるのかってところがイマイチ。

2,000,000 - (x, y)の解の数

としてマイナスになったら折り返し。としてるけど、解の候補は各列に2個以内なハズ。

うまい方法はないかな。

(define (problem85 n)
  (letrec ((sum
             (lambda (x y)
               (let ((s (lambda (n)
                          (/ (* (+ 1 n) n) 2))))
                 (* (s x) (s y)))))
           (iter
             (lambda (x y m pos)
               (let* ((s (- n (sum x y)))
                      (a (abs s)))
                 (cond ((< a m) (iter x (+ y 1) a (list x y)))
                       ((negative? s) (if (= x y)
                                          pos
                                          (iter (+ x 1) (+ x 1) m pos)))
                       (else
                         (iter x (+ y 1) m pos)))))))
    (iter 1 1 n '(0 0))))

(problem85 10000) ; (5 36)
(problem85 100000) ; (7 84)
(problem85 1000000) ; (2 816)
(problem85 2000000) ; (36 77)
(apply * (problem85 2000000)) ; 2772

結構シンプル。