No.2030 Googol Strings
タグ : / 解いたユーザー数 108
作問者 :
とりゐ
Problem Statement
You are given $2$ distinct strings $x, y$. Let $X$ be the string obtained by concatenating $10^{100}$ copies of $x$. Also, let $Y$ be the string obtained by concatenating $10^{100}$ copies of $y$.
Which of $X$ and $Y$ is lexicographically larger?
You are given $T$ test cases; solve each of them.
What is lexicographical order? (click to expand)
Given $2$ distinct strings $X, \ Y$, the lexicographical order between $X$ and $Y$ is determined as follows. Let $X_i$ denote the $i$-th character of $X$.
- Let $L$ be the length of the shorter of $X$ and $Y$.
- If there exists an $i$ $(1 \leq i \leq L)$ such that $X_i \neq Y_i$, let $j$ be the smallest such $i$. If $X_j < Y_j$ in alphabetical order, then $X < Y$; if $X_j > Y_j$, then $X > Y$.
- If there is no $i$ such that $X_i \neq Y_i$, compare the lengths $|X|, \ |Y|$ of $X, Y$. If $|X| < |Y|$, then $X < Y$; if $|X| > |Y|$, then $X > Y$.
Constraints
- $1 \leq T \leq 10^4$
- $x, y$ are strings consisting of lowercase English letters
- $1 \leq |x| , |y| \leq 10^6$
- $x \neq y$
- In $1$ input file, the sum of $|x|$ and the sum of $|y|$ are each at most $10^6$
Input
The input is given from standard input. Line $1$ is given in the following format.
$T$
Then, $T$ test cases follow, each given in the following format.
$x$ $y$
Output
Print $T$ lines. On line $i$ $(1 \leq i \leq T)$, for the $i$-th test case, print X if $X > Y$ lexicographically, and Y if $X < Y$.
Print a newline at the end.
Sample
Sample 1
Input
5 abcd abc b a yukicoder yuki w ww xyzxyzxyz xyzxyz
Output
X X Y Y X
$5$ test cases are given.
In test case $1$, $X$ is abcdabcdabcd... and $Y$ is abcabcabcabc.... The lexicographically larger one is $X$, so print X.
In test case $2$, $X$ is bbbb... and $Y$ is aaaa.... The lexicographically larger one is $X$, so print X.
In test case $3$, $X$ is yukicoderyukicoder... and $Y$ is yukiyukiyuki.... The lexicographically larger one is $Y$, so print Y.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。