問題一覧 > 通常問題

No.2768 Password Crack

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 （詳しくはこちら）
タグ : / 解いたユーザー数 103
作問者 : srjywrdnprkt / テスター : 👑 p-adic
2 ProblemId : 10437 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-05-30 17:43:50

問題文

この問題はインタラクティブな問題です。

SS は英小文字のみからなる長さ NN の文字列です。SS は直接は与えられません。

その代わりに、ジャッジシステムに対し、以下の質問を 25002500 回まで行うことができます。

  • 長さ NN の英小文字のみからなる文字列 TT を選び、SS と TT が一致する箇所の個数を聞く。つまり、1≤i≤N1\leq i \leq N を満たす整数 ii のうち、SS の ii 文字目と TT の ii 文字目が等しいものの数を聞く。

    • 文字列 SS を求めてください。

    制約

  • NN は 11 以上 100100 以下の整数

    • 入出力

    この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。

    最初に文字列 SS の長さ NN が以下の形式で与えられます。 
    NN
    文字列 SS を当てることができるまで質問を繰り返してください。

    質問は、以下の形式で標準出力に出力してください。 
    ?? TT
    これに対する応答は、次の形式で標準入力から与えられます。 
    nn
    ここで、 nn は SS と TT が一致する箇所の個数です。

    文字列 SS が分かったら、以下の形式で標準出力に出力してください。 
    !! SS

    注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE や WA となる可能性があります。
  • 不正な出力を行った場合のジャッジ結果は不定です。余分な空白や改行を出力することも不正な出力にあたるので、注意してください。
  • 文字列 SS を解答した後はすぐにプログラムを終了させてください。終了しなければジャッジの結果は不定です。
  • 解答をするクエリは質問回数に含まれません。

    • サンプル

    以下は S=S= pswd として対話が始まった場合の対話の一例です。

    入力 出力 説明
    4 SS の長さである 44 が与えられます。
    ? abcd SS と T=T=abcd が一致する箇所の数を聞きます。
    1 SS と TT が一致する箇所は 44 文字目の 11 箇所のみなので、 11 が返されます。
    ? hoge SS と T=T=hoge が一致する箇所の数を聞きます。
    0 SS と TT が一致する箇所はないので、 00 が返されます。
    ? pswd SS と T=T=pswd が一致する箇所の数を聞きます。
    4 SS と TT が一致する箇所は 1,2,3,41,2,3,4 文字目の 44 箇所なので、44 が返されます。
    ! pswd S=S=pswd だと分かったので、これを出力します。

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。