/** Ċ Ġ* ĠDescription : ĠKotlin Ġtips Ġfor Ġd um m ies Ċ Ġ* ĠSource : Ċ Ġ* Ġhttps :// co def or ces . com / blog / entry / 7 1 0 8 9 Ċ Ġ* ĠKotlin ĠReference Ċ Ġ* Ġhttps :// kotlin lang . org / docs / tutorials / compet itive - programming . html Ċ Ġ*/ Ċ Ċ /// Ġepisode Ġ 1 : Ġhttps :// co def or ces . com / contest / 1 1 7 0 Ċ /// Ġepisode Ġ 2 : Ġhttps :// co def or ces . com / contest / 1 2 1 1 Ċ /// Ġepisode Ġ 3 : Ġhttps :// co def or ces . com / contest / 1 2 9 7 Ċ // Ġhttps :// github . com / b qi 3 4 3 / US AC O / blob / master / Implement ations / content / var ious / kotlin Old . kt Ċ Ċ import Ġjava . io .* Ċ import Ġjava . lang . Math . abs Ċ import Ġjava . util .* Ċ import Ġkotlin . system . exit Process Ċ Ċ // Ġ@ Jvm Field Ġval ĠINPUT Ġ= ĠFile (" input . txt "). inputStream () Ċ // Ġ@ Jvm Field Ġval ĠOUTPUT Ġ= ĠFile (" output . txt "). output Stream () Ċ Ċ /// Ġhttps :// kotlin lang . org / api / latest / jvm / stdlib / kotlin . jvm /- jvm - field / Ċ Ċ class ĠK att io : ĠPrintWriter Ġ{ ĊĠĠĠ Ġ@ Jvm Field Ġval Ġr : ĠBufferedReader ĊĠĠĠ Ġ@ Jvm Field Ġvar Ġst Ġ= ĠString Tokenizer ("") ĊĠĠĠ Ġconstructor (): Ġthis ( System .` in `, System . out ) Ġ{} ĊĠĠĠ Ġconstructor ( i : ĠInputStream , Ġo : ĠOutputStream ): Ġsuper ( o , false ) Ġ{ Ġr Ġ= Ġi . buffered Reader () Ġ} ĊĠĠĠ Ġfun Ġr Line (): ĠString ? Ġ= Ġr . readLine () ĊĊĠĠĠ Ġfun Ġread (): ĠString Ġ{ Ġ// Ġif Ġno Ġinput Ġleft Ġreturns Ġempty Ġstring ĊĠĠĠĠĠĠĠ Ġwhile Ġ( st . hasMore Tokens (). not ()) Ġst Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ ĠString Tokenizer ( r Line () Ġ?: Ġreturn Ġ"", Ġ" Ġ") ĊĠĠĠĠĠĠĠ Ġreturn Ġst . nextToken () ĊĠĠĠ Ġ} ĊĠĠĠ Ġfun Ġstr s ( n : ĠInt ) Ġ= ĠList ( n ){ read ()} ĊĠĠĠ Ġfun Ġln () Ġ= Ġr Line () !! ĊĠĠĠ Ġfun Ġl ns ( n : ĠInt ) Ġ= ĠList ( n ){ ln ()} ĊĠĠĠ Ġfun Ġint () Ġ= Ġread (). toInt () ĊĠĠĠ Ġfun Ġints ( n : ĠInt ) Ġ= ĠList ( n ){ int ()} ĊĠĠĠ Ġfun Ġdb () Ġ= Ġread (). toDouble () ĊĠĠĠ Ġfun Ġr D bs ( n : ĠInt ) Ġ= ĠList ( n ){ db ()} ĊĠĠĠ Ġfun Ġlong () Ġ= Ġread (). to Long () ĊĠĠĠ Ġfun Ġlong s ( n : ĠInt ) Ġ= ĠList ( n ){ long ()} Ċ } Ċ Ċ val Ġio Ġ= ĠK att io () Ċ // const Ġval ĠMOD Ġ= Ġ 1 0 0 0 0 0 0 0 0 7 Ċ const Ġval ĠMOD Ġ= Ġ 9 9 8 2 4 4 3 5 3 Ċ const Ġval ĠINF Ġ= Ġ( 1 e 1 8 ). to Long () Ċ const Ġval ĠS Z Ġ= Ġ 1 Ġshl Ġ 1 7 Ċ Ċ fun ĠY N ( b : ĠBoolean ) Ġ: ĠString Ġ{ Ġreturn Ġif Ġ( b ) Ġ" YES " Ġelse Ġ" NO " Ġ Ġ} Ċ fun Ġadd ( a : ĠInt , Ġb : ĠInt ): ĠInt Ġ{ ĊĠĠĠ Ġval Ġres Ġ= Ġa + b ĊĠĠĠ Ġreturn Ġif Ġ( res Ġ>= ĠMOD ) Ġres - MOD Ġelse Ġres Ċ } Ċ fun Ġsub ( a : ĠInt , Ġb : ĠInt ): ĠInt Ġ{ ĊĠĠĠ Ġval Ġres Ġ= Ġa - b ĊĠĠĠ Ġreturn Ġif Ġ( res Ġ< Ġ 0 ) Ġres + MOD Ġelse Ġres Ċ } Ċ fun Ġmul ( a : ĠInt , Ġb : ĠInt ) Ġ= Ġ(( a . to Long ()* b )% MOD ). toInt () Ċ fun Ġmod _ pow ( a : ĠInt , Ġb : ĠInt ): ĠInt Ġ{ ĊĠĠĠ Ġif Ġ( b Ġ== Ġ 0 ) Ġreturn Ġ 1 ĊĠĠĠ Ġif Ġ( b % 2 Ġ== Ġ 1 ) Ġreturn Ġmul ( mod _ pow ( a , b - 1 ), a ) ĊĠĠĠ Ġreturn Ġmod _ pow ( mul ( a , a ), b / 2 ) Ċ } Ċ fun Ġmod _ inv ( a : ĠInt ): ĠInt Ġ= Ġmod _ pow ( a , MOD - 2 ) Ċ fun Ġgcd ( a : ĠInt , Ġb : ĠInt ) Ġ: ĠInt Ġ= Ġif Ġ( b Ġ== Ġ 0 ) Ġa Ġelse Ġgcd ( b , a % b ) Ċ Ċ fun Ġexample () Ġ{ ĊĠĠĠ Ġprintln ( String . format ("% . 8 f ", Ġ 5 . 2 5 )) Ġ// Ġprint Ġto Ġ 8 Ġdecimals ĊĠĠĠ Ġval Ġarr 2 D Ġ= ĠArray < IntArray >( 5 ,{ IntArray ( 5 ,{ 5 }) }) ĊĠĠĠ Ġvar Ġ( x , y ) Ġ= ĠarrayOf ( 3 , 2 ) Ġ// Ġor Ġr Ints ( 2 ) ĊĠĠĠ Ġwhen Ġ( x ) Ġ{ Ġ// Ġ Ġswitch , Ġcan Ġbe Ġused Ġas Ġexpression ĊĠĠĠĠĠĠĠĠ 0 , 1 Ġ-> Ġprintln (" x Ġ<= Ġ 1 ") ĊĠĠĠĠĠĠĠĠ 2 Ġ-> Ġprintln (" x Ġ== Ġ 2 ") Ġ// ĠNote Ġthe Ġblock ĊĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ Ġprintln (" x Ġis Ġneither Ġ 1 Ġnor Ġ 2 ") Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġx Ġ= Ġy . also Ġ{ Ġy Ġ= Ġx Ġ} Ġ// Ġswap Ġx Ġand Ġy ĊĠĠĠ Ġprintln ("${ max Of ( x + 2 , y )} ") Ġ// Ġ( x , y ) =( 4 , 3 ) Ġ-> Ġ 4 ĊĠĠĠ Ġval Ġh Ġ= ĠHashMap < String , Int >() ĊĠĠĠ Ġval Ġs Ġ= Ġ" abab a " ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. s . length - 2 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġw Ġ= Ġs . substring ( i , i + 2 ) ĊĠĠĠĠĠĠĠ Ġval Ġc Ġ= Ġh . getOrElse ( w ,{ 0 }) ĊĠĠĠĠĠĠĠ Ġh [ w ] Ġ= Ġc + 1 ĊĠĠĠ Ġ} ĊĠĠĠ Ġfor Ġ(( a , b ) Ġin Ġh ) Ġprintln ("${ a } Ġ${ b }") Ġ// Ġkey , value ĊĠĠĠ Ġval Ġpq Ġ= ĠPriority Queue < Pair < Long , Int >> (){ x , y Ġ-> ĊĠĠĠĠĠĠĠ Ġx . first . compareTo ( y . first )} Ġ// Ġor Ġcompare By { it . first } ĊĠĠĠ Ġval ĠA Ġ= Ġarray ListOf ( Pair ( 1 , 3 ), Pair ( 3 , 2 ), Pair ( 2 , 3 )) ĊĠĠĠ Ġval ĠB Ġ= ĠA . sorted With ( Comparator < Pair < Int , Int >> { x , y Ġ-> ĊĠĠĠĠĠĠĠ Ġx . first . compareTo ( y . first )}) Ġ// Ġor ĠsortBy { it . first } ĊĠĠĠ Ġval Ġlist Ġ= Ġarray ListOf (' a ',' b ',' c ',' d ',' e ') ĊĠĠĠ Ġprintln ( list . binary Search (' d ')) Ġ// Ġ 3 ĊĠĠĠ Ġlist . remove (' d ') ĊĠĠĠ Ġval Ġactual Insert Point Ġ= Ġ-( list . binary Search (' d ') + 1 ) Ġ// Ġ 3 ĊĠĠĠ Ġlist . add ( actual Insert Point , Ġ' d ') Ġ// Ġ[ a , b , c , d , e ] ĊĠĠĠ Ġlist . remove At ( 1 ) Ġ// Ġremove Ġat Ġindex Ġ-> Ġ[ a , c , d , e ] Ċ } Ċ Ċ // fun Ġmake ArrayList ( n : ĠInt ): ĠArrayList < Int > Ġ{ Ċ // ĠĠĠ Ġval Ġres Ġ= ĠArrayList < Int >() Ċ // ĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn ) Ġres . add ( 0 ) Ċ // ĠĠĠ Ġreturn Ġres Ċ //} Ċ Ċ // fun Ġall On es (): ĠArrayList < Int > Ġ{ Ċ // ĠĠĠ Ġval Ġres Ġ= ĠArrayList < Int >() Ċ // ĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġ 8 1 9 2 ) Ġres . add ( 1 ) Ċ // ĠĠĠ Ġreturn Ġres Ċ //} Ċ Ċ fun Ġempty (): ĠInt Array Ġ{ Ġ Ġreturn ĠInt Array ( 8 1 9 2 ){ 0 } Ġ} Ċ fun Ġones (): ĠInt Array Ġ{ Ġ Ġreturn ĠInt Array ( 8 1 9 2 ){ 1 } Ġ} Ċ val Ġseg Ġ= ĠArray < IntArray >( 2 0 4 8 ){ ones ()} Ċ Ċ fun Ġfft (_ A : ĠInt Array , Ġinv : ĠBoolean Ġ= Ġfalse ): ĠInt Array Ġ{ ĊĠĠĠ Ġvar ĠA Ġ= Ġ_ A . copyOf () ĊĠĠĠ Ġval Ġn Ġ= ĠA . size ĊĠĠĠ Ġvar Ġb Ġ= Ġn / 2 ĊĠĠĠ Ġvar ĠB Ġ= Ġempty () ĊĠĠĠ Ġwhile Ġ( b Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġw Ġ= Ġmod _ pow ( 5 ,( MOD - 1 )/ n * b ) ĊĠĠĠĠĠĠĠ Ġvar Ġm Ġ= Ġ 1 Ġ// Ġn / b 't h Ġroot Ġof Ġun ity ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġn ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 Ġuntil Ġb ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġu Ġ= ĠA [ i + j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġv Ġ= Ġmul ( A [ i + j + b ], m ); ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠB [ i Ġ/ Ġ 2 Ġ+ Ġj ] Ġ= Ġadd ( u , v ); ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠB [ i Ġ/ Ġ 2 Ġ+ Ġj Ġ+ Ġn Ġ/ Ġ 2 ] Ġ= Ġsub ( u , v ); ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ+= Ġb * 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġm Ġ= Ġmul ( m , w ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġb Ġ/= Ġ 2 ĊĠĠĠĠĠĠĠ ĠA Ġ= ĠB . also { ĠB Ġ= ĠA } ĊĠĠĠ Ġ} ĊĠĠĠ Ġif Ġ( inv ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 1 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< ĠA . size - i ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠA [ i ] Ġ= ĠA [ A . size - i ]. also { A [ A . size - i ] Ġ= ĠA [ i ]} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ++ i ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġz Ġ= Ġmod _ inv ( n ); ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn ) ĠA [ i ] Ġ= Ġmul ( A [ i ], z ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn ĠA Ċ } Ċ Ċ fun Ġmake On es ( w : ĠInt , Ġn : ĠInt ): ĠInt Array Ġ{ ĊĠĠĠ Ġval Ġres Ġ= Ġempty () ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. n ) Ġres [ i * w ] Ġ= Ġ 1 ĊĠĠĠ Ġreturn Ġres Ċ } Ċ Ċ fun Ġcom b ( a : ĠInt Array , Ġb : ĠInt Array ): ĠInt Array Ġ{ ĊĠĠĠ Ġval Ġc Ġ= Ġempty () ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġ 8 1 9 2 ) Ġc [ i ] Ġ= Ġmul ( a [ i ], b [ i ]) ĊĠĠĠ Ġreturn Ġc Ċ } Ċ Ċ fun Ġq range (_ l : ĠInt , Ġ_ r : ĠInt ): Ġ ĠInt Array Ġ{ ĊĠĠĠ Ġvar Ġl Ġ= Ġ_ l + 1 0 2 4 ĊĠĠĠ Ġvar Ġr Ġ= Ġ_ r + 1 0 2 5 ĊĠĠĠ Ġvar Ġres Ġ= Ġones () ĊĠĠĠ Ġwhile Ġ( l Ġ< Ġr ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( l % 2 Ġ== Ġ 1 ) Ġres Ġ= Ġcom b ( res , seg [ l ++ ]) ĊĠĠĠĠĠĠĠ Ġif Ġ( r % 2 Ġ== Ġ 1 ) Ġres Ġ= Ġcom b ( res , seg [ -- r ]) ĊĠĠĠĠĠĠĠ Ġl Ġ/= Ġ 2 ĊĠĠĠĠĠĠĠ Ġr Ġ/= Ġ 2 ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġres Ċ } Ċ Ċ fun Ġsolve () Ġ{ Ċ // ĠĠĠ Ġval Ġ( a , b , k ) Ġ= Ġio . long s ( 3 ) Ċ // ĠĠĠ Ġio . println (( k + 1 )/ 2 * a - k / 2 * b ) Ċ // ĠĠĠ Ġval Ġn Ġ= Ġio . int () Ċ // ĠĠĠ Ġval Ġa Ġ= Ġio . ints ( n ). sorted () Ċ //// ĠĠĠ Ġprintln ( a ) Ċ // ĠĠĠ Ġvar Ġans Ġ= Ġ 0 Ċ // ĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn / 2 ) Ġans Ġ+= Ġa [ 2 * i + 1 ]- a [ 2 * i ] Ċ // ĠĠĠ Ġprintln ( ans ) ĊĠĠĠ Ġval Ġn Ġ= Ġio . int () ĊĠĠĠ Ġval Ġa Ġ= Ġio . ints ( n ) ĊĠĠĠ Ġvar Ġsum Ġ= Ġ 0 L ĊĠĠĠ Ġfor Ġ( i Ġin Ġa ) Ġsum Ġ+= Ġi ĊĠĠĠ Ġval Ġans Ġ= ĠArrayList < Int >() ĊĠĠĠ Ġval Ġoc Ġ= ĠHashMap < Int , Int >() ĊĠĠĠ Ġfor Ġ( i Ġin Ġa ) Ġoc . put ( i , oc . get OrDefault ( i , 0 )+ 1 ); ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. n - 1 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġdes _ 2 Ġ= Ġsum - a [ i ] ĊĠĠĠĠĠĠĠ Ġif Ġ( des _ 2 % 2 Ġ!= Ġ 0 L ) Ġcontinue ĊĠĠĠĠĠĠĠ Ġval Ġdes Ġ= Ġdes _ 2 / 2 ĊĠĠĠĠĠĠĠ Ġif Ġ( des Ġ<= Ġ 1 0 0 0 0 0 0 Ġ&& Ġoc . get OrDefault ( des . toInt (), 0 )-( if Ġ( a [ i ]. to Long () Ġ== Ġdes ) Ġ 1 Ġelse Ġ 0 ) Ġ> Ġ 0 ) Ġans . add ( i ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġio . println ( ans . size ) ĊĠĠĠ Ġfor Ġ( i Ġin Ġans ) Ġio . print ("${ i + 1 } Ġ") Ċ } Ċ Ċ fun Ġmain () Ġ{ Ċ // ĠĠĠ Ġval Ġt Ġ= Ġio . int () ĊĠĠĠ Ġval Ġt Ġ= Ġ 1 ĊĠĠĠ Ġrepeat ( t ) Ġ{ Ġsolve () Ġ} ĊĠĠĠ Ġio . close () Ċ }