結果
問題 | No.5015 Escape from Labyrinth |
ユーザー |
|
提出日時 | 2023-04-16 18:25:15 |
言語 | Common Lisp (sbcl 2.5.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 59,812 bytes |
コンパイル時間 | 1,007 ms |
コンパイル使用メモリ | 116,196 KB |
実行使用メモリ | 340,932 KB |
スコア | 20,580 |
最終ジャッジ日時 | 2023-04-16 18:30:07 |
合計ジャッジ時間 | 287,734 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 73 RE * 19 TLE * 8 |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 16 APR 2023 06:25:15 PM): ; processing (IN-PACKAGE #:CL-USER) ; processing (DECLAIM (OPTIMIZE # ...)) ; processing (DECLAIM (MUFFLE-CONDITIONS COMPILER-NOTE)) ; processing (DISABLE-DEBUGGER) ; processing (SET-DISPATCH-MACRO-CHARACTER #\# ...) ; processing (SET-DISPATCH-MACRO-CHARACTER #\# ...) ; processing (DEFPACKAGE CP-LIBRARY/AVL-TREE ...) ; processing (IN-PACKAGE AVL) ; processing (DECLAIM (INLINE %%MAKE-NODE)) ; processing (DEFSTRUCT (NODE # ...) ...) ; processing (DEFMACRO DEFINE-ACCESSOR-FOR-NULLABLE-NODE ...) ; processing (DEFINE-ACCESSOR-FOR-NULLABLE-NODE %VALUE ...) ; processing (DEFINE-ACCESSOR-FOR-NULLABLE-NODE %KEY ...) ; processing (DEFINE-ACCESSOR-FOR-NULLABLE-NODE %CNT ...) ; processing (DEFINE-ACCESSOR-FOR-NULLABLE-NODE %HEIGHT ...) ; processing (DEFINE-ACCESSOR-FOR-NULLABLE-NODE %L ...) ; processing (DEFINE-ACCESSOR-FOR-NULLABLE-NODE %R ...) ; processing (DEFUN DUMP-TO-LIST ...) ; processing (DEFMETHOD PRINT-OBJECT ...) ; processing (DEFUN DUMP-TO-TREE ...) ; processing (DECLAIM (INLINE %MAKE-NODE)) ; processing (DEFUN %MAKE-NODE ...) ; processing (DEFUN MAKE-AVL-TREE ...) ; processing (DECLAIM (INLINE %UPDATE-NODE)) ; processing (DEFUN %UPDATE-NODE ...) ; processing (DECLAIM (INLINE %ROTATE-LEFT)) ; processing (DEFUN %ROTATE-LEFT ...) ; processing (DECLAIM (INLINE %ROTATE-RIGHT)) ; processing (DEFUN %ROTATE-RIGHT ...) ; processing (DECLAIM (INLINE %ROTATE-LR)) ; processing (DEFUN %ROTATE-LR ...) ; processing (DECLAIM (INLINE %ROTATE-RL)) ; processing (DEFUN %ROTATE-RL ...) ; processing (DEFCONSTANT +TOO-LEFT+ ...) ; processing (DEFCONSTANT +LEFT+ ...) ; processing (DEFCONSTANT +EVEN+ ...) ; processing (DEFCONSTANT +RIGHT+ ...) ; processing (DEFCONSTANT +TOO-RIGHT+ ...) ; processing (DECLAIM (INLINE %BIAS)) ; processing (DEFUN %BIAS ...) ; processing (DECLAIM (INLINE %LEFT-RIGHT-CASE-P)) ; processing (DEFUN %LEFT-RIGHT-CASE-P ...) ; processing (DECLAIM (INLINE %RIGHT-LEFT-CASE-P)) ; proces
ソースコード
(in-package #:cl-user);;;;;; Init;;;(eval-when (:compile-toplevel :load-toplevel :execute);; #+swank (declaim (optimize (speed 3) (safety 2)))#+swank (declaim (optimize (speed 0) (safety 3) (debug 3)))#-swank (declaim (optimize (speed 3) (safety 0) (debug 0)))#-swank (declaim (sb-ext:muffle-conditions sb-ext:compiler-note))#-swank (sb-ext:disable-debugger));;;;;; Reader Macros;;;(eval-when (:compile-toplevel :load-toplevel :execute)(set-dispatch-macro-character#\# #\f#'(lambda (stream c2 n)(declare (ignore c2 n))(let ((form (read stream t nil t)))`(lambda (&optional %) (declare (ignorable %)) ,form))))(set-dispatch-macro-character#\# #\>#'(lambda (stream c2 n)(declare (ignore c2 n))(let ((form (read stream t nil t)))(declare (ignorable form))#-swank nil#+swank (if (atom form)`(format *error-output* "~a => ~a~&" ',form ,form)`(format *error-output* "~a => ~a~&" ',form `(,,@form)))))));;;;;; Libraries;;;;;;;;; BOF;;;(defpackage cp-library/avl-tree(:use #:cl)(:nicknames #:avl)(:shadow #:remove#:count)(:export #:make-avl-tree#:insert#:remove#:insert!#:remove!#:count#:dump-to-list#:dump-to-tree#:keys#:vals#:predecessor#:successor#:nth-element#:compare-default#:compare-keyword#:ref#:update#:update!#:make-avl-tree-from-list#:rand-nth))(in-package avl)(declaim (inline %%make-node))(defstruct (node (:constructor %%make-node)(:conc-name %%))(key nil :type t)(value nil :type t)(cnt nil :type fixnum)(height nil :type fixnum)(l nil :type (or null node))(r nil :type (or null node)))(defmacro define-accessor-for-nullable-node (name accessor default)`(progn(declaim (inline ,name))(defun ,name (node)(if node(,accessor node),default))))(define-accessor-for-nullable-node %value %%value nil)(define-accessor-for-nullable-node %key %%key nil)(define-accessor-for-nullable-node %cnt %%cnt 0)(define-accessor-for-nullable-node %height %%height 0)(define-accessor-for-nullable-node %l %%l nil)(define-accessor-for-nullable-node %r %%r nil)(defun dump-to-list (node)(let ((res nil))(labels ((rec (node)(when node(rec (%%l node))(push (cons (%%key node)(%%value node))res)(rec (%%r node)))))(rec node)(reverse res))))(defmethod print-object ((node node) s)(print-unreadable-object (node s :type t)(dolist (kv (dump-to-list node))(fresh-line s)(princ kv s))(terpri s)))(defun dump-to-tree (node)(labels ((rec (node)(when node(cl:remove nil(list(rec (%%l node))(when node(cons (%%key node)(%%value node)))(rec (%%r node)))))))(rec node)))(declaim (inline %make-node))(defun %make-node (&key key value l r)(declare ((or null node) l r))(let ((height (1+ (max (%height l)(%height r))))(cnt (1+ (the fixnum(+ (%cnt l)(%cnt r))))))(declare (fixnum height cnt))(%%make-node :key key:value value:height height:cnt cnt:l l:r r)))(defun make-avl-tree ()"Create an empty avl-tree."nil);; helper functions(declaim (inline %update-node))(defun %update-node (node &key (key nil k-p) (value nil v-p) (l nil l-p) (r nil r-p))(%make-node :key (if k-pkey(%key node)):value (if v-pvalue(%value node)):l (if l-pl(%l node)):r (if r-pr(%r node))))(declaim (inline %rotate-left))(defun %rotate-left (node)(declare (node node)#+sbcl (sb-ext:muffle-conditions sb-ext:compiler-note))(let* ((r (%%r node))(rl (%l r)))(%update-node r :l (%update-node node :r rl))))(declaim (inline %rotate-right))(defun %rotate-right (node)(declare (node node)#+sbcl (sb-ext:muffle-conditions sb-ext:compiler-note))(let* ((l (%%l node))(lr (%r l)))(%update-node l :r (%update-node node :l lr))))(declaim (inline %rotate-lr))(defun %rotate-lr (node)(%rotate-right(%update-node node:l (%rotate-left (%%l node)))))(declaim (inline %rotate-rl))(defun %rotate-rl (node)(%rotate-left(%update-node node:r (%rotate-right (%%r node)))))(defconstant +too-left+ -2)(defconstant +left+ -1)(defconstant +even+ 0)(defconstant +right+ 1)(defconstant +too-right+ 2)(declaim (inline %bias))(defun %bias (node)(if (null node)0(- (%height (%%r node))(%height (%%l node)))))(declaim (inline %left-right-case-p))(defun %left-right-case-p (node)(= (%bias (%%l node)) +right+))(declaim (inline %right-left-case-p))(defun %right-left-case-p (node)(= (%bias (%%r node)) +left+))(declaim (inline %balance))(defun %balance (node)(let ((b (%bias node)))(cond((= b +even+) (values node t))((or (= b +left+)(= b +right+))(values node nil))((<= b +too-left+)(values (if (%left-right-case-p node)(%rotate-lr node)(%rotate-right node))t))(t(values (if (%right-left-case-p node)(%rotate-rl node)(%rotate-left node))t)))))(defun compare-default (key node-key)(declare (fixnum node-key key)(optimize (speed 3) (safety 0)))(cond((= key node-key) :eq)((< key node-key) :less)(t :greater)))(defun compare-keyword (k1 k2)(declare (keyword k1 k2))(let ((k1 (sb-impl::eq-hash k1))(k2 (sb-impl::eq-hash k2)))(cond((< k1 k2) :less)((= k1 k2) :eq)(t :greater))))(defun insert (node key value &optional (compare #'compare-default));; (values balanced-node need-to-balance-parents)(declare (optimize (speed 3) (safety 0))(function compare))(labels ((%rec (node)(unless node(return-from %rec(values (%make-node :key key:value value)nil)))(ecase (funcall compare key (%%key node))(:eq;; 書き換えだけなのでbalanceしなくていい(values (%update-node node :value value)t))(:less(multiple-value-bind (l balanced) (%rec (%%l node))(let ((new-node (%update-node node :l l)))(if balanced(values new-node t)(%balance new-node)))))(:greater(multiple-value-bind (r balanced) (%rec (%%r node))(let ((new-node (%update-node node :r r)))(if balanced(values new-node t)(%balance new-node))))))))(%rec node)))(defun %remove-rightest (node);; (values new-node removed-node balanced)(declare (optimize (speed 3) (safety 0)))(let ((r (%%r node)))(if (null r);; node = rightest(let ((l (%%l node))(removed (%update-node node :l nil)))(values l removed nil))(multiple-value-bind (new-r removed balanced) (%remove-rightest r)(let ((new (%update-node node :r new-r)))(if balanced(values new removed t)(multiple-value-bind (new balanced) (%balance new)(values new removed balanced))))))))(defun remove (node key &optional (compare #'compare-default))(declare (optimize (speed 3) (safety 0))(function compare))(labels ((%rec (node)(unless node(return-from %rec (values nil nil)))(ecase (funcall compare key (%%key node))(:eq(let ((l (%%l node))(r (%%r node)))(unless (and l r)(return-from %rec(if #1=(or l r)(values #1# nil)(values nil t))))(multiple-value-bind (new-l removed balanced) (%remove-rightest l)(if (null removed);; 変更なし(values node t)(let ((new-node (%make-node :key (%%key removed):value (%%value removed):l new-l:r (%%r node))))(if balanced(values new-node t)(%balance new-node)))))))(:less(multiple-value-bind (l balanced) (%rec (%%l node))(let ((new-node (%update-node node :l l)))(if balanced(values new-node t)(%balance new-node)))))(:greater(multiple-value-bind (r balanced) (%rec (%%r node))(let ((new-node (%update-node node :r r)))(if balanced(values new-node t)(%balance new-node))))))))(%rec node)))(define-modify-macro insert! (key value &optional (compare '(function compare-default))) insert)(define-modify-macro remove! (key &optional (compare '(function compare-default))) remove)(defun keys (node)(mapcar #'car (dump-to-list node)))(defun vals (node)(mapcar #'cdr (dump-to-list node)))(defun count (node)(%cnt node))(defun predecessor (node key &optional (compare #'compare-default))(declare (optimize (speed 3) (safety 0))(function compare))(labels ((%rec (node)(when node(ecase (funcall compare key (%%key node))(:greater(or (%rec (%%r node))node))((:eq :less)(%rec (%%l node)))))))(let ((res (%rec node)))(if res(values (%%key res) (%%value res) t)(values nil nil nil)))))(defun successor (node key &optional (compare #'compare-default))(declare (optimize (speed 3) (safety 0))(function compare))(labels ((%rec (node)(when node(ecase (funcall compare key (%%key node))(:less(or (%rec (%%l node))node))((:eq :greater)(%rec (%%r node)))))))(let ((res (%rec node)))(if res(values (%%key res) (%%value res) t)(values nil nil nil)))))(defun nth-element (node n)(declare (optimize (speed 3) (safety 0))(fixnum n))(labels ((%rec (node k)(declare (fixnum k))(let ((l-cnt (%cnt (%%l node))))(declare (fixnum l-cnt))(cond((< k l-cnt)(%rec (%%l node)k))((= k l-cnt)node)(t(%rec (%%r node)(- k l-cnt 1)))))))(if (<= 0 n (the fixnum (1- (the fixnum (%cnt node)))))(let ((res (%rec node n)))(declare (node node))(values (%%key res) (%%value res) t))(values nil nil nil))))(defun rand-nth (node)(when node(nth-element node (random (count node)))))(defun ref (node key &optional (compare #'compare-default))(declare (optimize (speed 3) (safety 0))(function compare))(labels ((%rec (node)(when node(ecase (funcall compare key (%%key node))(:eq node)(:less (%rec (%%l node)))(:greater (%rec (%%r node)))))))(let ((res (%rec node)))(if res(values (%%key node) (%%value node) t)(values nil nil nil)))))(defun update (node key fn &optional (compare #'compare-default))(let ((current (ref node key compare)))(insert node key (funcall fn current) compare)))(defun make-avl-tree-from-list (key-fn value-fn list &optional (compare #'compare-default))(let ((res nil))(dolist (x list res)(avl:insert! res(funcall key-fn x)(funcall value-fn x)compare))))(define-modify-macro update! (key fn &optional (compare '(function compare-default))) update);;;;;; EOF;;;;;;;;; BOF;;;(defpackage randomized-heap(:use #:cl)(:nicknames #:rh)(:shadow #:count)(:export #:make-randomized-heap#:empty-p#:push!#:pop!#:peak#:count#:do-all-kvs#:prune!))(in-package #:randomized-heap)(eval-when (:compile-toplevel :load-toplevel :execute)(defvar *OPT*#+swank '(optimize (speed 3) (safety 2))#-swank '(optimize (speed 3) (safety 0) (debug 0))))(declaim (inline %make-node make-randomized-heap))(defstruct (node (:constructor %make-node)(:conc-name %n-))(key nil :type fixnum)(value nil :type t)(children (make-array 2 :element-type '(or null node):initial-element nil):type (simple-array (or null node) (2))))(defstruct (randomized-heap (:constructor make-randomized-heap (&optional (compare #'sb-impl::two-arg-<) (key-fn #'identity))))(root nil :type (or null node))(count 0 :type (integer 0 #.most-positive-fixnum))(comparator compare :type (function (fixnum fixnum) boolean))(key-fn key-fn :type (function (t) fixnum)))(defun count (heap)(randomized-heap-count heap))(declaim (inline %direction))(defun %direction ()(declare #.*OPT*)(random 2))(defun meld (l r comparator)(declare #.*OPT*((or null node) l r)((function (fixnum fixnum) boolean) comparator))(cond((or (null l)(null r))(or l r))((funcall comparator(%n-key l)(%n-key r));; l is root(let ((dir (%direction)))(setf (aref (%n-children l) dir)(meld (aref (%n-children l) dir)rcomparator))l))(t;; r is root(let ((dir (%direction)))(setf (aref (%n-children r) dir)(meld l(aref (%n-children r) dir)comparator))r))))(declaim (inline peak))(defun peak (heap)(declare #.*OPT*)(let ((root (randomized-heap-root heap)))(values (%n-value root)(%n-key root))))(defun empty-p (heap)(null (randomized-heap-root heap)))(declaim (inline pop! push!))(defun pop! (heap)(declare #.*OPT*)(when (empty-p heap)(error "heap is empty"))(decf (randomized-heap-count heap))(multiple-value-bind (value key)(peak heap)(let* ((children (%n-children (randomized-heap-root heap)))(l (aref children 0))(r (aref children 1)))(setf (randomized-heap-root heap)(meld lr(randomized-heap-comparator heap)))(values value key))))(defun push! (heap value)(declare #.*OPT*)(let ((key (funcall (randomized-heap-key-fn heap)value)))(incf (randomized-heap-count heap))(setf (randomized-heap-root heap)(meld (randomized-heap-root heap)(%make-node :key key:value value)(randomized-heap-comparator heap))))heap)(defmacro do-all-kvs ((key value heap) &body body &environment env)(let ((temp (gensym)))(multiple-value-bind (args argvs res setter accessor)(get-setf-expansion heap env)`(let ((,temp (make-randomized-heap (randomized-heap-comparator ,accessor)(randomized-heap-key-fn ,accessor))))(loop :until (empty-p ,accessor):do (multiple-value-bind (,value ,key)(pop! ,accessor)(progn ,@body)(push! ,temp ,value)))(let* (,@(mapcar #'list args argvs)(,(car res) ,temp)),setternil)))))(defun prune! (heap cnt)(let ((new-root nil)(comparator (randomized-heap-comparator heap)))(dotimes (_ cnt)(multiple-value-bind (v k) (pop! heap)(setf new-root(meld new-root(%make-node :key k :value v)comparator))))(setf (randomized-heap-root heap)new-root)));;;;;; EOF;;;;;;;;; Macros;;;(in-package #:cl-user)(defmacro do-iota ((var count &optional (start 0) (step 1)) &body body)(check-type step integer)(let* ((last (gensym))(terminate (if (plusp step) `(>= ,var ,last) `(<= ,var ,last))))`(let ((,last (+ ,start (the fixnum (* ,step ,count)))))(declare (fixnum ,last))(do((,var ,start (+ ,var ,step)))(,terminate(progn ,@body))))))(defmacro awhen (test &body forms)`(let ((it ,test))(when it,@forms)))(defmacro while (test &body body)`(loop while ,test do (progn ,@body)))(defmacro eval-always (&body body)`(eval-when (:compile-toplevel :load-toplevel :execute),@body));;;;;; I/O;;;(in-package #:cl-user)(declaim (inline println))(defun println (obj &optional (stream *standard-output*))#+sbcl (declare (sb-kernel:ansi-stream stream))(let ((*read-default-float-format* 'double-float))(prog1 obj(princ obj stream)(terpri stream))))(declaim (inline %read-byte))(defun %read-byte (&optional (stream *standard-input*))(declare (inline read-byte)#+(and sbcl (not swank)) (sb-kernel:ansi-stream stream))(the fixnum #+swank (char-code (read-char stream nil #\Nul))#-swank (read-byte stream nil #.(char-code #\Nul))))(declaim (inline read-fixnum))(defun read-fixnum (&optional (in *standard-input*) (byte-reader #'%read-byte));; Ref: https://competitive12.blogspot.com/2020/03/common-lisp.html;; partially modified(declare ((function (stream) (unsigned-byte 8)) byte-reader)(optimize (speed 3) (safety 0) (debug 0)))(let ((minus nil)(res 0))(declare (boolean minus)(fixnum res))(labels ((%byte->num (b)(the fixnum (- (the fixnum b) #.(char-code #\0))))(%digit-p (byte)(<= #.(char-code #\0) (the fixnum byte) #.(char-code #\9)))(%first-proc! ()(loop for byte of-type fixnum = (funcall byte-reader in)do (cond((%digit-p byte)(setf (the fixnum res) (%byte->num byte))(return))((= byte #.(char-code #\Nul))(error "EOF"))((= byte #.(char-code #\-))(setf minus t)))))(%rest-proc! ()(loop for byte of-type fixnum = (funcall byte-reader in)do (cond((%digit-p byte)(setf (the fixnum res) (the fixnum (+ (the fixnum (* res 10)) (%byte->num byte)))))(t (return))))))(declare (inline %byte->num %digit-p %first-proc! %rest-proc!))(%first-proc!)(%rest-proc!)(the fixnum (if minus (- res) res)))))(declaim (inline read-base-char))(defun read-base-char (&optional (stream *standard-input*))(code-char (%read-byte stream)))(defun read-line-fast (&optional (stream *standard-input*))#+(and (not swank) sbcl) (declare (sb-kernel:ansi-stream stream))(loop with buffer of-type base-string = (make-array 0 :element-type 'base-char :fill-pointer 0)for c of-type base-char = (read-base-char stream)until (or (eql c #\Newline)(eql c #\Nul))do (vector-push-extend c buffer)finally (return buffer)))(defun split (string &optional (separator #\space))(declare (base-char separator))(let ((pos (position separator string)))(if pos(cons (subseq string 0 pos)(split (subseq string (1+ pos))separator))(list string))))(declaim (inline parse-fixnum))(defun parse-fixnum (string)(with-input-from-string (in string)(read-fixnum in #f(the (unsigned-byte 8)(char-code (read-char % nil #\Nul nil))))))(declaim (inline read-times))(defun read-times (count &key (result-type 'list) (reader #'read-fixnum))(coerce (loop repeat count collect (funcall reader)) result-type))(defun unwrap (sequence);; e.g. (unwrap (list 1 2 3 4 5)) => "1 2 3 4 5"(let ((*standard-output* (make-string-output-stream :element-type 'base-char)))(let ((init nil))(declare (boolean init))(map nil(lambda (x)(when init(princ #\space))(setq init t)(princ x))sequence))(coerce (get-output-stream-string *standard-output*) 'simple-base-string)));;;;;; Body;;;(in-package #:cl-user)(defmacro %expander-body (form cases)`(ecase ,form,@(loop for (from . to) in casescollect `(,from ,to))))(defmacro define-ecase-expander (name assoc-list)`(defmacro ,name (form)`(%expander-body ,form ,',assoc-list)))(eval-always;; TODO wait(defconstant +grid-size+ 60)(defconstant +player-vital+ 1500)(sb-int:defconstant-eqx +char-int-assoc+'((#\. . 0)(#\# . 1)(#\S . 2)(#\G . 3)(#\K . 4)(#\J . 5)(#\F . 6)(#\E . 7))#'equalp)(sb-int:defconstant-eqx +move-dy-dx-assoc+'((:down . (1 . 0))(:up . (-1 . 0))(:left . (0 . -1))(:right . (0 . 1))#+nil (:wait . (0 . 0)))#'equalp)(sb-int:defconstant-eqx +dir-char-assoc+'((:down . #\D)(:up . #\U)(:left . #\L)(:right . #\R))#'equal)(sb-int:defconstant-eqx +moves+ (mapcar #'car +move-dy-dx-assoc+)#'equal)(sb-int:defconstant-eqx +dy-dx+ (mapcar #'cdr +move-dy-dx-assoc+)#'equalp)(defun swap-cons (xs)(cons (cdr xs) (car xs))))(deftype moves () `(member ,@'#.+moves+))(define-ecase-expander char->int-ecase #.+char-int-assoc+)(define-ecase-expander int->char-ecase #.(mapcar #'swap-cons +char-int-assoc+))(define-ecase-expander dir->char-ecase #.+dir-char-assoc+)(defun char->int (c)(char->int-ecase c))(defun int->char (int)(declare ((unsigned-byte 4) int)(optimize (speed 3) (safety 0)))(int->char-ecase int))(defun dir->char (dir)(declare (moves dir)(optimize (speed 3) (safety 0)))(dir->char-ecase dir))(defun move->dy-dx (move)"Returns (cons dy dx)"(cdr (assoc move +move-dy-dx-assoc+)));; Coord(eval-always(defconstant +each-coord-word-size+ 8))(eval-always(deftype coord () '(unsigned-byte #.(* +each-coord-word-size+ 2))))(declaim (inline y x))(defun y (c)(ldb (byte #.+each-coord-word-size+ 0)c))(defun x (c)(ldb (byte #.+each-coord-word-size+ #.+each-coord-word-size+)c))#+nil(defun valid-coord-p (c)(and (<= 0 (y c) (1- +grid-size+))(<= 0 (x c) (1- +grid-size+))))(declaim (inline make-coord))(defun make-coord (&key y x)(when (and (<= 0 y (1- +grid-size+))(<= 0 x (1- +grid-size+)))(dpb x(byte +each-coord-word-size+ +each-coord-word-size+)y)))#+nil(let ((c (make-coord :y 3 :x 1)))(values c (y c) (x c)))(declaim (inline next-coord))(defun next-coord (c dy dx)(make-coord :y (the fixnum (+ (y c) dy)):x (the fixnum (+ (x c) dx))))(deftype costs () '(simple-array single-float (#.+grid-size+ #.+grid-size+)))(deftype objs () '(simple-array (unsigned-byte 4) (#.+grid-size+ #.+grid-size+)))(defstruct (game-info (:conc-name %))"ゲーム中に変化しない情報をまとめる"(estimated-cost-to-goal nil :type costs)(estimated-cost-to-key nil :type costs)(key-pos nil :type coord)(objs nil :type objs :read-only t);; TODO use vector(finder-cycle-by-coord (make-hash-table) :type hash-table :read-only t)(finder-penalty nil :type fixnum))(defun estimated-cost-to-goal (game-info c)(aref (%estimated-cost-to-goal game-info) (y c) (x c)))(defun estimated-cost-to-key (game-info c)(aref (%estimated-cost-to-key game-info) (y c) (x c)))(defun obj-at (game-info c)(declare (optimize (speed 3) (safety 0))(fixnum c))(int->char (aref (%objs game-info) (y c) (x c))))(defun finder-active-p (game-info pos turn);; MEMO turnは1からスタートする(let ((finder-cycle (gethash pos (%finder-cycle-by-coord game-info))))(zerop (rem turn finder-cycle))))(defstruct (state (:conc-name %))(pos nil :type coord)(has-key (error "Need to specify value") :type boolean);; avl-tree of coord (shared with other boards);; TODO 削除操作がなければbloom filterで保持できるとうれしそう(visited nil :type t :read-only t)(destroyed-finders nil :type t :read-only t)(blocks nil :type t :read-only t);; positive fixnum(fire-amount 0 :type (integer 0 #.most-positive-fixnum))(jewel-amount 0 :type (integer 0 #.most-positive-fixnum))(elapsed-turn 0 :type (integer 0 #.most-positive-fixnum))(elapsed-vital 0 :type (integer 0 #.most-positive-fixnum)))(defun visitedp (state coord)(avl:ref (%visited state) coord))(defun %get-next-visited (state coord)(avl:insert (%visited state) coord t))(defun reachablep (state game-info coord);; coordのマスへ移動できる;; TODO moveを引数に取りたい(let ((c (obj-at game-info coord)))(and (not (avl:ref (%blocks state) coord))(or (find c ".SGKJF")(and (char= c #\E)(avl:ref (%destroyed-finders state) coord))))))(defun block-placeable-p (state game-info coord);; coordのマスにブロックを配置できる;; finder破壊後のマスにも置ける?(let ((c (obj-at game-info coord)))(and (char= c #\.)(null (avl:ref (%blocks state) coord)))))(defun block-removable-p (state game-info coord);; coordのマスのブロックを削除(declare (ignore game-info))(avl:ref (%blocks state) coord))(defun %find-obj (get-obj-at obj)(loop for y below +grid-size+for c = (loop for x below +grid-size+for c = (make-coord :y y :x x)for i = (funcall get-obj-at c)when (char= i obj)return c)when creturn it))(defun %make-est-cost-from-obj (objs start-obj finder-cycle-by-coord)(flet ((obj-at (c)(int->char (aref objs (y c) (x c)))))(let ((sc (%find-obj #'obj-at start-obj))(costs (make-array (list +grid-size+ +grid-size+) :element-type 'single-float:initial-element most-positive-single-float))(heap (rh:make-randomized-heap #'< #'first)))(assert sc)(rh:push! heap (list 0.0 sc))(while (not (rh:empty-p heap))(destructuring-bind (cost c) (rh:pop! heap)(when (<= cost (aref costs (y c) (x c)))(setf (aref costs (y c) (x c))cost)(loop for (dy . dx) in +dy-dx+for ny = (+ (y c) dy)for nx = (+ (x c) dx)for nc = (make-coord :y ny :x nx)when (and nc(not (find (obj-at nc)"#E")))do (let ((penalty 0))(loop for (dy . dx) in +dy-dx+ unless (= dy dx 0) do;; ncは即値(let ((c nc))(while c(cond((char= (obj-at c) #\W)(return))((char= (obj-at c) #\E);; 一番近くの探知機で止まる(let ((cycle (gethash c finder-cycle-by-coord)))(assert cycle);; TODO いい感じの係数をかける(incf penalty (float (/ cycle)))(return)))(t(setf c (next-coord c dy dx)))))))(let ((new-cost (+ cost penalty)))(when (< new-cost (aref costs (y nc) (x nc)))(setf (aref costs (y nc) (x nc))new-cost)(rh:push! heap (list new-cost nc)))))))));; (break)costs)))(defun read-game-info ()(destructuring-bind (n d h) (mapcar #'parse-fixnum (split (read-line)))(declare (ignore n h))(let ((objs (make-array '(#.+grid-size+ #.+grid-size+) :element-type '(unsigned-byte 4))))(dotimes (y +grid-size+)(let ((s (read-line)))(dotimes (x +grid-size+)(setf (aref objs y x)(char->int (char s x))))))(let ((m (read))(finder-cycle-by-coord (make-hash-table)))(dotimes (_ m)(destructuring-bind (y x dd) (mapcar #'parse-fixnum (split (read-line)))(setf (gethash (make-coord :y y :x x) finder-cycle-by-coord)dd)))(make-game-info :estimated-cost-to-goal (%make-est-cost-from-obj objs #\G finder-cycle-by-coord):estimated-cost-to-key (%make-est-cost-from-obj objs #\K finder-cycle-by-coord):key-pos (%find-obj #f(int->char (aref objs (y %) (x %))) #\K):objs objs:finder-cycle-by-coord finder-cycle-by-coord:finder-penalty d)))))(defun %find-nearest-finders (game-info block-exist-p finder-destroyed-p pos &optional (directions +dy-dx+))(declare (optimize (speed 3) (safety 0))(function block-exist-p finder-destroyed-p)(fixnum pos))(let ((res nil))(loop for (dy . dx) of-type (fixnum . fixnum) in directions do(let ((c pos))(declare ((or null fixnum) c))(while c(cond((char= (obj-at game-info c)#\W)(return))((funcall block-exist-p c)(return))((and (char= (obj-at game-info c) #\E)(not (funcall finder-destroyed-p c)));; 一番近くの探知機で止まる(push c res)(return))(t(setf c (next-coord c dy dx)))))))(nreverse res)));; TODO 他のアクションと共通の部分は切り出すとよさそう?→バグらせそうなのでやめたほうがいい;; TODO 体力消費、ターン消費?(アイテム取得は移動時だけ)(defun do-nothing (state game-info)(with-accessors ((pos %pos)(visited %visited)(has-key %has-key)(dfs %destroyed-finders)(bs %blocks)(fa %fire-amount)(ja %jewel-amount)(ev %elapsed-vital)(et %elapsed-turn)) state(let* ((nearest-finders (%find-nearest-findersgame-info;; block-exist-p(lambda (c)(avl:ref bs c));; finder-destroyed-p(lambda (c)(avl:ref dfs c))pos))(nev (+ ev(* (length (remove-if-not #f(finder-active-p game-info % (1+ et))nearest-finders))(%finder-penalty game-info))1)));; #>(pos new-pos)(make-state :pos pos:has-key has-key:visited visited:destroyed-finders dfs:blocks bs:fire-amount fa:jewel-amount ja:elapsed-vital nev:elapsed-turn (1+ et)))))(defun move (state game-info move)(with-accessors ((pos %pos)(visited %visited)(has-key %has-key)(dfs %destroyed-finders)(bs %blocks)(fa %fire-amount)(ja %jewel-amount)(ev %elapsed-vital)(et %elapsed-turn)) state(destructuring-bind (dy . dx) (move->dy-dx move)(let* ((ny (+ (y pos) dy))(nx (+ (x pos) dx))(new-pos (make-coord :y ny:x nx))(nobj (obj-at game-info new-pos))(new-visited (%get-next-visited state new-pos))(nfa (if (char= nobj #\F)(1+ fa)fa))(nja (if (and (char= nobj #\J)(not (visitedp state new-pos)))(1+ ja)ja))(nearest-finders (%find-nearest-findersgame-info;; block-exist-p(lambda (c)(avl:ref bs c));; finder-destroyed-p(lambda (c)(avl:ref dfs c))new-pos))(nev (+ ev(* (length (remove-if-not #f(finder-active-p game-info % (1+ et))nearest-finders))(%finder-penalty game-info))1)));; #>(pos new-pos)(make-state :pos new-pos:has-key (or has-key (char= (obj-at game-info new-pos)#\K)):visited new-visited:destroyed-finders dfs:blocks bs:fire-amount nfa:jewel-amount nja:elapsed-vital nev:elapsed-turn (1+ et))))))(defun place-block (state game-info place-pos)(with-accessors ((pos %pos)(visited %visited)(hk %has-key)(dfs %destroyed-finders)(bs %blocks)(fa %fire-amount)(ja %jewel-amount)(ev %elapsed-vital)(et %elapsed-turn)) state(let* (;; 空のマスでないといけない(nbs (avl:insert bs place-pos t))(nearest-finders (%find-nearest-findersgame-info;; block-exist-p(lambda (c)(avl:ref nbs c));; finder-destroyed-p(lambda (c)(avl:ref dfs c))pos))(nev (+ ev(* (length nearest-finders)(%finder-penalty game-info))1)))(make-state :pos pos:visited visited:has-key hk:destroyed-finders dfs:blocks nbs:fire-amount fa:jewel-amount ja:elapsed-vital nev:elapsed-turn (1+ et)))))(defun destroy-block (state game-info place-pos)(with-accessors ((pos %pos)(visited %visited)(has-key %has-key)(dfs %destroyed-finders)(bs %blocks)(fa %fire-amount)(ja %jewel-amount)(ev %elapsed-vital)(et %elapsed-turn)) state(let* ((nbs (avl:remove bs place-pos))(nearest-finders (%find-nearest-findersgame-info;; block-exist-p(lambda (c)(avl:ref nbs c));; finder-destroyed-p(lambda (c)(avl:ref dfs c))pos))(nev (+ ev(* (length (remove-if-not #f(finder-active-p game-info % (1+ et))nearest-finders))(%finder-penalty game-info))1)))(make-state :pos pos:visited visited:has-key has-key:destroyed-finders dfs:blocks nbs:fire-amount fa:jewel-amount ja:elapsed-vital nev:elapsed-turn (1+ et)))))(defun destroy-finders-by-fire (state game-info dir)(with-accessors ((pos %pos)(has-key %has-key)(visited %visited)(dfs %destroyed-finders)(bs %blocks)(fa %fire-amount)(ja %jewel-amount)(ev %elapsed-vital)(et %elapsed-turn)) state(let* ((destroyed-finders (%find-nearest-findersgame-info;; block-exist-p(lambda (c)(avl:ref bs c));; finder-destroyed-p(lambda (c)(avl:ref dfs c))pos(list (move->dy-dx dir))))(ndfs (reduce (lambda (dfs c)(avl:insert dfs c t))destroyed-finders:initial-value dfs))(nearest-finders (%find-nearest-findersgame-info;; block-exist-p(lambda (c)(avl:ref bs c));; finder-destroyed-p(lambda (c)(avl:ref ndfs c))pos))(nfa (1- fa))(nev (+ ev(* (length (remove-if-not #f(finder-active-p game-info % (1+ et))nearest-finders))(%finder-penalty game-info))1)))(assert (>= nfa 0))(make-state :pos pos:visited visited:destroyed-finders ndfs:has-key has-key:blocks bs:fire-amount nfa:jewel-amount ja:elapsed-vital nev:elapsed-turn (1+ et)))))(defun make-init-state (game-info)(let* ((sp (%find-obj #f(obj-at game-info %) #\S))(visited (avl:make-avl-tree-from-list #'identity (constantly t) (list sp))))(make-state :pos sp:has-key nil:visited visited:destroyed-finders nil:blocks nil)))(defun goal-state-p (state game-info)(and (%has-key state)(char= (obj-at game-info (%pos state))#\G)))(defun validate-state (state game-info);; TODO 必要そうなものを適宜足す(unless (reachablep state game-info (%pos state))(error "~a is not unreachable" (%pos state)))(unless (visitedp state (%pos state))(error "Player is at ~a, but visited is not marked" (%pos state)))(awhen (loop for c in (avl:keys (%destroyed-finders state))for obj = (obj-at game-info c)when (char/= obj#\E)return (cons c obj))(error "~a is contained in destroyed-finders, but is actually ~a" (car it) (cdr it)))(awhen (loop for c in (avl:keys (%blocks state))for obj = (obj-at game-info c)when (char/= obj #\.)return (cons c obj))(error "~a is contained in blocks, so supposed to be empty block, but is actually ~a" (car it) (cdr it))))(defconstant +dist-penalty-factor+ -1.0)(defconstant +est-cost-factor+ 5.0d0)(defun %eval-dist-to-goal (state game-info)(- (round (estimated-cost-to-goal game-info (%pos state)))))(defun %eval-dist-to-key (state game-info)(let ((est-cost-from-here-to-key (round (estimated-cost-to-key game-info (%pos state)))));; 最短で取りに行きたい(if (zerop est-cost-from-here-to-key)(%elapsed-vital state)(- est-cost-from-here-to-key))))(defstruct (node (:conc-name %));; TODO hash(parent nil :type (or null node))(state nil :type state)(score nil :type fixnum)(last-action nil :type (or null cons)))(defconstant +heap-size-threshold+ 200)(defun chokudai-search (game-info eval-state goal-state-p&keyinit-statestime-limitelapsed-vital-minelapsed-vital-max)(declare (function eval-state goal-state-p))(let* ((n (- elapsed-vital-max elapsed-vital-min))(states (make-array (1+ n)))(start (get-internal-real-time))(goal-candidates (rh:make-randomized-heap #'> #'%score)))(dotimes (elapsed (1+ n))(setf (aref states elapsed)(rh:make-randomized-heap #'> #'%score)))(dolist (init-state init-states)(rh:push! (aref states (- (%elapsed-vital init-state)elapsed-vital-min))(make-node :state init-state:score (funcall eval-state init-state game-info))));; 時間いっぱいchokudaiサーチ(loop named search for turn from 1 do(loop for elapsed-vital from elapsed-vital-min below elapsed-vital-max for e-index = (- elapsed-vital elapsed-vital-min) do;; #>elapsed-vital(when (> (/ (float (- (get-internal-real-time)start))internal-time-units-per-second)time-limit)#>turn(return-from search))(unless (rh:empty-p #1=(aref states e-index))(let ((node (rh:pop! #1#)))(labels ((%treat-next (next-state action)#+(and swank) (validate-state next-state game-info)(let* ((next-node (make-node :parent node:state next-state:score (funcall eval-state next-state game-info):last-action action))(nev (%elapsed-vital next-state)))(when (<= nev elapsed-vital-max);; #>(nev elapsed-vital-min elapsed-vital-max)(cond((funcall goal-state-p next-state game-info)(rh:push! goal-candidates next-node))(t(rh:push! (aref states (- nev elapsed-vital-min))next-node)(when (= (rh:count (aref states (- nev elapsed-vital-min)))+heap-size-threshold+)(rh:prune! (aref states (- nev elapsed-vital-min))(ash +heap-size-threshold+ -1)))))))))(declare (inline %treat-next))(%treat-next (do-nothing (%state node) game-info)(cons :wait nil))(loop for (dir . (dy . dx)) in +move-dy-dx-assoc+ do(let ((nc (next-coord (%pos (%state node)) dy dx)))(when nc;; 移動(when (reachablep (%state node) game-info nc)(%treat-next (move (%state node)game-infodir)(cons :move dir)));; ブロックを配置(when (block-placeable-p (%state node) game-info nc)(%treat-next (place-block (%state node)game-infonc)(cons :place-block dir)));; ブロックを破壊(when (block-removable-p (%state node) game-info nc)(%treat-next (destroy-block (%state node)game-infonc)(cons :destroy-block dir)));; ファイヤー#+nil(when (plusp (%fire-amount (%state node)))(%treat-next (destroy-finders-by-fire (%state node) game-info dir)(cons :fire dir)))))))))));; moveを復元してリストとして返す#>((rh:count goal-candidates))(let ((best-node (unless (rh:empty-p goal-candidates)(rh:pop! goal-candidates)))(res nil))(assert best-node)#>((%score best-node))(while (%parent best-node)(push (%last-action best-node)res)(setf best-node (%parent best-node)))res)))(defun print-res (res)(princ(with-output-to-string (*standard-output*)(loop for (act . dir) in resdo (println(ecase act(:wait "S")(:move(format nil"M ~a"(dir->char dir)))((:place-block :destroy-block)(format nil "B ~a" (dir->char dir)))(:fire(format nil "F ~a" (dir->char dir)))))))))(defun apply-action (state game-info action dir)(ecase action(:wait (do-nothing state game-info))(:move (move state game-info dir))(:place-block(destructuring-bind (dy . dx) (move->dy-dx dir)(place-block state game-info (next-coord (%pos state) dy dx))))(:destroy-block(destructuring-bind (dy . dx) (move->dy-dx dir)(destroy-block state game-info (next-coord (%pos state) dy dx))))(:fire(destroy-finders-by-fire state game-info dir))))(defun apply-actions (state game-info actions)(reduce (lambda (acc act)(destructuring-bind (act-type . dir) act(apply-action acc game-info act-type dir)))actions:initial-value state))(defconstant +find-key-time-limit+ 0.3)(defconstant +earn-coin-time-limit+ 2.0)(defconstant +find-goal-time-limit+ 0.5)#+nil(defun eval-state (state game-info);; TODO ゴールに辿りつくのが難しい場合ほど大きなペナルティ;; TODO 残り体力が少なくなるほど傾斜を強くする?(cond((not (%has-key state))(- (%eval-for-dist-to-key state game-info)100000));; 残り100ターンを切ったらゴールを最優先して目指す((< (- +player-vital+ (%elapsed-vital state))400)(+ (%eval-for-dist-to-goal state game-info)(* 100000 (%jewel-amount state))))(t(%jewel-amount state))))(declaim (notinline main))(defun main ()(let* ((game-info (read-game-info))(init-state (make-init-state game-info))(best-moves-to-key (chokudai-searchgame-info#'%eval-dist-to-key(lambda (state game-info)(declare (ignore game-info))(%has-key state)):init-states (list init-state):time-limit +find-key-time-limit+:elapsed-vital-min 0:elapsed-vital-max (round (* (estimated-cost-to-key game-info (%pos init-state))10))))(next-init-state (apply-actions init-state game-info best-moves-to-key))(elapsed-vital-to-key (%elapsed-vital next-init-state))(earn-end (max (1+ elapsed-vital-to-key)(round (- +player-vital+(* (estimated-cost-to-goal game-info (%key-pos game-info))10)))))(best-earn-moves (chokudai-searchgame-info(lambda (state game-info)(declare (ignore game-info))(%jewel-amount state))(lambda (state game-info)(declare (ignore game-info))(<= (abs (- (%elapsed-vital state)earn-end))30)):init-states (list next-init-state):time-limit +earn-coin-time-limit+:elapsed-vital-min (%elapsed-vital next-init-state):elapsed-vital-max earn-end))(next-init-state (apply-actions next-init-state game-info best-earn-moves))(_ #>next-init-state)(best-back-moves (chokudai-searchgame-info#'%eval-dist-to-goal#'goal-state-p:init-states (list next-init-state):time-limit +find-goal-time-limit+:elapsed-vital-min (%elapsed-vital next-init-state):elapsed-vital-max +player-vital+))(res (concatenate 'listbest-moves-to-keybest-earn-movesbest-back-moves)))#>(elapsed-vital-to-key earn-end)(print-res res)))#-swank (main);;;;;; Debug;;;#+swank(defun run ()(let ((*standard-input*(make-string-input-stream(with-output-to-string (*standard-output*)(run-program(truename "~/.roswell/bin/copy-or-paste")'():output *standard-output*)))))(main)));; Raise error on warning at compile time#+(and sbcl (not swank))(eval-when (:compile-toplevel)(when (or (plusp sb-c::*compiler-warning-count*)sb-c::*undefined-warnings*)(error "compiler-error-count:~a, undefined warnings:~a"sb-c::*compiler-warning-count*sb-c::*undefined-warnings*)))#+swank(defun run-sample (infile outfile &optional (out *standard-output*))(with-open-file (*standard-input* infile :direction :input)(with-open-file (*standard-output* outfile :direction :output:if-exists :supersede)(main))(sb-ext:run-program "/usr/bin/java" (list "Judge" infile outfile):output out:error *error-output*)))#+swank (declaim (notinline run-sample-zero))#+swank(defun run-sample-zero ()(gc :full t)(with-input-from-string (*standard-input* "60 3 1500.......JJ....J#..#E#....EE.J..E...E#J.....#.#EE......#..J.J##E#.....##J..JE....E..#....J.........#......#..#J.........#..J.J.#.#....J.#..#........J#...#J#.KJE.J.E.#J.#....#......J.J..E..#.E#.......E........JEJ.....F..##..............#...J.J..J.......JE...#......J.#.#..#J#JFJ.......E..#..#....E.....J#..J.....EE....J........E............##.E#.E.#JJ..........E....#......J.J..J#...#...#.#..JE#....##E...#F.#....E....#E#...JJ.....###.J.EE...J...#E#E#...E.E.....#E......J..#...#....#E.E.......#JF.J.J.E.##E#...EE..J....F..#.#J#..E#J..E..J...#F##....F.#F#.E.#.EJ...J#E..#..#.J.......E...J....#..#..#....S.E...E...J..J#........#...E.E.......#.....J..J.....E..E....#.................#J#.....F...JE.#......##.........JJ.J....#.E..J...E##..#.J...#...#.E....##...#.....EEJJJ.##.#.E.....E#.E#.F.#.......JF..#..E#......EJ.....#.#.E.##..JJ.......E.J..EJE..#E....E..E.J#.E...E...J...#J#J.#.E.....E..#E#.E..EF###..E....J.#..J#....#..EE#.E...E.J.J...E#E#.J..J...E..........J#.....#..J.#JF.#....E..#EE..E..#.......E.........#..J..#..J.F#.EF.......E.J.E............#.........#...........E...#.#J..F.....JJ...E#..E.#....#.E#...#...F.J.#.E.F.#.....J.....#EJ.E###......#.E.J.E...#E..#..E...#.....#..#.#......F#.E.J..#.#E....JEEE..EE.#.E#..#JJ............#J.E.#E..J........E....#.E..E....EJ...J........#..J..J.#E#.#...#.E....#E.#E.#.#E..#..#...#E#.E.....#J.E.#.#.J.J...E.JJ#J...#.J...##....J.J.......#.....F....#..J#J..#....#.E...EJ#..#...#.#F#F.EE#..#.....#E.EJ#..#....#.#E..#.J.#.#......EJ..J.............#...#....#.E....##EEEE.....JJ..J.#..#..#.E....#J#E#E...E......#JJ#.E..E.#J#E..##..JJ.#.JE.....E.##.E....E#.....#E.#J..#....JJ..#.#.....E.#.E....#E..E..JEJ..JE..#F#..#.#.#..E#J#......#.E.EJ#..F.E.J....#....J.JE.J#...JF.E..JE.J..#....F.F#..E.##JJE....#F.EE..F.EJF...E...EE#..J.#F.F#....JE#J.......E#F.....E.....J...##E##EJ#.E....E......JJ..F##J..E...J..JE..J.EJ..E.....E.EE.#EE#...E...JE.#.#..E..#.J....E..#.#.J#.E.E.#.#E.##.#...#...E.J...G##..EF.J#J.J....E.F.......E#.J...#..E...##........#.E.#......J.#..J...E..EJ..E......J....E...#.#.F#E.EE..#J.E......E........E.E..#FJ.E#.F..E#.#...........F....J..#.##.##..EFJ.E....E.#....##.JE...EE.E.#E#..JJEF....#J.#....J.JE..J.....J..#E...........JJ....###....J#................J..#J.JJ#JE.EJ..JE.#EJE..#..E..J..#.J.#.....J.J.....#EJJ.E#.E..#E.......E..##.#J......#....#...#....J.J.E#J.E##.J....EE.#..E..##J..E....E..E.F.#E....E.....J.#.#.EJ.#.#.J.#...JJ##..#J.....#J.EJ.....#J.E#......#..E..#..#...J#J....#.E.J......#F.#.E.EJ..E...#.....J.E..#.#......J...#.JE.#.E...#..E..E.J.E..#.E...#....#EJ...##.J..J.J...JEJEJ...#.##.#.EE.F...F#.......E.E...#.....J....#F..JJ....J##.......F...#..#E....#JJJE.E.J##.E..J...F#J#.#....J..#......EJ.#....EE.#...E....E...#.E.J.E...JEE.E..J..#...#...#.#....#...E.#.E..E.E..F.E.FEE...............F..#.E#.E.JJ.....E#EJE#....##....#.#.F..#J..#E...#...E.#..##EJ#.#...F....#....#..........E.E.FE.#E......#..#EE..#...#EE....FE..#..JJ#J..EE...J........J#.E..E..J..E.#...##......J..J..........##...#...JJF#J....F....#.....#E.......EJ.........J.#..........J.#J.....J....##J..#..JJ.#..#.#.#...J.JE##E.JJ....E#.#.E...#......EE.....JE..........J.J..J#...#.#..#F..#..J..E...#.E...E..E.F.E#....J....E.#.E.JJ..J.J.J.#.##.....J.E..J.......##E.....E#EJJ.##.......E.##....EE......E...FE.#.....E.J##..J..#E#J#......J#......#.#.J....E.#..E..#E.##.#.###......#....#E#.#J...E.#.JE.#.J...#.....#....J..EE.##EE#..##.......##E..#.#......#.J.J...E#.E...JE#......#..J.....J#JF..#E.EJ.J.....J....#...JJ...E......#E.J..##.....#.J.#..#E.E..#.....##..J..E#E.......J#.....EE.J..##...F.....J.FJ#.E........E........#.J.E....J.E.J...E.#..E........##..E....#J..#.#..J...#...E#E..3740 18 50 24 50 25 20 30 30 34 20 45 30 46 41 1 31 14 51 19 22 37 52 41 53 3 33 8 43 17 33 27 34 11 24 42 44 53 25 9 45 10 25 24 35 40 55 43 25 58 56 30 26 38 56 50 56 56 57 14 27 15 57 24 57 26 47 31 57 33 47 40 38 0 58 2 58 18 58 22 38 27 38 28 58 46 28 51 59 12 39 16 39 23 59 39 410 1 510 5 210 26 510 28 310 51 410 54 311 30 212 0 412 7 412 24 412 40 512 41 412 51 512 57 413 0 413 20 213 28 213 39 413 54 213 59 514 1 514 5 414 10 414 13 514 18 214 22 414 37 214 43 414 47 414 50 214 53 315 0 315 19 315 20 415 23 215 27 315 35 215 37 315 47 516 19 416 23 216 24 516 27 216 38 517 2 517 11 417 15 517 50 318 11 518 15 318 24 318 39 518 56 418 59 519 11 519 15 519 20 219 26 419 51 419 59 420 5 420 6 420 7 420 10 320 11 420 15 420 37 520 40 420 52 220 59 321 2 221 7 321 30 521 39 321 45 321 48 221 53 422 4 422 7 222 16 422 28 223 25 323 29 223 45 423 46 523 57 423 59 424 12 324 28 524 57 225 4 225 5 325 6 425 7 225 27 425 35 525 37 325 41 325 53 325 56 426 1 526 14 226 20 326 25 326 30 326 38 527 1 227 5 427 11 227 14 327 18 227 23 227 38 327 50 227 52 227 59 528 14 228 24 528 28 228 44 328 50 328 58 428 59 329 4 229 10 529 14 429 15 229 31 329 41 329 49 430 1 430 4 330 8 230 13 530 30 330 38 430 43 330 47 330 53 330 55 330 56 230 59 231 0 531 5 331 10 231 17 531 27 431 37 231 39 331 44 431 57 432 8 332 20 332 30 532 40 232 56 533 14 333 17 433 21 333 33 333 43 433 45 333 46 433 52 533 59 534 8 434 10 434 17 234 23 534 55 534 59 535 4 235 15 335 19 535 20 235 22 535 25 235 31 535 48 236 1 436 54 336 56 237 1 537 4 237 6 337 12 437 37 537 41 537 44 237 48 237 56 238 28 238 32 338 41 538 42 538 47 538 55 239 0 439 3 239 8 239 13 539 25 339 54 340 4 240 15 340 34 440 48 540 50 440 54 441 6 441 25 441 29 441 36 541 39 441 43 441 48 441 58 442 16 242 18 342 30 542 31 442 46 242 48 243 31 243 40 243 42 243 48 544 15 444 23 344 24 544 30 244 35 244 41 544 45 444 50 244 51 344 53 345 18 345 22 545 25 545 27 245 32 345 35 445 36 245 57 446 0 446 9 546 11 246 13 446 37 346 45 346 52 247 21 247 23 447 26 247 29 547 40 247 41 347 49 347 50 447 56 548 8 348 9 248 25 548 28 448 34 249 32 549 40 550 43 250 46 550 54 550 59 351 10 451 11 351 18 251 54 452 0 452 4 452 7 352 11 252 22 252 26 252 49 353 2 353 8 453 10 253 23 453 31 353 32 353 39 453 44 253 52 254 3 354 30 454 35 454 39 455 1 355 9 555 14 455 36 255 37 555 41 455 42 255 57 356 17 556 20 356 25 356 49 456 51 457 14 257 22 257 42 557 44 358 0 258 2 458 17 258 18 458 40 258 49 459 2 459 9 459 15 359 20 359 33 259 55 559 57 2")(main)))