No.104 国道

■■■問題■■■

ユキコダ国には1からはじまる番号のついた国道がある。
国道を判別するため同じ番号の国道は2つ以上無い。

まずユキコダ城から国道1号線がスタートしている。
国道は必ずいつか左と右の道に分岐する。

国道はより小さな番号の国道から、使えるより小さな番号を使って分岐する。
分岐する際に左の国道のほうが右の国道よりかならず番号が小さい。
1号線は左の2号線と右の3号線に分岐する。
2号線は左の4号線と右の5号線に分岐する。
3号線は左の6号線と右の7号線に分岐する。
4号線は左の8号線と右の9号線に分岐する。
5号線は左の10号線と右の11号線に分岐する。
このようなルールで国道には番号がついている。

いまA君はユキコダ城を出て引き返すことなくいくつかの分岐点を通過した。
A君は順番に左と右のどちらに分岐したかを覚えている。
A君がいま何号線を歩いているかを答えよ。

■■■入力■■■

S

分岐の方向をあらわす文字列Sが与えられる。
Sは文字'L'と'R'からなる0文字以上30文字以下の文字列。
'L'は分岐点で左に移動したことをあらわし、'R'は右に移動したことをあらわす。
文字列の先頭がA君の最も古い記憶で順に新しくなっていく。

最後にかならず改行が入っているので0文字が与えられることはない。

■■■出力■■■

A君が国道何号線を歩いているかを1行で答えよ。
改行を忘れずに。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("LR");
            //5
            //A君は最初1号線を歩いている。
            //最初の分岐点で1号線は左の2号線と右の3号線に分岐する。
            //A君は左の2号線を歩く。
            //2つめの分岐点で2号線は左の4号線と右の5号線に分岐する。
            //A君は右の5号線を歩く。
            //現在A君は5号線を歩いていることになる。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("RLL");
            //12
            //A君は最初1号線を歩いている。
            //最初の分岐点で1号線は左の2号線と右の3号線に分岐する。
            //A君は右の3号線を歩く。
            //2つめの分岐点で3号線は左の6号線と右の7号線に分岐する。
            //A君は左の6号線を歩く。
            //3つめの分岐点で6号線は左の12号線と右の13号線に分岐する。
            //A君は左の12号線を歩く。
            //現在A君は12号線を歩いていることになる。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("RLLRLRLRRRLRL");
            //12986
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("");
            //1
            //A君には分岐した記憶がない。よって1号線を歩いている
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int CurrRoad = 1;
        foreach (char EachChar in InputList[0]) {
            CurrRoad *= 2;
            if (EachChar == 'R') CurrRoad++;
        }
        Console.WriteLine(CurrRoad);
    }
}

解説

有名なアルゴリズムである
2分探索木のノード番号の付け方を流用して考えてます。