[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/S0qgV4pB    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Feb 13:
; facebook hacker cup 2013, round 1, problem 1

(define (drop n xs)
  (let loop ((n n) (xs xs))
    (if (or (zero? n) (null? xs)) xs
      (loop (- n 1) (cdr xs)))))

(define sort #f)
(define merge #f)
(let ()
  (define dosort
    (lambda (pred? ls n)
      (if (= n 1)
          (list (car ls))
          (let ((i (quotient n 2)))
            (domerge pred?
                     (dosort pred? ls i)
                     (dosort pred? (list-tail ls i) (- n i)))))))
  (define domerge
    (lambda (pred? l1 l2)
      (cond
        ((null? l1) l2)
        ((null? l2) l1)
        ((pred? (car l2) (car l1))
         (cons (car l2) (domerge pred? l1 (cdr l2))))
        (else (cons (car l1) (domerge pred? (cdr l1) l2))))))
  (set! sort
    (lambda (pred? l)
      (if (null? l) l (dosort pred? l (length l)))))
  (set! merge
    (lambda (pred? l1 l2)
      (domerge pred? l1 l2))))

(define m 1000000007)

(define n 10000)

(define (inverse x m)
  (let loop ((x x) (a 0) (b m) (u 1))
    (if (positive? x)
        (let ((q (quotient b x)) (r (remainder b x)))
        (loop (modulo b x) u x (- a (* q u))))
        (if (= b 1) (modulo a m) #f))))

(define inv
  (let ((inverses (make-vector (+ n 1) 0)))
    (do ((x 1 (+ x 1))) ((< n x))
      (vector-set! inverses x (inverse x m)))
    (lambda (x) (vector-ref inverses x))))

(define (choose n k)
  (if (zero? k) 1
    (modulo (* n (inv k) (choose (- n 1) (- k 1))) m)))

(define (f n k as)
  (let loop ((i (- k 1)) (as (drop (- k 1) (sort < as))) (s 0))
    (if (null? as) s
      (loop (+ i 1) (cdr as) (+ s (* (choose i (- k 1)) (car as)))))))

(display (f 4 3 '(3 6 2 8))) (newline)
(display (f 5 2 '(10 20 30 40 50))) (newline)
(display (f 6 4 '(0 1 2 3 5 8))) (newline)
(display (f 2 2 '(1069 1122))) (newline)
(display (f 10 5 '(10386 10257 10432 10087 10381 10035 10167 10206 10347 10088))) (newline)


Output:
1
2
3
4
5
30
400
103
1122
2621483


Create a new paste based on this one


Comments: