問題一覧 > 通常問題

No.2030 Googol Strings

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

問題文

$2$ つの異なる文字列 $x, y$ が与えられます。$x$ を $10^{100}$ 個連結した文字列を $X$ とします。また、$y$ を $10^{100}$ 個連結した文字列を $Y$ とします。

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

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

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

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

  • $X$ と $Y$ のうち、長さが短い方の文字列の長さを $L$ とする。
  • $X_i \neq Y_i$ なる $i$ $(1 \leq i \leq L)$ が存在するならば、そのうち最小の $i$ を $j$ とする。アルファベット順で $X_j < Y_j$ ならば $X < Y$ 、 $X_j > Y_j$ ならば $X > Y$ と決定する。
  • $X_i \neq Y_i$ なる $i$ が存在しないならば、$X, Y$ の長さ $|X|, \ |Y|$ を比較し、 $|X| < |Y|$ ならば $X < Y$ 、 $|X| > |Y|$ ならば $X > Y$ と決定する。

制約

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

入力

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

$T$

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

$x$
$y$

出力

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

最後に改行すること。

サンプル

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

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

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

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

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

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