[白俊]#1256辞書

18219 ワード
白駿 algorithm DP テキストリンク

質問する


東昊と圭完は212番で文字列を勉強した.金ジンヨン助教は、東昊と圭完に特別課題を与えた.特別な課題は,特殊な文字列からなる辞書の作成である.辞書に収録されているすべての文字列は,N個の「a」とM個の「z」からなる.しかも他の文字はありません.辞書にはアルファベット順に収録されている.
圭完は辞書を完成したが、東昊は辞書を完成しなかった.自分の課題を達成するために、東昊は圭完の辞書をこっそり参考にすることにした.東昊は圭がいないうちに辞書をこっそり見ようとしたので、文字列は1つしか見つからなかった.
NとMが与えられた場合、葵婉の辞書からK番目の文字列が何であるかを見つけるプログラムを作成します.

入力


1行目はN,M,Kの順に与えられる.NおよびMは100以下の自然数であり、Kは10000000以下の自然数である.

しゅつりょく


1行目は葵婉の辞書からK番目の文字列を出力します.圭完の辞書の文字列数がKより小さい場合、-1が出力されます.

入力例1

2 2 2

サンプル出力1

azaz

に答える


この問題はダイナミックプログラミングで解決できる.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static StringBuilder sb;
    static long[][] dp;

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

        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        int K = Integer.parseInt(input[2]);
        dp = new long[N+2][M+2];
        for(int i=0; i<=N; i++)
            dp[i][0] = 1;
        for(int j=0; j<=M; j++)
            dp[0][j] = 1;

        dp[1][1] = 2;     //dp 배열 전처리

        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {

                dp[i+1][j] = Math.min(dp[i][j]*(i+j+1)/(i+1), 1000000000);    //조합을 이용해서 가능한 경우의수 구하기
                dp[i][j+1] = Math.min(dp[i][j]*(i+j+1)/(j+1), 1000000000);
            }
        }

        if(dp[N][M]<K)
            System.out.println(-1);

        else {
            sb = new StringBuilder();
            make_string(N, M, K);
            System.out.println(sb);
        }
    }

    public static void make_string(int n, int m, long k) {    //정답 단어 찾기

        if(n==0) {
            sb.append("z".repeat(Math.max(0, m)));
            return;
        }

        if(m==0) {
            sb.append("a".repeat(Math.max(0, n)));
            return;
        }

        if(dp[n-1][m]>=k) {
            sb.append('a');
            make_string(n-1, m, k);
        }

        else {
            sb.append('z');
            make_string(n, m-1, k-dp[n-1][m]);
        }
    }
}
9.17キーボードの操作
cpdetectorによる文書ドキュメントの符号化の判断