結果

問題 No.4 おもりと天秤
コンテスト
ユーザー mikan-water
提出日時 2024-02-01 09:50:33
言語 Common Lisp
(sbcl 2.6.3)
コンパイル:
sbclc _filename_
実行:
sbcl --script Main.fasl
結果
AC  
実行時間 35 ms / 5,000 ms
コード長 1,646 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 222 ms
コンパイル使用メモリ 43,880 KB
実行使用メモリ 40,280 KB
最終ジャッジ日時 2026-04-15 02:01:00
合計ジャッジ時間 1,993 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 15 APR 2026 02:00:53 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) (#:V0 S))
;     (DECLARE (IGNORABLE #:V0)
;              (TYPE VECTOR #:V0)
;              (IGNORABLE C))
;     (MULTIPLE-VALUE-BIND (#:D1 #:I2)
;         (SB-KERNEL:%DATA-VECTOR-AND-INDEX/KNOWN #:V0 0)
;       (LET ((#:LIM3 #))
;         (SB-C::%IN-BOUNDS-CONSTRAINT #:D1 #:LIM3)
;         (TAGBODY
;          SB-LOOP::NEXT-LOOP
;           (WHEN # #)
;           (SB-LOOP::LOOP-DESETQ C #)
;           (SB-LOOP::LOOP-DESETQ #:I2 #)
;           (CONVERT-TO-INT C)
;           (GO SB-LOOP::NEXT-LOOP)
;          SB-LOOP::END-LOOP
;           (PUSH # *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.026

ソースコード

diff #
raw source code 

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