[伯俊]#2011パスワード

質問する

尚根と善英は、兄妹同士の会話を他の人に聞かれないように、会話を暗号化することにした.そこで以下のような会話を行いました.

上根:簡単に暗号化しましょう.Aは1 Bと2 Zは26です

善英:それはいけませんね.「BEAN」を暗号化すると25114が出てきて、文字に変換し直す方法がたくさんあります.

尚根:そうですね.25114を英語に置き換えると、「BEAAD」「YAAD」「YAN」「YDD」「BEKD」「BEAN」の6種類がありますが、BEANが正しい単語なのは分かりにくいのでは?

善英

:例が適切ではありません.もし私が500文字を暗号化したと言ったら.その時に出てくる説明は本当にたくさんあります.いつできますか.

勤務:どのくらいありますか.

善英:助けに行こう!プログラムを作成して、あるパスワードが与えられたとき、そのパスワードがどれだけ解釈できるかを求めます.

入力

最初の行のパスワードは5000ビット未満です.パスワードは数字で構成されています.

しゅつりょく

説明できる偽の技を見つけてください.答えが大きいかもしれないので、残りの10万を割ります.
パスワードが無効で、パスワードを解釈できない場合は0を出力します.

入力例1

25114

サンプル出力1

6

に答える

この問題はdp(Dynamic)アルゴリズムで解くことができる.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {


    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        if(input.equals("") || input.charAt(0)=='0') {
            System.out.println(0);
            return;
        }

        sol(input);
     }

    public static void sol(String str) {
        long[][] dp = new long[str.length()+1][2];
        dp[0][0] = 1;
        dp[1][0] = 1;

        for(int i=2; i<=str.length(); i++) {
            int one = str.charAt(i-1) - '0';
            int ten = str.charAt(i-2) - '0';

            if(one==0) {        //일의 자리 0인 경우
                if(ten==0) {
                    System.out.println(0);
                    return;
                }

                else {
                    dp[i][0] = 0;       //한자리 수 없는 경우

                    if(ten==1 || ten==2) { //두 자리 수 가능한 경우
                        dp[i][1] = (dp[i-2][0] + dp[i-2][1]) % 1000000;
                    }
                }
            }

            else {
                dp[i][0] = (dp[i-1][0]+dp[i-1][1]) % 1000000;
                //-----일의 자리 있는 경우
                if(ten==1 && (one>=0 && one<=9)) {  //십의 자리가 1일 때는 일의 자리 0~9 가능
                    dp[i][1] = (dp[i-2][0] + dp[i-2][1]) % 1000000;
                }

                else if(ten==2 && (one>=0 && one<=6)) {     //십의 자리가 2일 때는 일의자리 0~6까지 가능
                    dp[i][1] = (dp[i-2][0] + dp[i-2][1]) % 1000000;
                }

                else
                    dp[i][1] = 0;
            }
        }

        System.out.println((dp[str.length()][0]+dp[str.length()][1]) % 1000000);
    }
}