実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
野球少年の高橋君は今年とても良い子にしていたので、サンタさんはバットかグローブのうち値段が高い方を高橋君にプレゼントすることにしました。
バットの値段が B 円、グローブの値段が G 円 (B\neq G) のとき、サンタさんが高橋君にプレゼントするのはどちらですか？
制約
- B,G は 1 以上 1000 以下の相異なる整数
入力
入力は以下の形式で標準入力から与えられる。
B G
出力
サンタさんが高橋君にプレゼントするのがバットであるとき Bat を、グローブであるとき Glove を出力せよ。
入力例 1
300 100
出力例 1
Bat
バットの方がグローブより値段が高いので、サンタさんは高橋君にバットをプレゼントします。
入力例 2
334 343
出力例 2
Glove
グローブの方がバットより値段が高いので、サンタさんは高橋君にグローブをプレゼントします。
Score : 100 points
Problem Statement
Takahashi, a young baseball enthusiast, has been a very good boy this year, so Santa has decided to give him a bat or a glove, whichever is more expensive.
If a bat costs B yen and a glove costs G yen (B\neq G), which one will Santa give to Takahashi?
Constraints
- B and G are different integers between 1 and 1000, inclusive.
Input
The input is given from Standard Input in the following format:
B G
Output
If Santa gives Takahashi a bat, print Bat; if Santa gives him a glove, print Glove.
Sample Input 1
300 100
Sample Output 1
Bat
The bat is more expensive than the glove, so Santa will give Takahashi the bat.
Sample Input 2
334 343
Sample Output 2
Glove
The glove is more expensive than the bat, so Santa will give Takahashi the glove.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
英大文字・英小文字からなる空でない文字列 S が与えられます。以下の条件が満たされているか判定してください。
- S の先頭の文字は大文字であり、それ以外の文字はすべて小文字である。
制約
- 1 \leq |S| \leq 100（|S| は文字列 S の長さ）
- S の各文字は英大文字または英小文字である。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
条件が満たされていれば Yes、そうでなければ No を出力せよ。
入力例 1
Capitalized
出力例 1
Yes
Capitalized の先頭の文字 C は大文字であり、それ以外の文字 apitalized はすべて小文字であるため、Yes を出力します。
入力例 2
AtCoder
出力例 2
No
AtCoder は先頭以外にも大文字 C を含むため、No を出力します。
入力例 3
yes
出力例 3
No
yes の先頭の文字 y は大文字でないため、No を出力します。
入力例 4
A
出力例 4
Yes
Score: 100 points
Problem Statement
You are given a non-empty string S consisting of uppercase and lowercase English letters. Determine whether the following condition is satisfied:
- The first character of S is uppercase, and all other characters are lowercase.
Constraints
- 1 \leq |S| \leq 100 (|S| is the length of the string S.)
- Each character of S is an uppercase or lowercase English letter.
Input
The input is given from Standard Input in the following format:
S
Output
If the condition is satisfied, print Yes; otherwise, print No.
Sample Input 1
Capitalized
Sample Output 1
Yes
The first character C of Capitalized is uppercase, and all other characters apitalized are lowercase, so you should print Yes.
Sample Input 2
AtCoder
Sample Output 2
No
AtCoder contains an uppercase letter C that is not at the beginning, so you should print No.
Sample Input 3
yes
Sample Output 3
No
The first character y of yes is not uppercase, so you should print No.
Sample Input 4
A
Sample Output 4
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は RPG を作っています。高橋君は 2 枚の RPG 世界のマップが一致しているかを判定するプログラムを書くことにしました。
縦 H マス横 W マスの 2 つのグリッド A, B があります。グリッドの各マスには # と . のいずれかの文字が書かれています。
A と B の上から i 行目、左から j 列目に書かれている文字をそれぞれ A_{i, j}, B_{i, j} と呼びます。
次の 2 種類の操作をそれぞれ 縦方向のシフト, 横方向のシフト と呼びます。
- j=1, 2, \dots, W について次の操作を同時に行う。
- A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} を A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j} に同時に置き換える。
- i = 1, 2, \dots, H について次の操作を同時に行う。
- A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} を A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1} に同時に置き換える。
次の条件を満たす非負整数の組 (s, t) は存在しますか？存在する場合は Yes を、存在しない場合は No を出力してください。
- 縦方向のシフトを s 回行い、次に横方向のシフトを t 回行った時、操作後の A が B と一致する。
ここで、A と B が一致するとは、1 \leq i \leq H, 1 \leq j \leq W を満たす整数の組 (i, j) すべてに対して A_{i, j} = B_{i, j} が成り立つことを言います。
制約
- 2 \leq H, W \leq 30
- A_{i,j},B_{i,j} は
#または. - H, W は整数
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}
出力
条件を満たす整数の組 (s, t) が存在する場合は Yes を、存在しない場合は No を出力せよ。
入力例 1
4 3 ..# ... .#. ... #.. ... .#. ...
出力例 1
Yes
(s, t) = (2, 1) とすると A と B を一致させることができます。
(s, t) = (2, 1) の時の操作の手順を説明します。はじめ、A は次の通りです。
..# ... .#. ...
まず、縦方向のシフトを行います。A は次のようになります。
... .#. ... ..#
次に、再び縦方向のシフトを行います。A は次のようになります。
.#. ... ..# ...
最後に、横方向のシフトを行います。A は次のようになり、これは B と一致しています。
#.. ... .#. ...
入力例 2
3 2 ## ## #. .. #. #.
出力例 2
No
どのように (s, t) を選んでも A と B を一致させることはできません。
入力例 3
4 5 ##### .#... .##.. ..##. ...## #...# ##### ...#.
出力例 3
Yes
入力例 4
10 30 ..........##########.......... ..........####....###.....##.. .....##....##......##...#####. ....####...##..#####...##...## ...##..##..##......##..##....# #.##....##....##...##..##..... ..##....##.##..#####...##...## ..###..###..............##.##. .#..####..#..............###.. #..........##................. ................#..........##. ######....................#### ....###.....##............#### .....##...#####......##....##. .#####...##...##....####...##. .....##..##....#...##..##..##. ##...##..##.....#.##....##.... .#####...##...##..##....##.##. ..........##.##...###..###.... ...........###...#..####..#...
出力例 4
Yes
Score : 200 points
Problem Statement
Takahashi is developing an RPG. He has decided to write a code that checks whether two maps are equal.
We have grids A and B with H horizontal rows and W vertical columns. Each cell in the grid has a symbol # or . written on it.
The symbols written on the cell at the i-th row from the top and j-th column from the left in A and B are denoted by A_{i, j} and B_{i, j}, respectively.
The following two operations are called a vertical shift and horizontal shift.
- For each j=1, 2, \dots, W, simultaneously do the following:
- simultaneously replace A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} with A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}.
- For each i = 1, 2, \dots, H, simultaneously do the following:
- simultaneously replace A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} with A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}.
Is there a pair of non-negative integers (s, t) that satisfies the following condition? Print Yes if there is, and No otherwise.
- After applying a vertical shift s times and a horizontal shift t times, A is equal to B.
Here, A is said to be equal to B if and only if A_{i, j} = B_{i, j} for all integer pairs (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W.
Constraints
- 2 \leq H, W \leq 30
- A_{i,j} is
#or., and so is B_{i,j}. - H and W are integers.
Input
The input is given from Standard Input in the following format:
H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}
Output
Print Yes if there is a conforming integer pair (s, t); print No otherwise.
Sample Input 1
4 3 ..# ... .#. ... #.. ... .#. ...
Sample Output 1
Yes
By choosing (s, t) = (2, 1), the resulting A is equal to B.
We describe the procedure when (s, t) = (2, 1) is chosen. Initially, A is as follows.
..# ... .#. ...
We first apply a vertical shift to make A as follows.
... .#. ... ..#
Then we apply another vertical shift to make A as follows.
.#. ... ..# ...
Finally, we apply a horizontal shift to make A as follows, which equals B.
#.. ... .#. ...
Sample Input 2
3 2 ## ## #. .. #. #.
Sample Output 2
No
No choice of (s, t) makes A equal B.
Sample Input 3
4 5 ##### .#... .##.. ..##. ...## #...# ##### ...#.
Sample Output 3
Yes
Sample Input 4
10 30 ..........##########.......... ..........####....###.....##.. .....##....##......##...#####. ....####...##..#####...##...## ...##..##..##......##..##....# #.##....##....##...##..##..... ..##....##.##..#####...##...## ..###..###..............##.##. .#..####..#..............###.. #..........##................. ................#..........##. ######....................#### ....###.....##............#### .....##...#####......##....##. .#####...##...##....####...##. .....##..##....#...##..##..##. ##...##..##.....#.##....##.... .#####...##...##..##....##.##. ..........##.##...###..###.... ...........###...#..####..#...
Sample Output 4
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
1, \dots, N と番号付けられた N 個の都市と、都市間を結ぶ M 本の道路があります。
i \, (1 \leq i \leq M) 番目の道路は都市 A_i と都市 B_i を結んでいます。
以下の指示に従い、N 行にわたって出力してください。
- 都市 i \, (1 \leq i \leq N) と道路で直接結ばれた都市が d_i 個あるとし、それらを昇順に都市 a_{i, 1}, \dots, a_{i, d_i} とおく。
- i \, (1 \leq i \leq N) 行目には、d_i + 1 個の整数 d_i, a_{i, 1}, \dots, a_{i, d_i} を、この順番で空白区切りで出力せよ。
制約
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
- (i \neq j) ならば (A_i, B_i) \neq (A_j, B_j)
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 \vdots A_M B_M
出力
問題文の指示に従い、N 行にわたって出力せよ。
入力例 1
6 6 3 6 1 3 5 6 2 5 1 2 1 6
出力例 1
3 2 3 6 2 1 5 2 1 6 0 2 2 6 3 1 3 5
都市 1 と道路で直接結ばれているのは都市 2, 3, 6 です。よって、d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6 であるので、1 行目には 3, 2, 3, 6 をこの順番で空白区切りで出力します。
a_{i, 1}, \dots, a_{i, d_i} は昇順に並んでいなければならないことに注意してください。例えば、1 行目に 3, 3, 2, 6 をこの順番で出力した場合、不正解となります。
入力例 2
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
出力例 2
4 2 3 4 5 4 1 3 4 5 4 1 2 4 5 4 1 2 3 5 4 1 2 3 4
Score : 200 points
Problem Statement
There are N cities numbered 1, \dots, N, and M roads connecting cities.
The i-th road (1 \leq i \leq M) connects city A_i and city B_i.
Print N lines as follows.
- Let d_i be the number of cities directly connected to city i \, (1 \leq i \leq N), and those cities be city a_{i, 1}, \dots, city a_{i, d_i}, in ascending order.
- The i-th line (1 \leq i \leq N) should contain d_i + 1 integers d_i, a_{i, 1}, \dots, a_{i, d_i} in this order, separated by spaces.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
- (A_i, B_i) \neq (A_j, B_j) if (i \neq j).
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 \vdots A_M B_M
Output
Print N lines as specified in the Problem Statement.
Sample Input 1
6 6 3 6 1 3 5 6 2 5 1 2 1 6
Sample Output 1
3 2 3 6 2 1 5 2 1 6 0 2 2 6 3 1 3 5
The cities directly connected to city 1 are city 2, city 3, and city 6. Thus, we have d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6, so you should print 3, 2, 3, 6 in the first line in this order, separated by spaces.
Note that a_{i, 1}, \dots, a_{i, d_i} must be in ascending order. For instance, it is unacceptable to print 3, 3, 2, 6 in the first line in this order.
Sample Input 2
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
Sample Output 2
4 2 3 4 5 4 1 3 4 5 4 1 2 4 5 4 1 2 3 5 4 1 2 3 4
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
列 S_n を次のように定義します。
- S_1 は 1 つの 1 からなる長さ 1 の列である。
- S_n (n は 2 以上の整数) は S_{n-1}, n, S_{n-1} をこの順につなげた列である。
たとえば S_2,S_3 は次のような列です。
- S_2 は S_1, 2, S_1 をこの順につなげた列なので 1,2,1 である。
- S_3 は S_2, 3, S_2 をこの順につなげた列なので 1,2,1,3,1,2,1 である。
N が与えられるので、列 S_N をすべて出力してください。
制約
- N は整数
- 1 \leq N \leq 16
入力
入力は以下の形式で標準入力から与えられる。
N
出力
S_N を空白区切りで出力せよ。
入力例 1
2
出力例 1
1 2 1
問題文の説明にある通り、S_2 は 1,2,1 となります。
入力例 2
1
出力例 2
1
入力例 3
4
出力例 3
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
S_4 は S_3,4,S_3 をこの順につなげた列です。
Score : 300 points
Problem Statement
We define sequences S_n as follows.
- S_1 is a sequence of length 1 containing a single 1.
- S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.
For example, S_2 and S_3 is defined as follows.
- S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
- S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.
Given N, print the entire sequence S_N.
Constraints
- N is an integer.
- 1 \leq N \leq 16
Input
Input is given from Standard Input in the following format:
N
Output
Print S_N, with spaces in between.
Sample Input 1
2
Sample Output 1
1 2 1
As described in the Problem Statement, S_2 is 1,2,1.
Sample Input 2
1
Sample Output 2
1
Sample Input 3
4
Sample Output 3
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
- S_4 is a concatenation of S_3, 4, and S_3, in this order.