import Ġjava . util .* Ċ import Ġjava . io .* Ċ import Ġkotlin . math .* Ċ Ċ const Ġval ĠSEARCH DEPTH Ġ= Ġ 7 Ċ const Ġval ĠSPE ED LIMIT Ġ= Ġ 1 0 0 0 Ċ const Ġval Ġsearch Depth Ġ= ĠSEARCH DEPTH Ċ const Ġval Ġspeed Limit Squared Ġ= ĠSPE ED LIMIT Ġ* ĠSPE ED LIMIT Ċ var Ġnext Seq Ġ= Ġ 1 Ċ Ċ data Ġclass ĠInt Vec ( val Ġx Ġ: ĠInt , Ġval Ġy Ġ: ĠInt ) Ġ{ ĊĠ Ġoperator Ġfun Ġplus ( v Ġ: ĠInt Vec ) Ġ: ĠInt Vec Ġ{ ĊĠĠĠ Ġreturn ĠInt Vec ( x Ġ+ Ġv . x , Ġy Ġ+ Ġv . y ) ĊĠ Ġ} ĊĠ Ġoperator Ġfun Ġcompare To ( other Ġ: ĠInt Vec ) Ġ: ĠInt Ġ{ ĊĠĠĠ Ġreturn Ġif Ġ( y Ġ== Ġother . y ) Ġother . x Ġ- Ġx Ġelse Ġy Ġ- Ġother . y ĊĠ Ġ} Ċ } Ċ Ċ data Ġclass ĠRace Course ( val Ġthink Time Ġ: ĠInt , Ġval Ġstep Limit Ġ: ĠInt , Ġval Ġwidth Ġ: ĠInt , Ġval Ġlength Ġ: ĠInt , Ġval Ġvision Ġ: ĠInt ) Ġ{ ĊĠ Ġconstructor ( input Ġ: Ġjava . util . Scanner ) Ġ: this ( input . nextInt (), Ġinput . nextInt (), Ġinput . nextInt (), Ġinput . nextInt (), Ġinput . nextInt ()) Ġ{} Ċ } Ċ Ċ fun Ġadd S quares ( x Ġ: ĠInt , Ġy 0 Ġ: ĠInt , Ġy 1 Ġ: ĠInt , Ġsquares Ġ: ĠMutable List < Int Vec >) Ġ{ ĊĠ Ġfor Ġ( y Ġin Ġ( if Ġ( y 1 Ġ> Ġy 0 ) Ġy 0 .. y 1 Ġelse Ġy 0 Ġdown To Ġy 1 )) Ġsquares . add ( Int Vec ( x , Ġy )) Ċ } Ċ Ċ data Ġclass ĠMovement ( val Ġfrom Ġ: ĠInt Vec , Ġval Ġto Ġ: ĠInt Vec ) Ġ{ ĊĠ Ġfun Ġtouched S quares () Ġ: ĠMutable List < Int Vec > Ġ{ ĊĠĠĠ Ġval Ġr Ġ: ĠMutable List < Int Vec > Ġ= Ġmutable ListOf () ĊĠĠĠ Ġif Ġ( to . x Ġ== Ġfrom . x ) Ġadd S quares ( from . x , Ġfrom . y , Ġto . y , Ġr ) ĊĠĠĠ Ġelse Ġ{ ĊĠĠĠĠĠ Ġval Ġa Ġ: ĠDouble Ġ= Ġ( to . y Ġ- Ġfrom . y ). toDouble () Ġ/ Ġ( to . x Ġ- Ġfrom . x ). toDouble () ĊĠĠĠĠĠ Ġval Ġs gn x Ġ= Ġif Ġ( from . x Ġ< Ġto . x ) Ġ 1 Ġelse Ġ- 1 ĊĠĠĠĠĠ Ġvar Ġy 1 Ġ= Ġa Ġ* Ġs gn x Ġ/ Ġ 2 . 0 Ġ+ Ġfrom . y Ġ+ Ġ 0 . 5 ĊĠĠĠĠĠ Ġvar Ġiy 1 Ġ= Ġ( if Ġ( to . y Ġ> Ġfrom . y ) Ġfloor ( y 1 ) Ġelse Ġceil ( y 1 ) Ġ- Ġ 1 ). toInt () ĊĠĠĠĠĠ Ġadd S quares ( from . x , Ġfrom . y , Ġiy 1 , Ġr ) ĊĠĠĠĠĠ Ġfor Ġ( x Ġin Ġ( if Ġ( sg nx Ġ> Ġ 0 ) Ġ( from . x Ġ+ Ġs gn x ) .. ( to . x Ġ- Ġ 1 ) Ġelse Ġ( from . x Ġ+ Ġs gn x ). down To ( to . x Ġ+ Ġ 1 ))) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġy 0 Ġ= Ġa Ġ* Ġ( x Ġ- Ġfrom . x Ġ- Ġs gn x Ġ/ Ġ 2 . 0 ) Ġ+ Ġfrom . y Ġ+ Ġ 0 . 5 ĊĠĠĠĠĠĠĠ Ġy 1 Ġ= Ġa Ġ* Ġ( x Ġ- Ġfrom . x Ġ+ Ġs gn x Ġ/ Ġ 2 . 0 ) Ġ+ Ġfrom . y Ġ+ Ġ 0 . 5 ĊĠĠĠĠĠĠĠ Ġval Ġiy 0 Ġ= Ġ( if Ġ( to . y Ġ> Ġfrom . y ) Ġceil ( y 0 ) Ġ- Ġ 1 Ġelse Ġfloor ( y 0 )). toInt () ĊĠĠĠĠĠĠĠ Ġiy 1 Ġ= Ġ( if Ġ( to . y Ġ> Ġfrom . y ) Ġfloor ( y 1 ) Ġelse Ġceil ( y 1 ) Ġ- Ġ 1 ). toInt () ĊĠĠĠĠĠĠĠ Ġadd S quares ( x , Ġiy 0 , Ġiy 1 , Ġr ) ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġval Ġy 0 Ġ= Ġa Ġ* Ġ( to . x Ġ- Ġfrom . x Ġ- Ġs gn x Ġ/ Ġ 2 . 0 ) Ġ+ Ġfrom . y Ġ+ Ġ 0 . 5 ĊĠĠĠĠĠ Ġval Ġiy 0 Ġ= Ġ( if Ġ( to . y Ġ> Ġfrom . y ) Ġceil ( y 0 ) Ġ- Ġ 1 Ġelse Ġfloor ( y 0 )). toInt () ĊĠĠĠĠĠ Ġadd S quares ( to . x , Ġiy 0 , Ġto . y , Ġr ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġr ĊĠ Ġ} Ċ } Ċ Ċ data Ġclass ĠPlayer State ( val Ġposition Ġ: ĠInt Vec , Ġval Ġvelocity Ġ: ĠInt Vec ) Ġ{ ĊĠ Ġconstructor Ġ( input Ġ: Ġjava . util . Scanner ) Ġ: Ġthis ( Int Vec ( input . nextInt (), Ġinput . nextInt ()), ĠInt Vec ( input . nextInt (), Ġinput . nextInt ())) Ġ{} ĊĠ Ġoperator Ġfun Ġcompare To ( other Ġ: ĠPlayer State ) Ġ: ĠInt Ġ{ ĊĠĠĠ Ġval Ġc 1 Ġ= Ġposition . compareTo ( other . position ) ĊĠĠĠ Ġreturn Ġif Ġ( c 1 Ġ== Ġ 0 ) Ġvelocity . compareTo ( other . velocity ) Ġelse Ġc 1 ĊĠ Ġ} Ċ } Ċ Ċ data Ġclass ĠRace Info ( val Ġstep Number Ġ: ĠInt , Ġval Ġtime Left Ġ: ĠInt , Ġval Ġme Ġ: ĠPlayer State , Ġval Ġopponent Ġ: ĠPlayer State , Ġval Ġsquares Ġ: ĠList < List < Int >>) Ġ{ ĊĠ Ġconstructor ( input Ġ: Ġjava . util . Scanner , Ġcourse Ġ: ĠRace Course ) ĠĊĠĠĠĠ Ġ: this ( input . nextInt (), Ġinput . nextInt (), ĠPlayer State ( input ), ĊĠĠĠĠĠĠĠĠĠĠ ĠPlayer State ( input ), ĊĠĠĠĠĠĠĠĠĠĠ ĠArray ( course . length , Ġ{ Array ( course . width , Ġ{ input . nextInt ()} ). asList ()} ). asList ()) Ġ{} Ċ } Ċ Ċ data Ġclass ĠC andidate ( val Ġcourse Ġ: ĠRace Course , Ġval Ġstep Ġ: ĠInt , Ġval Ġstate Ġ: ĠPlayer State , Ġval Ġfrom Ġ: ĠC andidate ?, Ġval Ġhow Ġ: ĠInt Vec ) Ġ: ĠComparable < Candidate > Ġ{ ĊĠ Ġval Ġseq Ġ= Ġnext Seq ĊĠ Ġinit Ġ{ ĊĠĠĠ Ġnext Seq Ġ+= Ġ 1 ĊĠ Ġ} ĊĠ Ġval Ġgo aled Ġ= Ġstate . position . y Ġ>= Ġcourse . length ĊĠ Ġval Ġgoal Time Ġ= Ġif Ġ( go aled ) Ġ( step Ġ+ Ġcourse . length Ġ- Ġstate . position . y Ġ- Ġ 0 . 5 ) Ġ/ Ġstate . velocity . y Ġelse Ġ 0 . 0 ĊĊĠ Ġoperator Ġoverride Ġfun Ġcompare To ( other Ġ: ĠC andidate ) Ġ: ĠInt Ġ{ ĊĠĠĠ Ġif Ġ( go aled ) Ġ{ ĊĠĠĠĠĠ Ġif Ġ(! other . go aled Ġ|| Ġother . goal Time Ġ> Ġgoal Time ) Ġreturn Ġ- 1 ĊĠĠĠĠĠ Ġelse Ġif Ġ( other . goal Time Ġ< Ġgoal Time ) Ġreturn Ġ 1 ĊĠĠĠĠĠ Ġelse Ġreturn Ġ 0 ĊĠĠĠ Ġ} Ġelse Ġif Ġ( state Ġ== Ġother . state ) Ġreturn Ġstep Ġ- Ġother . step ĊĠĠĠ Ġelse Ġreturn Ġother . state . compareTo ( state ) ĊĠ Ġ} ĊĊĠ Ġoverride Ġfun ĠtoString () Ġ: ĠString Ġ{ ĊĠĠĠ Ġreturn Ġ"# ${ seq }: Ġ${ step }@ (${ state . position . x }, ${ state . position . y }) + (${ state . velocity . x }, ${ state . velocity . y }) Ġ<- Ġ# ${ from ?. seq Ġ?: Ġ 0 }" ĊĠ Ġ} Ċ } ĊĊĊ Ċ fun Ġplan ( info Ġ: ĠRace Info , Ġcourse Ġ: ĠRace Course ) Ġ: ĠInt Vec Ġ{ ĊĠ Ġval Ġcandidates Ġ= ĠPriority Queue < Candidate >() ĊĠ Ġval Ġinitial Ġ= ĠPlayer State ( info . me . position , Ġinfo . me . velocity ) ĊĠ Ġval Ġinitial C and Ġ= ĠC andidate ( course , Ġ 0 , Ġinitial , Ġnull , ĠInt Vec ( 0 , Ġ 0 )) ĊĠ Ġval Ġreached Ġ= Ġmutable Map Of ( initial Ġto Ġinitial C and ) ĊĠ Ġvar Ġbest Ġ= Ġinitial C and ĊĠ Ġcandidates . add ( initial C and ) ĊĠ Ġwhile Ġ(! candidates . isEmpty ()) Ġ{ ĊĠĠĠ Ġval Ġc Ġ= Ġcandidates . poll () ĊĠĠĠ Ġfor Ġ( cay Ġin Ġ 1 Ġdown To Ġ- 1 ) Ġ{ ĊĠĠĠĠĠ Ġfor Ġ( c ax Ġin Ġ- 1 .. 1 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġaccel Ġ= ĠInt Vec ( c ax , Ġc ay ) ĊĠĠĠĠĠĠĠ Ġvar Ġve lo Ġ= Ġc . state . velocity Ġ+ Ġaccel ĊĠĠĠĠĠĠĠ Ġif Ġ( velo . x Ġ* Ġve lo . x Ġ+ Ġve lo . y Ġ* Ġve lo . y Ġ<= Ġspeed Limit Squared ) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġval Ġpos Ġ= Ġc . state . position Ġ+ Ġve lo ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( 0 Ġ<= Ġpos . x Ġ&& Ġpos . x Ġ< Ġcourse . width ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmove Ġ= ĠMovement ( c . state . position , Ġpos ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtouched Ġ= Ġmove . touched S quares () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( pos Ġ!= Ġinfo . opp onent . position Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtouched . all Ġ{ Ġs Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ 0 Ġ> Ġs . y Ġ|| Ġs . y Ġ>= Ġcourse . length Ġ|| ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinfo . squares [ s . y ][ s . x ] Ġ!= Ġ 1 }) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( 0 Ġ<= Ġpos . y Ġ&& Ġpos . y Ġ< Ġcourse . length Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinfo . squares [ pos . y ][ pos . x ] Ġ== Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġve lo Ġ= ĠInt Vec ( 0 , Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnext State Ġ= ĠPlayer State ( pos , Ġve lo ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnext C and Ġ= ĠC andidate ( course , Ġc . step Ġ+ Ġ 1 , Ġnext State , Ġc , Ġaccel ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! next C and . go aled Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc . step Ġ< Ġsearch Depth Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ(! re ached . containsKey ( next State ) Ġ|| ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreached [ next State ] !!. step Ġ> Ġc . step Ġ+ Ġ 1 )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcandidates . add ( next C and ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreached [ next State ] Ġ= Ġnext C and ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( next C and Ġ< Ġbest ) Ġbest Ġ= Ġnext C and ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠ Ġ} ĊĠ Ġif Ġ( best Ġ== Ġinitial C and ) Ġ{ ĊĠĠĠ Ġvar Ġax Ġ= Ġ 0 ĊĠĠĠ Ġvar Ġay Ġ= Ġ 0 ĊĠĠĠ Ġif Ġ( info . me . velocity . x Ġ< Ġ 0 ) Ġax Ġ+= Ġ 1 ĊĠĠĠ Ġelse Ġif Ġ( info . me . velocity . x Ġ> Ġ 0 ) Ġax Ġ-= Ġ 1 ĊĠĠĠ Ġif Ġ( info . me . velocity . y Ġ< Ġ 0 ) Ġay Ġ+= Ġ 1 ĊĠĠĠ Ġelse Ġif Ġ( info . me . velocity . y Ġ> Ġ 0 ) Ġay Ġ-= Ġ 1 ĊĠĠĠ Ġreturn ĠInt Vec ( ax , Ġay ) ĊĠ Ġ} ĊĠ Ġvar Ġc Ġ: ĠC andidate Ġ= Ġbest ĊĠ Ġwhile Ġ( c . from Ġ!= Ġinitial C and ) Ġ{ ĊĠĠĠ Ġc Ġ= Ġc . from !! ĊĠ Ġ} ĊĠ Ġreturn Ġc . how Ċ } ĊĊ Ċ fun Ġmain ( args Ġ: ĠArray < String >) Ġ{ ĊĠ Ġval Ġinput Ġ= Ġjava . util . Scanner ( System .` in `) ĊĠ Ġval Ġcourse Ġ= ĠRace Course ( input ) ĊĠ Ġprintln ( 0 ) ĊĠ ĠSystem . out . flush () ĊĠ Ġtry Ġ{ ĊĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠ Ġval Ġinfo Ġ= ĠRace Info ( input , Ġcourse ) ĊĠĠĠĠĠ Ġval Ġaccel Ġ= Ġplan ( info , Ġcourse ) ĊĠĠĠĠĠ Ġprintln ("${ accel . x } Ġ${ accel . y }") ĊĠĠĠĠĠ ĠSystem . out . flush () ĊĠĠĠ Ġ} ĊĠ Ġ} Ġcatch Ġ( e Ġ: ĠException ) Ġ{ ĊĠ Ġ} Ċ } Ċ