実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
相異なる二つの文字列 S, T が与えられます。
S が T よりも辞書順で小さい場合は Yes を、大きい場合は No を出力してください。
辞書順とは？
辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。
以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。
- S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
- S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
- S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。
なお、主要なプログラミング言語の多くでは、文字列の辞書順による比較は標準ライブラリに含まれる関数や演算子として実装されています。詳しくは各言語のリファレンスをご参照ください。
制約
- S, T は英小文字からなる長さ 1 以上 10 以下の相異なる文字列である。
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
S が T より辞書順で小さい場合は Yes を、大きい場合は No を出力せよ。
入力例 1
abc atcoder
出力例 1
Yes
abc と atcoder は 1 文字目が同じで 2 文字目が異なります。 アルファベットの b は t よりもアルファベット順で先に来るので、 abc の方が atcoder よりも辞書順で小さいことがわかります。
入力例 2
arc agc
出力例 2
No
入力例 3
a aa
出力例 3
Yes
Score : 100 points
Problem Statement
You are given two different strings S and T.
If S is lexicographically smaller than T, print Yes; otherwise, print No.
What is the lexicographical order?
Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.
Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.
- Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
- If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
- If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.
Note that many major programming languages implement lexicographical comparison of strings as operators or functions in standard libraries. For more detail, see your language's reference.
Constraints
- S and T are different strings, each of which consists of lowercase English letters and has a length of between 1 and 10 (inclusive).
Input
Input is given from Standard Input in the following format:
S T
Output
If S is lexicographically smaller than T, print Yes; otherwise, print No.
Sample Input 1
abc atcoder
Sample Output 1
Yes
abc and atcoder begin with the same character, but their second characters are different. Since b comes earlier than t in alphabetical order, we can see that abc is lexicographically smaller than atcoder.
Sample Input 2
arc agc
Sample Output 2
No
Sample Input 3
a aa
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
数直線があり、高橋君はこれを赤色と青色で次のように塗りました。
- X=L_1 から X=R_1 までをすべて赤色で塗る。
- X=L_2 から X=R_2 までをすべて青色で塗る。
数直線のうち、赤色と青色の両方で塗られている部分の長さを求めてください。
制約
- 0\leq L_1<R_1\leq 100
- 0\leq L_2<R_2\leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
L_1 R_1 L_2 R_2
出力
両方の色で塗られている部分の長さを整数で出力せよ。
入力例 1
0 3 1 5
出力例 1
2
X=0 から X=3 までが赤く、 X=1 から X=5 までが青く塗られています。
よって、両方の色で塗られている部分は X=1 から X=3 までであり、その長さは 2 となります。
入力例 2
0 1 4 5
出力例 2
0
両方の色で塗られている部分はありません。
入力例 3
0 3 3 7
出力例 3
0
赤色と青色で塗られている部分が接している場合でも、 両方の色で塗られている部分の長さは 0 となります。
Score : 100 points
Problem Statement
We have a number line. Takahashi painted some parts of this line, as follows:
- First, he painted the part from X=L_1 to X=R_1 red.
- Next, he painted the part from X=L_2 to X=R_2 blue.
Find the length of the part of the line painted both red and blue.
Constraints
- 0\leq L_1<R_1\leq 100
- 0\leq L_2<R_2\leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
L_1 R_1 L_2 R_2
Output
Print the length of the part of the line painted both red and blue, as an integer.
Sample Input 1
0 3 1 5
Sample Output 1
2
The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.
Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.
Sample Input 2
0 1 4 5
Sample Output 2
0
No part is painted both red and blue.
Sample Input 3
0 3 3 7
Sample Output 3
0
If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は置き時計を買いました。
この時計は、現在の時刻が 24 時制で \mathrm{AB} 時 \mathrm{CD} 分であるときに図 1 のように時刻を表します。
例えば図 2 では、時計は 7 時 58 分を示しています。
時刻の表示方法をより形式的に説明すると次のようになります。
現在の時刻が 24 時制で h 時 m 分であるとします。ここで 24 時制とは、時間を 0 以上 23 以下の整数で、分を 0 以上 59 以下の整数で表す時刻の表現方法を言います。
h の 10 の位を A, 1 の位を B, m の 10 の位を C, 1 の位を D とします。(ただし h, m が 1 桁である場合は先行ゼロを追加して考えます。)
このとき時計は左上に A を、左下に B を、右上に C を、右下に D を表示します。
高橋君は、次の条件を満たす時刻を 見間違えやすい時刻 と呼ぶことにしました。
- 時計の表示の右上と左下を入れ替えても、それに対応する 24 時制の時刻が存在する。
例えば 図 3 は 20 時 13 分を示していますが、時計の表示の右上と左下を入れ替えると 21 時 3 分を意味する表示になります。よって 20 時 13 分は見間違えやすい時刻です。
今、時計は H 時 M 分を示しています。
(現時点も含めて)以降はじめて訪れる見間違えやすい時刻を 24 時制で答えてください。
制約
- 0 \leq H \leq 23
- 0 \leq M \leq 59
- H, M は整数
入力
入力は以下の形式で標準入力から与えられる。
H M
出力
答えを h 時 m 分とする。ここで h, m は 0 \leq h \leq 23, 0 \leq m \leq 59 である必要がある。
このとき h, m を以下の形式で出力せよ。
h m
なお、h, m を 2 桁に揃えるために先行ゼロをつけた形式で出力しても正答と見なされる。
入力例 1
1 23
出力例 1
1 23
1 時 23 分は見間違えやすい時刻です。なぜならば、時計の表示の右上と左下を入れ替えると 2 時 13 分を意味する表示になるからです。
よって答えは 1 時 23 分です。
なお、01 23 のように先行ゼロをつけた形式で出力しても正答として扱われます。
入力例 2
19 57
出力例 2
20 0
19 時 57 分以降ではじめて訪れる見間違えやすい時刻は 20 時 0 分です。
入力例 3
20 40
出力例 3
21 0
24 時制では 24 時 0 分という表記は合法でないのに注意してください。
Score : 200 points
Problem Statement
Takahashi bought a table clock.
The clock shows the time as shown in Figure 1 at \mathrm{AB}:\mathrm{CD} in the 24-hour system.
For example, the clock in Figure 2 shows 7:58.
The format of the time is formally described as follows.
Suppose that the current time is m minutes past h in the 24-hour system. Here, the 24-hour system represents the hour by an integer between 0 and 23 (inclusive), and the minute by an integer between 0 and 59 (inclusive).
Let A be the tens digit of h, B be the ones digit of h, C be the tens digit of m, and D be the ones digit of m. (Here, if h has only one digit, we consider that it has a leading zero; the same applies to m.)
Then, the clock shows A in its top-left, B in its bottom-left, C in its top-right, and D in its bottom-right.
Takahashi has decided to call a time a confusing time if it satisfies the following condition:
- after swapping the top-right and bottom-left digits on the clock, it still reads a valid time in the 24-hour system.
For example, the clock in Figure 3 shows 20:13. After swapping its top-right and bottom-left digits, it reads 21:03. Thus, 20:13 is a confusing time.
The clock now shows H:M.
Find the next confusing time (including now) in the 24-hour system.
Constraints
- 0 \leq H \leq 23
- 0 \leq M \leq 59
- H and M are integers.
Input
The input is given from Standard Input in the following format:
H M
Output
Let h:m be the answer, where h and m must satisfy 0 \leq h \leq 23 and 0 \leq m \leq 59.
Print h and m in the following format:
h m
Your answer is considered correct even if h contains a leading zero to represent it as a 2-digit integer; the same applies to m.
Sample Input 1
1 23
Sample Output 1
1 23
1:23 is a confusing time because, after swapping its top-right and bottom-left digits on the clock, it reads 2:13.
Thus, the answer is 1:23.
Your answer is considered correct even if you print 01 23 with a leading zero.
Sample Input 2
19 57
Sample Output 2
20 0
The next confusing time after 19:57 is 20:00.
Sample Input 3
20 40
Sample Output 3
21 0
Note that 24:00 is an invalid notation in the 24-hour system.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
H 行 W 列のマス目があり、そのうち二つの異なるマスに駒が置かれています。
マス目の状態は H 個の長さ W の文字列 S_1, \dots, S_H で表されます。S_{i, j} = o ならば i 行目 j 列目のマスに駒が置かれていることを、S_{i, j} = - ならばそのマスには駒が置かれていないことを表します。なお、S_{i, j} は文字列 S_i の j 文字目を指します。
一方の駒をマス目の外側に出ないように上下左右の隣接するマスに動かすことを繰り返すとき、もう一方の駒と同じマスに移動させるためには最小で何回動かす必要がありますか？
制約
- 2 \leq H, W \leq 100
- H, W は整数
- S_i \, (1 \leq i \leq H) は
oおよび-のみからなる長さ W の文字列 - S_{i, j} =
oとなる整数 1 \leq i \leq H, 1 \leq j \leq W の組がちょうど二つ存在する
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 \vdots S_H
出力
答えを出力せよ。
入力例 1
2 3 --o o--
出力例 1
3
1 行目 3 列目に置かれている駒を 下 \rightarrow 左 \rightarrow 左 と移動すると 3 回でもう一方の駒と同じマスに移動させることができます。2 回以下で移動させることはできないので、3 を出力します。
入力例 2
5 4 -o-- ---- ---- ---- -o--
出力例 2
4
Score : 200 points
Problem Statement
There is a grid with H horizontal rows and W vertical columns, in which two distinct squares have a piece.
The state of the squares is represented by H strings S_1, \dots, S_H of length W. S_{i, j} = o means that there is a piece in the square at the i-th row from the top and j-th column from the left; S_{i, j} = - means that the square does not have a piece. Here, S_{i, j} denotes the j-th character of the string S_i.
Consider repeatedly moving one of the pieces to one of the four adjacent squares. It is not allowed to move the piece outside the grid. How many moves are required at minimum for the piece to reach the square with the other piece?
Constraints
- 2 \leq H, W \leq 100
- H and W are integers.
- S_i \, (1 \leq i \leq H) is a string of length W consisting of
oand-. - There exist exactly two pairs of integers 1 \leq i \leq H, 1 \leq j \leq W such that S_{i, j} =
o.
Input
Input is given from Standard Input in the following format:
H W S_1 \vdots S_H
Output
Print the answer.
Sample Input 1
2 3 --o o--
Sample Output 1
3
The piece at the 1-st row from the top and 3-rd column from the left can reach the square with the other piece in 3 moves: down, left, left. Since it is impossible to do so in two or less moves, 3 should be printed.
Sample Input 2
5 4 -o-- ---- ---- ---- -o--
Sample Output 2
4
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
文字列 S,T が与えられます。S は英小文字からなり、T は S に英小文字を 1 つ挿入して作られたことがわかっています。
挿入された文字は T の先頭から何番目の文字であるか求めてください。
複数の候補が考えられる場合はいずれか 1 つを求めてください。
制約
- 1 \leq |S| \leq 5\times 10^5
- S は英小文字からなる
- T は S に英小文字を 1 つ挿入して作られた文字列である
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
答えを出力せよ。なお、答えが複数考えられる場合はどれを出力しても正解となる。
入力例 1
atcoder atcorder
出力例 1
5
T の先頭から 5 番目の文字 r が挿入された文字です。
入力例 2
million milllion
出力例 2
5
T の先頭から 3,4,5 番目の文字のいずれかが挿入された文字です。
よって、3,4,5 のいずれかを出力すると正解となります。
入力例 3
vvwvw vvvwvw
出力例 3
3
Score : 300 points
Problem Statement
You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.
Find the position of the inserted character in T.
If there are multiple candidates, find any of them.
Constraints
- 1 \leq |S| \leq 5\times 10^5
- S consists of lowercase English letters.
- T is obtained by inserting a lowercase English letter into S.
Input
The input is given from Standard Input in the following format:
S T
Output
Print an integer i, representing that the inserted character is the i-th character from the beginning of T. If there are multiple possible answers, printing any of them is accepted.
Sample Input 1
atcoder atcorder
Sample Output 1
5
The 5-th character from the beginning of T, r, is inserted.
Sample Input 2
million milllion
Sample Output 2
5
One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.
Sample Input 3
vvwvw vvvwvw
Sample Output 3
3