結果

問題 No.3 ビットすごろく
コンテスト
ユーザー IJKTanabe
提出日時 2017-10-23 00:19:27
言語 Kotlin
(2.1.0)
結果
WA  
実行時間 -
コード長 2,608 bytes
コンパイル時間 12,705 ms
コンパイル使用メモリ 439,684 KB
実行使用メモリ 57,888 KB
最終ジャッジ日時 2024-11-20 13:04:45
合計ジャッジ時間 25,172 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:3:10: warning: parameter 'args' is never used
fun main(args: Array<String>) {
         ^

ソースコード

diff # 

import java.util.*

fun main(args: Array<String>) {
   
    val sc = Scanner(System.`in`)
    val goal = Integer.parseInt(sc.next())
    val root: Int = 1
    
    val routeStack: MutableList<Int> = mutableListOf()
    val searchedList: MutableList<Int> = mutableListOf()
    val resultRouteList: MutableList<List<Int>> = mutableListOf()
    
    var num: Int
    var upperNext: Int
    var lowerNext: Int
    
    num = root
    routeStack.add(num)
    do {
        num = routeStack.get(0)             //ルートスタックの先頭を参照して現地点を移動
        searchedList.add(0, num)            //探索済みリストに現地点を追加
        upperNext = num + Integer.bitCount(num)     //プラス方向
        lowerNext = num - Integer.bitCount(num)     //マイナス方向
        ///*Debug*/println("Route Stack" + routeStack)
        ///*Debug*/println("Searched List" + searchedList)
        ///*Debug*/println("nowSearching = " + num + " : up = " + upperNext + " : low = " + lowerNext)
        
        if(!searchedList.contains(upperNext) && upperNext < goal) {
            //プラス方向が未探索かつゴール以下の場合、ルートスタックに追加
            routeStack.add(0,upperNext)
            ///*Debug*/println("going to UpperNext")
        } else if(!searchedList.contains(lowerNext) && lowerNext > 0) {
            //プラス方向が探索済みで、マイナス方向が未探索かつ0以上の場合、ルートスタックに追加
            routeStack.add(0,lowerNext)
            ///*Debug*/println("going to LowerNext")
        } else {
            //上下ともに探索済み（もしくは範囲外）だった場合
            //あれ、もしかしてプラス方向がゴールだった？ なら結果に追加
            if(upperNext == goal) {
                routeStack.add(0, goal)
                resultRouteList.add(routeStack.toList())
                ///*Debug*/println("***We found route!! " + goal)
                routeStack.removeAt(0)
            }
            //探索が終わったので現地点をルートスタックから削除（つまりルートを一つ戻ることになる）
            routeStack.removeAt(0)
            ///*Debug*/println("remove this Number from Stack")
        }
        ///*Debug*/println("")

    } while(routeStack.size > 0)
    
    if(resultRouteList.size > 0) {
        //println(resultRouteList.size)
        resultRouteList.sortBy { l -> l.size }
        println(resultRouteList[0].size)
        //println(resultRouteList[0])
    } else {
        println(-1)
    }
}
0