実行時間制限: 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 [m] の場所では \dfrac{x}{100} [MPa] になるものとします。
水深 D [m] の場所の水圧は何 [MPa] ですか？
制約
- 1 \leq D \leq 10000
- D は整数である。
入力
入力は以下の形式で標準入力から与えられる。
D
出力
答えを出力せよ。想定解答との絶対誤差または相対誤差が 10^{-3} 以下であれば正解として扱われる。
入力例 1
1000
出力例 1
10
水深 1000 [m] の場所の水圧は 10 [MPa] です。10.0 や 9.999999 などを出力しても正解となります。
入力例 2
50
出力例 2
0.5
入力例 3
3141
出力例 3
31.41
Score : 100 points
Problem Statement
Let us assume that water pressure depends only on depth and is \dfrac{x}{100} megapascal at a depth of x meters.
What is the water pressure in megapascals at a depth of D meters?
Constraints
- 1 \leq D \leq 10000
- D is an integer.
Input
Input is given from Standard Input in the following format:
D
Output
Print the answer. Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-3}.
Sample Input 1
1000
Sample Output 1
10
The water pressure at a depth of 1000 meters is 10 megapascal. Outputs such as 10.0 and 9.999999 would also be accepted.
Sample Input 2
50
Sample Output 2
0.5
Sample Input 3
3141
Sample Output 3
31.41
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は 2 次元コード TaK Code を考案しました。以下の条件を全て満たすものが TaK Code です。
- 縦 9 マス 横 9 マスの領域である
- 左上及び右下の縦 3 マス 横 3 マスの領域に含まれる計 18 マスは全て黒である
- 左上及び右下の縦 3 マス 横 3 マスの領域に八方位で隣接する計 14 マスは全て白である
TaK Code を回転させることはできません。
縦 N マス、横 M マスのグリッドがあります。
グリッドの状態は N 個の長さ M の文字列 S_1,\ldots,S_N で与えられ、上から i 行目左から j 列目のマスは S_i の j 文字目が # のとき黒、. のとき白です。
グリッドに完全に含まれる縦 9 マス横 9 マスの領域で、TaK Code の条件を満たす箇所を全て求めてください。
制約
- 9 \leq N,M \leq 100
- N,M は整数である
- S_i は
.および#のみからなる長さ M の文字列である
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 \vdots S_N
出力
上から i 行目左から j 列目のマスを左上とする縦 9 マス 横 9 マスの領域が TaK Code の条件を満たす (i,j) の組全てを辞書順の昇順で 1 行に 1 組ずつ、i,j をこの順に空白区切りで出力せよ。
(i,j) の組の辞書順の昇順とは、i の昇順、i が等しい組は j の昇順にすることである。
入力例 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
出力例 1
1 1 1 10 7 7 10 2
TaK Code は以下のものです。# が黒マス、. が白マス、? が白黒どちらでもよいマスを表します。
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
入力で与えられたグリッドの上から 10 マス目左から 2 列目のマスを左上とする縦 9 マス 横 9 マスの領域は以下のようになっており、TaK Code の条件を満たします。
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
入力例 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
出力例 2
1 1
入力例 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
出力例 3
TaK Code の条件を満たす箇所が 1 つもないこともあります。
Score : 200 points
Problem Statement
Takahashi invented Tak Code, a two-dimensional code. A TaK Code satisfies all of the following conditions:
- It is a region consisting of nine horizontal rows and nine vertical columns.
- All the 18 cells in the top-left and bottom-right three-by-three regions are black.
- All the 14 cells that are adjacent (horizontally, vertically, or diagonally) to the top-left or bottom-right three-by-three region are white.
It is not allowed to rotate a TaK Code.
You are given a grid with N horizontal rows and M vertical columns.
The state of the grid is described by N strings, S_1,\ldots, and S_N, each of length M. The cell at the i-th row from the top and j-th column from the left is black if the j-th character of S_i is #, and white if it is ..
Find all the nine-by-nine regions, completely contained in the grid, that satisfy the conditions of a TaK Code.
Constraints
- 9 \leq N,M \leq 100
- N and M are integers.
- S_i is a string of length M consisting of
.and#.
Input
The input is given from Standard Input in the following format:
N M S_1 \vdots S_N
Output
For all pairs (i,j) such that the nine-by-nine region, whose top-left cell is at the i-th row from the top and j-th columns from the left, satisfies the conditions of a TaK Code, print a line containing i, a space, and j in this order.
The pairs must be sorted in lexicographical ascending order; that is, i must be in ascending order, and within the same i, j must be in ascending order.
Sample Input 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
Sample Output 1
1 1 1 10 7 7 10 2
A TaK Code looks like the following, where # is a black cell, . is a white cell, and ? can be either black or white.
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
In the grid given by the input, the nine-by-nine region, whose top-left cell is at the 10-th row from the top and 2-nd column from the left, satisfies the conditions of a TaK Code, as shown below.
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
Sample Input 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
Sample Output 2
1 1
Sample Input 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
Sample Output 3
There may be no region that satisfies the conditions of TaK Code.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
数字のみからなる長さ 6 の文字列が N 個与えられます。i \, (i = 1, 2, \dots, N) 番目のものを S_i と表します。
さらに、数字のみからなる長さ 3 の文字列が M 個与えられます。j \, (j = 1, 2, \dots, M) 番目のものを T_j と表します。
S_1, S_2, \dots, S_N のうち、末尾 3 文字が T_1, T_2, \dots, T_M のいずれかに一致するものの個数を求めてください。
制約
- 1 \leq N, M \leq 1000
- N, M は整数
- 全ての i = 1, 2, \dots, N に対し、S_i は数字のみからなる長さ 6 の文字列
- 全ての j = 1, 2, \dots, M に対し、T_j は数字のみからなる長さ 3 の文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N T_1 T_2 \vdots T_M
出力
答えを出力せよ。
入力例 1
3 3 142857 004159 071028 159 287 857
出力例 1
2
S_1 の末尾 3 文字は 857 であり、これは T_3 に一致します。
S_2 の末尾 3 文字は 159 であり、これは T_1 に一致します。
S_3 の末尾 3 文字は 028 であり、これは T_1, T_2, T_3 のいずれにも一致しません。
以上から、答えは 2 です。
入力例 2
5 4 235983 109467 823476 592801 000333 333 108 467 983
出力例 2
3
入力例 3
4 4 000000 123456 987111 000000 000 111 999 111
出力例 3
3
Score : 200 points
Problem Statement
You are given N strings of length six each, consisting of digits. Let S_i be the i-th (i = 1, 2, \dots, N) of them.
You are also given M strings of length three each, consisting of digits. Let T_j be the j-th (j = 1, 2, \dots, M) of them.
Find the number of strings among S_1, S_2, \dots, S_N whose last three characters coincide with one or more of T_1, T_2, \dots, T_M.
Constraints
- 1 \leq N, M \leq 1000
- N and M are integers.
- S_i is a string of length 6 consisting of digits, for all i = 1, 2, \dots, N.
- T_j is a string of length 3 consisting of digits, for all j = 1, 2, \dots, M.
Input
The input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N T_1 T_2 \vdots T_M
Output
Print the answer.
Sample Input 1
3 3 142857 004159 071028 159 287 857
Sample Output 1
2
The last three characters of S_1 are 857, which coincide with T_3.
The last three characters of S_2 are 159, which coincide with T_1.
The last three characters of S_3 are 028, which do not coincide with T_1, T_2, or T_3.
Thus, the answer is 2.
Sample Input 2
5 4 235983 109467 823476 592801 000333 333 108 467 983
Sample Output 2
3
Sample Input 3
4 4 000000 123456 987111 000000 000 111 999 111
Sample Output 3
3
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
数字からなる文字列 S が与えられます。
以下の条件を全て満たす文字列 T を 1122文字列 と呼びます。（定義は F 問題と同じです。）
- T は数字からなる空でない文字列
- |T| は偶数。ここで、 |T| は文字列 T の長さを表す
- T の 1 文字目から \frac{|T|}2 文字目までは全て同じ数字である
- T の \frac{|T|}2+1 文字目から |T| 文字目までは全て同じ数字である
- T の 1 文字目の数字に 1 を足すと |T| 文字目の数字になる
例えば 1122 や 01 、 444555 などは 1122文字列 ですが、 1222 や 90 は 1122文字列 ではありません。
S の 部分文字列 であって 1122文字列 であるものの個数を求めてください。
ただし、ある二つの部分文字列が文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えるものとします。
制約
- S は長さ 1 以上 10^6 以下の数字からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の空でない部分文字列であって 1122文字列 であるものの個数を出力せよ。
入力例 1
1122
出力例 1
2
以下の 2 つの部分文字列が条件を満たします。
- S の 2 文字目から 3 文字目を取り出した
12 - S の 1 文字目から 4 文字目を取り出した
1122
したがって、 2 を出力してください。
入力例 2
7788788
出力例 2
3
文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えることに注意してください。
入力例 3
2025
出力例 3
0
1122文字列 となる部分文字列が存在しない場合もあります。
入力例 4
1112222334445556555
出力例 4
11
Score : 300 points
Problem Statement
You are given a string S consisting of digits.
A string T is called a 1122-string if it satisfies all of the following conditions. (The definition is the same as in Problem F.)
- T is a non-empty string consisting of digits.
- |T| is even, where |T| denotes the length of string T.
- All characters from the 1-st through the \frac{|T|}2-th character of T are the same digit.
- All characters from the (\frac{|T|}2+1)-th through the |T|-th character of T are the same digit.
- Adding 1 to the digit of the 1-st character of T gives the digit of the |T|-th character.
For example, 1122, 01, and 444555 are 1122-strings, but 1222 and 90 are not 1122-strings.
Find the number of substrings of S that are 1122-strings.
Two substrings are counted separately if they are extracted from different positions, even if they are identical as strings.
Constraints
- S is a string consisting of digits with length between 1 and 10^6, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Output the number of non-empty substrings of S that are 1122-strings.
Sample Input 1
1122
Sample Output 1
2
The following two substrings satisfy the condition.
12extracted from the 2-nd through 3-rd characters of S1122extracted from the 1-st through 4-th characters of S
Thus, output 2.
Sample Input 2
7788788
Sample Output 2
3
Note that two substrings are counted separately if they are extracted from different positions, even if they are identical as strings.
Sample Input 3
2025
Sample Output 3
0
There may be no substring that is a 1122-string.
Sample Input 4
1112222334445556555
Sample Output 4
11