実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
N 個の台が一列に並んでおり、左から i 番目の台の高さは H_i です。
高橋君は最初、左端の台の上に立っています。
高橋君は高い所が好きなので、次のルールで可能な限り移動を繰り返します。
- いま立っているのが右端の台ではなく、かつ、右隣にある台の高さが自分がいま立っている台より高いとき、右隣の台に移動する
最終的に高橋君が立っている台の高さを求めてください。
制約
- 2 \leq N \leq 10^5
- 1 \leq H_i \leq 10^9
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N H_1 \ldots H_N
出力
答えを出力せよ。
入力例 1
5 1 5 10 4 2
出力例 1
10
最初、高橋君は左端にある高さ 1 の台に立っています。右隣の台の高さは 5 であり、いま立っている台より高いので、右隣の台に移動します。
移動後、高橋君は左から 2 番目にある高さ 5 の台に立っています。右隣の台の高さは 10 であり、いま立っている台より高いので、右隣の台に移動します。
移動後、高橋君は左から 3 番目にある高さ 10 の台に立っています。右隣の台の高さは 4 であり、いま立っている台より低いので、高橋君は移動をやめます。
よって、最終的に高橋君が立っている台の高さは 10 です。
入力例 2
3 100 1000 100000
出力例 2
100000
入力例 3
4 27 1828 1828 9242
出力例 3
1828
Score : 200 points
Problem Statement
There are N platforms arranged in a row. The height of the i-th platform from the left is H_i.
Takahashi is initially standing on the leftmost platform.
Since he likes heights, he will repeat the following move as long as possible.
- If the platform he is standing on is not the rightmost one, and the next platform to the right has a height greater than that of the current platform, step onto the next platform.
Find the height of the final platform he will stand on.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq H_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N H_1 \ldots H_N
Output
Print the answer.
Sample Input 1
5 1 5 10 4 2
Sample Output 1
10
Takahashi is initially standing on the leftmost platform, whose height is 1. The next platform to the right has a height of 5 and is higher than the current platform, so he steps onto it.
He is now standing on the 2-nd platform from the left, whose height is 5. The next platform to the right has a height of 10 and is higher than the current platform, so he steps onto it.
He is now standing on the 3-rd platform from the left, whose height is 10. The next platform to the right has a height of 4 and is lower than the current platform, so he stops moving.
Thus, the height of the final platform Takahashi will stand on is 10.
Sample Input 2
3 100 1000 100000
Sample Output 2
100000
Sample Input 3
4 27 1828 1828 9242
Sample Output 3
1828
実行時間制限: 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 点
問題文
1, 2, \ldots, N の番号がついた N 人の人が二次元平面上におり、人 i は座標 (X_i,Y_i) で表される地点にいます。
人 1 がウイルスに感染しました。ウイルスに感染した人から距離が D 以内にいる人にウイルスはうつります。
ただし、距離はユークリッド距離、すなわち 2 点 (a_1, a_2) と (b_1, b_2) に対し、この 2 点間の距離が \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2} であるものとして定められています。
十分に時間が経過した、すなわち人 i がウイルスに感染しているならば 人 i との距離が D 以内にいるすべての人がウイルスに感染している状態になったときに、各 i について人 i がウイルスに感染しているか判定してください。
制約
- 1 \leq N, D \leq 2000
- -1000 \leq X_i, Y_i \leq 1000
- i \neq j のとき (X_i, Y_i) \neq (X_j, Y_j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
N 行出力せよ。i 行目には、人 i がウイルスに感染しているならば Yes を、そうでないならば No を出力せよ。
入力例 1
4 5 2 -1 3 1 8 8 0 5
出力例 1
Yes Yes No Yes
人 1 と人 2 の距離は \sqrt 5 であるため、人 2 はウイルスに感染します。
また、人 2 と人 4 の距離は 5 であるため、人 4 はウイルスに感染します。
人 3 は距離 5 以内に人がいないので、ウイルスに感染することはありません。
入力例 2
3 1 0 0 -1000 -1000 1000 1000
出力例 2
Yes No No
入力例 3
9 4 3 2 6 -1 1 6 6 5 -2 -3 5 3 2 -3 2 1 2 6
出力例 3
Yes No No Yes Yes Yes Yes Yes No
Score : 300 points
Problem Statement
There are N people numbered 1, 2, \ldots, N on a two-dimensional plane, and person i is at the point represented by the coordinates (X_i,Y_i).
Person 1 has been infected with a virus. The virus spreads to people within a distance of D from an infected person.
Here, the distance is defined as the Euclidean distance, that is, for two points (a_1, a_2) and (b_1, b_2), the distance between these two points is \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2}.
After a sufficient amount of time has passed, that is, when all people within a distance of D from person i are infected with the virus if person i is infected, determine whether person i is infected with the virus for each i.
Constraints
- 1 \leq N, D \leq 2000
- -1000 \leq X_i, Y_i \leq 1000
- (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Print N lines. The i-th line should contain Yes if person i is infected with the virus, and No otherwise.
Sample Input 1
4 5 2 -1 3 1 8 8 0 5
Sample Output 1
Yes Yes No Yes
The distance between person 1 and person 2 is \sqrt 5, so person 2 gets infected with the virus.
Also, the distance between person 2 and person 4 is 5, so person 4 gets infected with the virus.
Person 3 has no one within a distance of 5, so they will not be infected with the virus.
Sample Input 2
3 1 0 0 -1000 -1000 1000 1000
Sample Output 2
Yes No No
Sample Input 3
9 4 3 2 6 -1 1 6 6 5 -2 -3 5 3 2 -3 2 1 2 6
Sample Output 3
Yes No No Yes Yes Yes Yes Yes No
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
非負整数 K に対して、以下のようにレベル K のカーペットを定義します。
- レベル 0 のカーペットは黒いマス 1 個のみからなる 1\times 1 のグリッドである。
- K>0 のとき、レベル K のカーペットは 3^K\times 3^K のグリッドである。
このグリッドを 3^{K-1}\times 3^{K-1} のブロック 9 個に分割したとき、
- 中央のブロックはすべて白いマスからなる。
- 他の 8 個のブロックは、レベル (K-1) のカーペットである。
非負整数 N が与えられます。
レベル N のカーペットを出力の形式に従って出力してください。
制約
- 0\leq N \leq 6
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
3^N 行出力せよ。
i 行目 (1\leq i\leq 3^N) には、. と # からなる長さ 3^N の文字列 S_i を出力せよ。
S_i の j 文字目 (1\leq j\leq 3^N) は、レベル N のカーペットの上から i 行目かつ左から j 列目のマスが黒いとき # とし、白いとき . とせよ。
入力例 1
1
出力例 1
### #.# ###
レベル 1 のカーペットは次のような 3\times 3 のグリッドです。
これを出力形式にしたがって出力すると出力例のようになります。
入力例 2
2
出力例 2
######### #.##.##.# ######### ###...### #.#...#.# ###...### ######### #.##.##.# #########
レベル 2 のカーペットは 9\times 9 のグリッドとなります。
Score : 250 points
Problem Statement
For a non-negative integer K, we define a level-K carpet as follows:
- A level-0 carpet is a 1 \times 1 grid consisting of a single black cell.
- For K > 0, a level-K carpet is a 3^K \times 3^K grid. When this grid is divided into nine 3^{K-1} \times 3^{K-1} blocks:
- The central block consists entirely of white cells.
- The other eight blocks are level-(K-1) carpets.
You are given a non-negative integer N.
Print a level-N carpet according to the specified format.
Constraints
- 0 \leq N \leq 6
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print 3^N lines.
The i-th line (1 \leq i \leq 3^N) should contain a string S_i of length 3^N consisting of . and #.
The j-th character of S_i (1 \leq j \leq 3^N) should be # if the cell at the i-th row from the top and j-th column from the left of a level-N carpet is black, and . if it is white.
Sample Input 1
1
Sample Output 1
### #.# ###
A level-1 carpet is a 3 \times 3 grid as follows:
When output according to the specified format, it looks like the sample output.
Sample Input 2
2
Sample Output 2
######### #.##.##.# ######### ###...### #.#...#.# ###...### ######### #.##.##.# #########
A level-2 carpet is a 9 \times 9 grid.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
AtCoder 国には 1 から N の番号がついた N 個の都市と、1 から N-1 の番号がついた N-1 個の道路があります。
道路 i を通ると都市 A_i と都市 B_i の間を相互に移動することができます。全ての都市は道路を使って互いに行き来できることが保証されます。
高橋くんは都市 1 を出発し、次のルールで旅をします。
- いまいる都市と道路で直接つながっている都市のうち、まだ訪れたことがない都市が存在するとき、そのような都市のうち番号が最も小さい都市へ移動する
- そのような都市が存在しないとき
- いまいる都市が都市 1 なら旅を終了する
- そうでないなら、いまいる都市を初めて訪れたときに直前にいた都市へ移動する
高橋くんが旅の過程で訪れる都市を順に答えてください。
制約
- 2 \leq N \leq 2\times 10^5
- 1\leq A_i,B_i \leq N
- 全ての都市は道路を使って互いに行き来できる
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
出力
高橋くんが訪れる都市を、旅の開始時及び終了時の都市 1 も含めて順に空白区切りで出力せよ。
入力例 1
4 1 2 4 2 3 1
出力例 1
1 2 4 2 1 3 1
高橋くんの旅は次のようになります。
- 最初都市 1 にいます。
- 都市 1 から道路で直接つながっている都市のうち未訪問なのは都市 2,3 です。番号が小さい都市 2 へ移動します。
- 都市 2 から道路で直接つながっている都市のうち未訪問なのは都市 4 です。都市 4 へ移動します。
- 都市 4 から道路で直接つながっている都市のうち未訪問の都市はありません。直前にいた都市 2 へ移動します。
- 都市 2 から道路で直接つながっている都市のうち未訪問の都市はありません。初めて都市 2 に来る直前にいた都市 1 へ移動します。
- 都市 1 から道路で直接つながっている都市のうち未訪問なのは都市 3 です。都市 3 へ移動します。
- 都市 3 から道路で直接つながっている都市のうち未訪問の都市はありません。直前にいた都市 1 へ移動します。
- 都市 1 から道路で直接つながっている都市のうち未訪問の都市はありません。旅を終了します。
入力例 2
5 1 2 1 3 1 4 1 5
出力例 2
1 2 1 3 1 4 1 5 1
Score : 400 points
Problem Statement
The Republic of AtCoder has N cities numbered 1 through N and N-1 roads numbered 1 through N-1. Road i connects City A_i and City B_i bidirectionally. It is guaranteed that one can travel between every pair of cities using roads.
Takahashi will depart City 1 and have a journey by repeating the following.
- If there are unvisited cities that are directly connected to the city Takahashi is in now, he goes to the city with the smallest number among those cities.
- Otherwise,
- if he is in City 1, he ends the journey;
- otherwise, he goes to the city he was in just before visiting the current city for the first time.
Find the sequence of cities visited by Takahashi in the order he visits them.
Constraints
- 2 \leq N \leq 2\times 10^5
- 1\leq A_i,B_i \leq N
- It is possible to travel between every pair of cities using roads.
Input
Input is given from Standard Input in the following format:
N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
Output
Print the sequence of cities visited by Takahashi in the order he visits them, including City 1 at the beginning and end of the journey, with spaces in between.
Sample Input 1
4 1 2 4 2 3 1
Sample Output 1
1 2 4 2 1 3 1
His journey will be as follows.
- Start in City 1.
- The unvisited cities directly connected to City 1 are City 2 and 3. Go to the city with the smaller number, that is, City 2.
- The unvisited city directly connected to City 2 is City 4. Go there.
- There is no unvisited city directly connected to City 4. Go back to City 2.
- There is no unvisited city directly connected to City 2. Go to City 1, where he was in just before visiting City 2 for the first time.
- The unvisited city directly connected to City 1 is City 3. Go there.
- There is no unvisited city directly connected to City 3. Go back to City 1.
- There is no unvisited city directly connected to City 1. End the journey.
Sample Input 2
5 1 2 1 3 1 4 1 5
Sample Output 2
1 2 1 3 1 4 1 5 1