Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
チーム高橋とチーム青木が、チーム高橋を先攻として野球を行なっています。
現在、9 回表までが終了し、9 回裏が始まろうとしています。
試合において、チーム高橋は i 回表 (1\leq i\leq 9) に A_i 点を取り、チーム青木は j 回裏 (1\leq j\leq 8) に B_j 点を取りました。
ここで、9 回表の終了時点でチーム高橋の得点はチーム青木の得点以上です。
チーム青木は 9 回裏に最低何点取れば勝利することができるか求めてください。
ただし、9 回裏の終了時点で同点であった場合は引き分けとなり、すなわちチーム青木が勝利するためには 9 回裏の終了時点でチーム高橋より真に多くの点をとっている必要があるものとします。
なお、（ある時点における）チーム高橋の得点はそれまでの回の表に取った点数の合計であり、チーム青木の得点はそれまでの回の裏に取った点数の合計です。
制約
- 0\leq A_i, B_j\leq 99
- A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 + A_8 + A_9 \geq B_1 + B_2 + B_3 + B_4 + B_5 + B_6 + B_7 + B_8
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
A_1 A_2 A_3 A_4 A_5 A_6 A_7 A_8 A_9 B_1 B_2 B_3 B_4 B_5 B_6 B_7 B_8
出力
チーム青木が勝利するために 9 回裏に取る必要のある最小の得点を出力せよ。
入力例 1
0 1 0 1 2 2 0 0 1 1 1 0 0 0 0 1 0
出力例 1
5
9 回表の終了時点でチーム高橋の得点は 7 点、チーム青木の得点は 3 点となっています。
よって、チーム青木は9 回裏に 5 点取れば 7-8 となり、勝利することができます。
9 回裏に 4 点では、引き分けとなり勝利できないことに注意してください。
入力例 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力例 2
1
Score: 100 points
Problem Statement
Team Takahashi and Team Aoki are playing a baseball game, with Team Takahashi batting first.
Currently, the game has finished through the top of the ninth inning, and the bottom of the ninth is about to begin.
Team Takahashi scored A_i runs in the top of the i-th inning (1\leq i\leq 9), and Team Aoki scored B_j runs in the bottom of the j-th inning (1\leq j\leq 8).
At the end of the top of the ninth, Team Takahashi's score is not less than Team Aoki's score.
Determine the minimum number of runs Team Aoki needs to score in the bottom of the ninth to win the game.
Here, if the game is tied at the end of the bottom of the ninth, it results in a draw. Therefore, for Team Aoki to win, they must score strictly more runs than Team Takahashi by the end of the bottom of the ninth.
Team Takahashi's score at any point is the total runs scored in the tops of the innings up to that point, and Team Aoki's score is the total runs scored in the bottoms of the innings.
Constraints
- 0\leq A_i, B_j\leq 99
- A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 + A_8 + A_9 \geq B_1 + B_2 + B_3 + B_4 + B_5 + B_6 + B_7 + B_8
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A_1 A_2 A_3 A_4 A_5 A_6 A_7 A_8 A_9 B_1 B_2 B_3 B_4 B_5 B_6 B_7 B_8
Output
Print the minimum number of runs Team Aoki needs to score in the bottom of the ninth inning to win.
Sample Input 1
0 1 0 1 2 2 0 0 1 1 1 0 0 0 0 1 0
Sample Output 1
5
At the end of the top of the ninth inning, Team Takahashi has scored seven runs, and Team Aoki has scored three runs.
Therefore, if Team Aoki scores five runs in the bottom of the ninth, the scores will be 7-8, allowing them to win.
Note that scoring four runs would result in a draw and not a victory.
Sample Input 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample Output 2
1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
英小文字からなる 2 文字以上の文字列 S が与えられます。
S の先頭の文字と末尾の文字が同じ文字かどうか判定してください。
制約
- S は英小文字からなる長さ 2 以上 10 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の先頭の文字と末尾の文字が同じ文字ならば Yes を、異なる文字ならば No を出力せよ。
入力例 1
luminol
出力例 1
Yes
先頭の文字は l、末尾の文字は l で一致しています。したがって Yes を出力してください。
入力例 2
rule
出力例 2
No
先頭の文字は r、末尾の文字は e で一致していません。したがって No を出力してください。
Score : 100 points
Problem Statement
You are given a string S of length at least 2 consisting of lowercase English letters.
Determine whether the first character and the last character of S are the same.
Constraints
- S is a string of length between 2 and 10, inclusive, consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
If the first character and the last character of S are the same, output Yes; otherwise, output No.
Sample Input 1
luminol
Sample Output 1
Yes
The first character is l and the last character is l, which match. Thus, output Yes.
Sample Input 2
rule
Sample Output 2
No
The first character is r and the last character is e, which do not match. Thus, output No.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋君は英小文字からなる文字列 S をキーボードで入力しようとしました。
高橋君は画面を見ずにキーボードだけを見てタイピングをしていました。
誤って別の英小文字を入力してしまったときにはその直後にバックスペースキーを押しましたが、バックスペースキーが壊れていたため誤って入力された文字は消去されず、実際に入力された文字列は文字列 T となりました。
また、英小文字以外のキーを誤って押してしまうことはありませんでした。
T のうち高橋君が誤って入力した文字でないものを正しく入力された文字であると定めます。
正しく入力された文字が T の何文字目であるか答えてください。
制約
- S, T は長さ 1 以上 2 \times 10^5 以下の英小文字からなる文字列
- T は問題文中の手続きにより得られる文字列
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
S の長さを |S| として、正しく入力された文字が A_1, A_2, \ldots, A_{|S|} 文字目であるとき A_1, A_2, \ldots, A_{|S|} の値をこの順に空白区切りで出力せよ。
ただし、出力は昇順になるようにせよ。すなわち、各 1 \leq i \leq |S| - 1 に対して A_i < A_{i + 1} を満たすようにせよ。
入力例 1
abc axbxyc
出力例 1
1 3 6
高橋君のタイピングの一連の流れは以下のようになります。
aを入力する。bを入力しようとするが、誤ってxを入力してしまう。- バックスペースキーを押すが、文字の削除は行われない。
bを入力する。cを入力しようとするが、誤ってxを入力してしまう。- バックスペースキーを押すが、文字の削除は行われない。
cを入力しようとするが、誤ってyを入力してしまう。- バックスペースキーを押すが、文字の削除は行われない。
cを入力する。
正しく入力された文字は 1, 3, 6 文字目です。
入力例 2
aaaa bbbbaaaa
出力例 2
5 6 7 8
入力例 3
atcoder atcoder
出力例 3
1 2 3 4 5 6 7
高橋君が誤った文字を入力することはありませんでした。
Score: 200 points
Problem Statement
Takahashi tried to type a string S consisting of lowercase English letters using a keyboard.
He was typing while looking only at the keyboard, not the screen.
Whenever he mistakenly typed a different lowercase English letter, he immediately pressed the backspace key. However, the backspace key was broken, so the mistakenly typed letter was not deleted, and the actual string typed was T.
He did not mistakenly press any keys other than those for lowercase English letters.
The characters in T that were not mistakenly typed are called correctly typed characters.
Determine the positions in T of the correctly typed characters.
Constraints
- S and T are strings of lowercase English letters with lengths between 1 and 2 \times 10^5, inclusive.
- T is a string obtained by the procedure described in the problem statement.
Input
The input is given from Standard Input in the following format:
S T
Output
Let |S| be the length of S. If the correctly typed characters are the A_1-th, A_2-th, \ldots, A_{|S|}-th characters of T, print the values of A_1, A_2, \ldots, A_{|S|} in this order, separated by spaces.
Ensure that the output is in ascending order. That is, A_i < A_{i + 1} should hold for each 1 \leq i \leq |S| - 1.
Sample Input 1
abc axbxyc
Sample Output 1
1 3 6
The sequence of Takahashi's typing is as follows:
- Type
a. - Try to type
bbut mistakenly typex. - Press the backspace key, but the character is not deleted.
- Type
b. - Try to type
cbut mistakenly typex. - Press the backspace key, but the character is not deleted.
- Try to type
cbut mistakenly typey. - Press the backspace key, but the character is not deleted.
- Type
c.
The correctly typed characters are the first, third, and sixth characters.
Sample Input 2
aaaa bbbbaaaa
Sample Output 2
5 6 7 8
Sample Input 3
atcoder atcoder
Sample Output 3
1 2 3 4 5 6 7
Takahashi did not mistakenly type any characters.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋君は漢文の勉強をしていて、漢字を読む順番が分からず困っています。高橋君を助けましょう！
1 から N までの N 個の整数が小さい方から順に 1 列に並んでいます。
整数の間に M 個の「レ」が挟まっています。i 個目の「レ」は、整数 a_i と整数 a_i + 1 の間にあります。
あなたは次の手順に従って、N 個の整数を 1 回ずつ全て読みます。
- まず、頂点に 1 から N までの番号がついた N 頂点 M 辺の無向グラフ G を考える。i 本目の辺は頂点 a_i と頂点 a_i + 1 を結んでいる。
- そして、読まれていない整数が無くなるまで次の操作を繰り返す。
- 読まれていない整数のうち最小のものを x とする。頂点 x が含まれる連結成分 C を選び、C に含まれる頂点の番号を大きい方から順に全て読む。
例えば、整数と「レ」が
という順番で並んでいる場合を考えます。(この場合 N = 5, M = 3, a = (1, 3, 4) です。)
このとき、整数が読まれる順番は以下の手順によって 2, 1, 5, 4, 3 に決定します。
- 最初、読まれていない整数のうち最小のものは 1 であり、グラフ G の頂点 1 を含む連結成分に含まれる頂点は \lbrace 1, 2 \rbrace である。よって 2, 1 がこの順で読まれる。
- 次に、読まれていない整数のうち最小のものは 3 であり、グラフ G の頂点 3 を含む連結成分に含まれる頂点は \lbrace 3, 4, 5 \rbrace である。よって 5, 4, 3 がこの順で読まれる。
- すべての整数が読まれたので手順を終了する。
N, M, (a_1, a_2, \dots, a_M) が入力として与えられるので、 N 個の整数を読む順番を出力してください。
連結成分とは
あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。グラフが 連結 であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。
制約
- 1 \leq N \leq 100
- 0 \leq M \leq N - 1
- 1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 a_2 \dots a_M
出力
答えを以下の形式で出力せよ。ここで p_i は、i 番目に読まれる整数を意味する。
p_1 p_2 \dots p_N
入力例 1
5 3 1 3 4
出力例 1
2 1 5 4 3
問題文の例にある通り、整数と「レ」が
という順で並んでいる場合は 2, 1, 5, 4, 3 の順で読みます。
入力例 2
5 0
出力例 2
1 2 3 4 5
「レ」が存在しない場合もあります。
入力例 3
10 6 1 2 3 7 8 9
出力例 3
4 3 2 1 5 6 10 9 8 7
Score : 200 points
Problem Statement
Studying Kanbun, Takahashi is having trouble figuring out the order to read words. Help him out!
There are N integers from 1 through N arranged in a line in ascending order.
Between them are M "レ" marks. The i-th "レ" mark is between the integer a_i and integer (a_i + 1).
You read each of the N integers once by the following procedure.
- Consider an undirected graph G with N vertices numbered 1 through N and M edges. The i-th edge connects vertex a_i and vertex (a_i+1).
- Repeat the following operation until there is no unread integer:
- let x be the minimum unread integer. Choose the connected component C containing vertex x, and read all the numbers of the vertices contained in C in descending order.
For example, suppose that integers and "レ" marks are arranged in the following order:
(In this case, N = 5, M = 3, and a = (1, 3, 4).)
Then, the order to read the integers is determined to be 2, 1, 5, 4, and 3, as follows:
- At first, the minimum unread integer is 1, and the connected component of G containing vertex 1 has vertices \lbrace 1, 2 \rbrace, so 2 and 1 are read in this order.
- Then, the minimum unread integer is 3, and the connected component of G containing vertex 3 has vertices \lbrace 3, 4, 5 \rbrace, so 5, 4, and 3 are read in this order.
- Now that all integers are read, terminate the procedure.
Given N, M, and (a_1, a_2, \dots, a_M), print the order to read the N integers.
What is a connected component?
A subgraph of a graph is a graph obtained by choosing some vertices and edges from the original graph.A graph is said to be connected if and only if one can travel between any two vertices in the graph via edges.
A connected component is a connected subgraph that is not contained in any larger connected subgraph.
Constraints
- 1 \leq N \leq 100
- 0 \leq M \leq N - 1
- 1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M a_1 a_2 \dots a_M
Output
Print the answer in the following format, where p_i is the i-th integers to read.
p_1 p_2 \dots p_N
Sample Input 1
5 3 1 3 4
Sample Output 1
2 1 5 4 3
As described in the Problem Statement, if integers and "レ" marks are arranged in the following order:
then the integers are read in the following order: 2, 1, 5, 4, and 3.
Sample Input 2
5 0
Sample Output 2
1 2 3 4 5
There may be no "レ" mark.
Sample Input 3
10 6 1 2 3 7 8 9
Sample Output 3
4 3 2 1 5 6 10 9 8 7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。
1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するかどうか判定してください。
制約
- 2 \leq N \leq 2\times 10^5
- -10^9 \leq A_i \leq 10^9
- -10^9 \leq X \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 \ldots A_N
出力
1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するとき Yes、存在しないとき No と出力せよ。
入力例 1
6 5 3 1 4 1 5 9
出力例 1
Yes
A_6-A_3=9-4=5 です。
入力例 2
6 -4 -2 -7 -1 -8 -2 -8
出力例 2
No
A_i-A_j=-4 となる組 (i,j) は存在しません。
入力例 3
2 0 141421356 17320508
出力例 3
Yes
A_1-A_1=0 です。
Score : 300 points
Problem Statement
You are given a sequence of N numbers: A=(A_1,\ldots,A_N).
Determine whether there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X.
Constraints
- 2 \leq N \leq 2\times 10^5
- -10^9 \leq A_i \leq 10^9
- -10^9 \leq X \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N X A_1 \ldots A_N
Output
Print Yes if there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X, and No otherwise.
Sample Input 1
6 5 3 1 4 1 5 9
Sample Output 1
Yes
We have A_6-A_3=9-4=5.
Sample Input 2
6 -4 -2 -7 -1 -8 -2 -8
Sample Output 2
No
There is no pair (i,j) such that A_i-A_j=-4.
Sample Input 3
2 0 141421356 17320508
Sample Output 3
Yes
We have A_1-A_1=0.