結果

問題 No.4 おもりと天秤
コンテスト
ユーザー mikan-water
提出日時 2024-02-01 09:50:33
言語 Common Lisp
(sbcl 2.5.0)
結果
AC  
実行時間 48 ms / 5,000 ms
コード長 1,646 bytes
コンパイル時間 776 ms
コンパイル使用メモリ 30,336 KB
実行使用メモリ 29,824 KB
最終ジャッジ日時 2024-09-28 10:27:30
合計ジャッジ時間 1,624 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 28 SEP 2024 10:27:27 AM):

; file: /home/judge/data/code/Main.lisp
; in: DEFUN SET-WS
;     (LOOP FOR C ACROSS S
;           DO (CONVERT-TO-INT C)
;           FINALLY (PUSH (PARSE-INTEGER (COERCE (REVERSE *STACK*) 'STRING))
;                         *INTS*))
; ==>
;   (LET ((C NIL) (#:LOOP-ACROSS-VECTOR-0 S) (#:LOOP-ACROSS-INDEX-1 0))
;     (DECLARE (IGNORABLE #:LOOP-ACROSS-INDEX-1)
;              (TYPE FIXNUM #:LOOP-ACROSS-INDEX-1)
;              (IGNORABLE #:LOOP-ACROSS-VECTOR-0)
;              (TYPE VECTOR #:LOOP-ACROSS-VECTOR-0)
;              (IGNORABLE C))
;     (LET ((#:LOOP-ACROSS-LIMIT-2 (LENGTH #:LOOP-ACROSS-VECTOR-0)))
;       (TAGBODY
;        SB-LOOP::NEXT-LOOP
;         (WHEN (>= #:LOOP-ACROSS-INDEX-1 #:LOOP-ACROSS-LIMIT-2)
;           (GO SB-LOOP::END-LOOP))
;         (SB-LOOP::LOOP-DESETQ C
;                               (AREF #:LOOP-ACROSS-VECTOR-0
;                                     #:LOOP-ACROSS-INDEX-1))
;         (SB-LOOP::LOOP-DESETQ #:LOOP-ACROSS-INDEX-1 (1+ #:LOOP-ACROSS-INDEX-1))
;         (CONVERT-TO-INT C)
;         (GO SB-LOOP::NEXT-LOOP)
;        SB-LOOP::END-LOOP
;         (PUSH (PARSE-INTEGER #) *INTS*))))
; 
; caught WARNING:
;   undefined variable: COMMON-LISP-USER::S

;     (SETF S (READ-LINE))
; 
; caught WARNING:
;   undefined variable: COMMON-LISP-USER::S
; 
; compilation unit finished
;   Undefined variable:
;     S
;   caught 2 WARNING conditions

; wrote /home/judge/data/code/Main.fasl
; compilation finished in 0:00:00.047

ソースコード

diff # 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; 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)
0