問題一覧 > 通常問題

No.2030 Googol Strings

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 106
作問者 : Shirotsume / テスター : 👑 ygussany とりゐ
3 ProblemId : 8203 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-05 19:50:54

問題文

22 つの異なる文字列 x,yx, y が与えられます。xx を 1010010^{100} 個連結した文字列を XX とします。また、yy を 1010010^{100} 個連結した文字列を YY とします。

XX と YY のうち、辞書順で 大きい ものはどちらでしょうか？

TT 個のテストケースが与えられるので、それぞれについて解いてください。

辞書順とは（クリックで展開）

22 つの相異なる文字列 X, YX, \ Y が与えられたとき、 XX と YY の辞書順による大小は以下のように決まります。XX の ii 文字目を XiX_i のように表します。

  • XX と YY のうち、長さが短い方の文字列の長さを LL とする。
  • Xi≠YiX_i \neq Y_i なる ii (1≤i≤L)(1 \leq i \leq L) が存在するならば、そのうち最小の ii を jj とする。アルファベット順で Xj<YjX_j < Y_j ならば X<YX < Y 、 Xj>YjX_j > Y_j ならば X>YX > Y と決定する。
  • Xi≠YiX_i \neq Y_i なる ii が存在しないならば、X,YX, Y の長さ ∣X∣, ∣Y∣|X|, \ |Y| を比較し、 ∣X∣<∣Y∣|X| < |Y| ならば X<YX < Y 、 ∣X∣>∣Y∣|X| > |Y| ならば X>YX > Y と決定する。

制約

  • 1≤T≤1041 \leq T \leq 10^4
  • x,yx, y は英小文字からなる文字列
  • 1≤∣x∣,∣y∣≤1061 \leq |x| , |y| \leq 10^6
  • x≠yx \neq y
  • 11 つの入力ファイルにおいて、 ∣x∣|x| の合計、 ∣y∣|y| の合計はそれぞれ 10610^6 以下

入力

入力は標準入力から与えられる。 11 行目は以下の形式で与えられる。

TT

以下、 TT 個のテストケースがそれぞれ以下の形式で与えられる。

xx
yy

出力

TT 行にわたって出力せよ。ii (1≤i≤T)(1 \leq i \leq T) 行目には、 ii 番目のテストケースについて、辞書順で X>YX > Y なら X、 X<YX < Y なら Y を出力せよ。

最後に改行すること。

サンプル

サンプル1
入力
5
abcd
abc
b
a
yukicoder
yuki
w
ww
xyzxyzxyz
xyzxyz
出力
X
X
Y
Y
X

55 つのテストケースが与えられています。

11 つ目のケースでは、XX は abcdabcdabcd... で、 YY は abcabcabcabc... です。辞書順でより大きいものは XX なので、X と出力してください。

22 つ目のケースでは、XX は bbbb... で、 YY は aaaa... です。辞書順でより大きいものは XX なので、X と出力してください。

33 つ目のケースでは、XX は yukicoderyukicoder... で、 YY はyukiyukiyuki... です。辞書順でより大きいものは YY なので、Y と出力してください。

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