Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
ある日、高橋君は A 時 B 分ちょうどに、青木君は C 時 D 分 1 秒に起きました。
高橋君の起床時刻が青木君より早いならば Takahashi を、そうでないならば Aoki を出力してください。
制約
- 0 \leq A \leq 23
- 0 \leq B \leq 59
- 0 \leq C \leq 23
- 0 \leq D \leq 59
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
A B C D
出力
高橋君の起床時刻が青木君より早いならば Takahashi を、そうでないならば Aoki を出力せよ。
入力例 1
7 0 6 30
出力例 1
Aoki
高橋君は 7 時ちょうどに、青木君は 6 時 30 分 1 秒に起きました。
青木君の起床時刻の方が早いため、Aoki を出力します。
入力例 2
7 30 7 30
出力例 2
Takahashi
高橋君は 7 時 30 分ちょうどに、青木君は 7 時 30 分 1 秒に起きました。
高橋君の起床時刻の方が 1 秒だけ早いため、Takahashi を出力します。
入力例 3
0 0 23 59
出力例 3
Takahashi
ある日の 0 時 0 分ちょうどはその日の 0 時 1 分の 1 分前であり、
その日の 23 時 59 分の 1 分後、すなわちいわゆる 24 時ちょうどのことではありません。
よって、高橋君の起床時刻の方が早く、Takahashi を出力します。
Score : 100 points
Problem Statement
One day, Takahashi got up at exactly B minutes past A o'clock (in 24-hour clock), and Aoki got up at exactly D minutes and 1 second past C o'clock.
If Takahashi got up earlier than Aoki, print Takahashi; otherwise, print Aoki.
Constraints
- 0 \leq A \leq 23
- 0 \leq B \leq 59
- 0 \leq C \leq 23
- 0 \leq D \leq 59
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B C D
Output
If Takahashi got up earlier than Aoki, print Takahashi; otherwise, print Aoki.
Sample Input 1
7 0 6 30
Sample Output 1
Aoki
Takahashi got up at 7 sharp, and Aoki got up at 30 minutes and 1 second past 6 o'clock.
Aoki was the first to get up, so Aoki should be printed.
Sample Input 2
7 30 7 30
Sample Output 2
Takahashi
Takahashi got up at exactly half past 7, and Aoki got up at 30 minutes and 1 second past 7 o'clock.
Just by one second, Takahashi was the first to get up, so Takahashi should be printed.
Sample Input 3
0 0 23 59
Sample Output 3
Takahashi
0:00 in a day is one minute before 0:01, not one minute past 23:59 ("24:00").
Thus, Takahashi was the first to get up, so Takahashi should be printed.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
配信者の高橋君は L 時から R 時に配信をすることにしました。
高橋君には N 人のリスナーがおり、i 人目のリスナーは X_i 時から Y_i 時まで配信を見ることができます。
高橋君の配信を最初から最後まで見ることができるリスナーは何人いますか?
制約
- 1\leq N\leq 100
- 0\leq L\lt R\leq 23
- 0\leq X_i\lt Y_i\leq 23
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N L R X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
高橋君の配信を最初から最後まで見ることができるリスナーの数を出力せよ。
入力例 1
5 19 22 17 23 20 23 19 22 0 23 12 20
出力例 1
3
高橋君の配信を最初から最後まで見ることができるのは 1,3,4 人目のリスナーです。
入力例 2
3 12 13 0 1 0 1 0 1
出力例 2
0
高橋君の配信を最初から最後まで見ることができるリスナーはいません。
入力例 3
10 8 14 5 20 14 21 9 21 5 23 8 10 0 14 3 8 2 6 0 16 5 20
出力例 3
5
Score : 100 points
Problem Statement
Streamer Takahashi has decided to stream from L o'clock to R o'clock (using the 24-hour clock).
He has N listeners, and the i-th listener can watch the stream from X_i o'clock to Y_i o'clock.
How many listeners can watch Takahashi's stream from beginning to end?
Constraints
- 1\leq N\leq 100
- 0\leq L\lt R\leq 23
- 0\leq X_i\lt Y_i\leq 23
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N L R X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Output the number of listeners who can watch Takahashi's stream from beginning to end.
Sample Input 1
5 19 22 17 23 20 23 19 22 0 23 12 20
Sample Output 1
3
The listeners who can watch Takahashi's stream from beginning to end are the 1st, 3rd, and 4th listeners.
Sample Input 2
3 12 13 0 1 0 1 0 1
Sample Output 2
0
No listeners can watch Takahashi's stream from beginning to end.
Sample Input 3
10 8 14 5 20 14 21 9 21 5 23 8 10 0 14 3 8 2 6 0 16 5 20
Sample Output 3
5
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋君は長さ N の整数列 A=(A_1,A_2,\ldots,A_N) を持っています。
A は広義単調増加であることが保証されます。
高橋君はこの整数列に対して M 回操作を行います。 i 回目 (1\leq i\leq M) の操作では、次の操作を行います。
数列 A が B_i を要素として持つならば、そのような要素を 1 つ選び、削除する。 そのような要素が存在しないならば何もしない。
A は広義単調増加であるため、操作後の列は要素の選び方によらず一意であり、再び広義単調増加となることに注意せよ。
M 回の操作を行なった後の A を求めてください。
広義単調増加 とは
数列 X=(X_1,X_2,\ldots,X_K) が広義単調増加であるとは、 任意の i (1\leq i\leq K-1) について、 X_i\leq X_{i+1} をみたすことを指します。制約
- 1 \leq N \leq 100
- 1 \leq M \leq 100
- 1 \leq A_i,B_i \leq 10^9
- 整数列 A は広義単調増加である。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
出力
操作後の A の各要素を、順に空白区切りで一行に出力せよ。
操作後の A が空ならば、何も出力しないようにせよ。
入力例 1
8 5 1 2 2 3 3 3 5 6 2 2 7 3 2
出力例 1
1 3 3 5 6
最初、A は A=(1,2,2,3,3,3,5,6) です。
操作は次のように行われます。
- A から 2 を 1 つ削除し、操作後の A は A=(1,2,3,3,3,5,6) となります。
- A から 2 を 1 つ削除し、操作後の A は A=(1,3,3,3,5,6) となります。
- A は 7 を要素として持たないため、何も行いません。操作後の A は A=(1,3,3,3,5,6) のままです。
- A から 3 を 1 つ削除し、操作後の A は A=(1,3,3,5,6) となります。
- A は 2 を要素として持たないため、何も行いません。操作後の A は A=(1,3,3,5,6) のままです。
よって、すべての操作の後、A=(1,3,3,5,6) であるため、要素をこの順に空白区切りで出力します。
入力例 2
1 2 1 1 1
出力例 2
操作後の A は空となるため、何も出力しません。
Score : 200 points
Problem Statement
Takahashi has an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.
It is guaranteed that A is non-decreasing.
Takahashi performs M operations on this integer sequence. In the i-th operation (1\leq i\leq M), he performs the following operation:
If the sequence A contains B_i as an element, select one such element and delete it. If no such element exists, do nothing.
Note that since A is non-decreasing, the sequence after the operation is uniquely determined regardless of the choice of element, and remains non-decreasing.
Find A after performing M operations.
What is non-decreasing?
A sequence X=(X_1,X_2,\ldots,X_K) is non-decreasing if X_i\leq X_{i+1} holds for all i (1\leq i\leq K-1).Constraints
- 1 \leq N \leq 100
- 1 \leq M \leq 100
- 1 \leq A_i,B_i \leq 10^9
- The integer sequence A is non-decreasing.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
Output
Output the elements of A after the operations, in order, separated by spaces on a single line.
If A is empty after the operations, output nothing.
Sample Input 1
8 5 1 2 2 3 3 3 5 6 2 2 7 3 2
Sample Output 1
1 3 3 5 6
Initially, A is A=(1,2,2,3,3,3,5,6).
The operations are performed as follows:
- Delete one 2 from A, and A becomes A=(1,2,3,3,3,5,6) after the operation.
- Delete one 2 from A, and A becomes A=(1,3,3,3,5,6) after the operation.
- Since A does not contain 7 as an element, do nothing. A remains A=(1,3,3,3,5,6) after the operation.
- Delete one 3 from A, and A becomes A=(1,3,3,5,6) after the operation.
- Since A does not contain 2 as an element, do nothing. A remains A=(1,3,3,5,6) after the operation.
Therefore, after all operations, A=(1,3,3,5,6), so output the elements in this order separated by spaces.
Sample Input 2
1 2 1 1 1
Sample Output 2
A becomes empty after the operations, so output nothing.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
AtCoder社のオフィスは H 行 W 列のマス目で表されます。上から i 行目、左から j 列目のマスを (i, j) と表します。
各マスの状態は文字 S_{i,j} で表され、 S_{i,j} が # のときそのマスは机、. のときそのマスは床です。床のマスは 2 つ以上存在することが保証されます。
あなたは床のマスから異なる 2 マスを選び、加湿器を設置します。
加湿器が設置されたとき、あるマス (i,j) は加湿器があるマス (i',j') からのマンハッタン距離が D 以下であるとき、またその時に限り加湿されます。 なお、マス (i,j) からマス (i',j') までのマンハッタン距離は |i-i'|+|j-j'| で表されます。 ここで、加湿器が置かれた床のマスは必ず加湿されていることに注意してください。
加湿される 床のマス の個数として考えられる最大値を求めてください。
制約
- 1 \leq H \leq 10
- 1 \leq W \leq 10
- 2 \leq H \times W
- 0 \leq D \leq H+W-2
- H,W,D は整数
- S_{i,j} は
#または.である (1 \leq i \leq H, 1 \leq j \leq W) - 床のマスは 2 つ以上存在する
入力
入力は以下の形式で標準入力から与えられる。
H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}
出力
答えを出力せよ。
入力例 1
2 5 1 .###. .#.##
出力例 1
3
マス (1,1) とマス (1,5) に加湿器を置いた時:
- マス (1,1) の加湿器によってマス (1,1),(2,1) の 2 マスが加湿されます。
- マス (1,5) の加湿器によってマス (1,5) の 1 マスが加湿されます。
よって、合計 3 マス加湿されています。また、4 マス以上加湿するような加湿器の置き方は存在しないため、答えは 3 です。
入力例 2
5 5 2 .#.#. ..... .#.#. #.#.# .....
出力例 2
15
マス (2,4) とマス (5,3) に加湿器を置いた時、15 個の床のマスが加湿されます。
入力例 3
4 4 2 .... .##. .##. ....
出力例 3
10
Score : 250 points
Problem Statement
The AtCoder company office can be represented as a grid of H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
The state of each cell is represented by a character S_{i,j}. If S_{i,j} is #, that cell contains a desk; if S_{i,j} is ., that cell is a floor. It is guaranteed that there are at least two floor cells.
You will choose two distinct floor cells and place a humidifier on each.
After placing the humidifiers, a cell (i,j) is humidified if and only if it is within a Manhattan distance D from at least one of the humidifier cells (i',j'). The Manhattan distance between (i,j) and (i',j') is defined as |i - i'| + |j - j'|. Note that any floor cell on which a humidifier is placed is always humidified.
Find the maximum possible number of humidified floor cells.
Constraints
- 1 \leq H \leq 10
- 1 \leq W \leq 10
- 2 \leq H \times W
- 0 \leq D \leq H+W-2
- H,W,D are integers.
- S_{i,j} is
#or.. (1 \leq i \leq H, 1 \leq j \leq W) - There are at least two floor cells.
Input
The input is given from Standard Input in the following format:
H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}
Output
Print the answer.
Sample Input 1
2 5 1 .###. .#.##
Sample Output 1
3
When placing humidifiers on (1,1) and (1,5):
- From the humidifier on (1,1), two cells (1,1) and (2,1) are humidified.
- From the humidifier on (1,5), one cell (1,5) is humidified.
In total, three cells are humidified. No configuration can humidify four or more floor cells, so the answer is 3.
Sample Input 2
5 5 2 .#.#. ..... .#.#. #.#.# .....
Sample Output 2
15
When placing humidifiers on (2,4) and (5,3), 15 floor cells are humidified.
Sample Input 3
4 4 2 .... .##. .##. ....
Sample Output 3
10
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の文字列 S が与えられます。S_i\ (1\leq i \leq N) を S の左から i 番目の文字とします。
あなたは以下の 2 種類の操作を好きな順番で 0 回以上好きな回数行うことができます。
-
A 円払う。 S の左端の文字を右端に移動する。すなわち、S_1S_2\ldots S_N を S_2\ldots S_NS_1 に変える。
-
B 円払う。 1 以上 N 以下の整数 i を選び、 S_i を好きな英小文字で置き換える。
S を回文にするためには最低で何円必要ですか?
回文とは
ある文字列 T について、 T の長さを |T| として、全ての整数 i (1 \le i \le |T|) について、 T の前から i 文字目と後ろから i 文字目が同じであるとき、またそのときに限って、 T は回文です。制約
- 1\leq N \leq 5000
- 1\leq A,B\leq 10^9
- S は英小文字からなる長さ N の文字列
- S 以外の入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A B S
出力
答えを整数として出力せよ。
入力例 1
5 1 2 rrefa
出力例 1
3
最初に 2 番目の操作を 1 回行います。2 円払い、i=5 として S_5 を e で置き換えます。 S は rrefe となります。
次に 1 番目の操作を 1 回行います。1 円払い、S は refer となります。これは回文です。
よって 3 円払うことで S を回文にすることができました。 2 円以下払うことで S を回文にすることは不可能なので、これが答えです。
入力例 2
8 1000000000 1000000000 bcdfcgaa
出力例 2
4000000000
答えは 32 bit 整数に収まらない場合があることに注意してください。
Score : 300 points
Problem Statement
You are given a string S of length N. Let S_i\ (1\leq i \leq N) be the i-th character of S from the left.
You may perform the following two kinds of operations zero or more times in any order:
-
Pay A yen (the currency in Japan). Move the leftmost character of S to the right end. In other words, change S_1S_2\ldots S_N to S_2\ldots S_NS_1.
-
Pay B yen. Choose an integer i between 1 and N, and replace S_i with any lowercase English letter.
How many yen do you need to pay to make S a palindrome?
What is a palindrome?
A string T is a palindrome if and only if the i-th character from the left and the i-th character from the right are the same for all integers i (1 \le i \le |T|), where |T| is the length of T.Constraints
- 1\leq N \leq 5000
- 1\leq A,B\leq 10^9
- S is a string of length N consisting of lowercase English letters.
- All values in the input except for S are integers.
Input
The input is given from Standard Input in the following format:
N A B S
Output
Print the answer as an integer.
Sample Input 1
5 1 2 rrefa
Sample Output 1
3
First, pay 2 yen to perform the operation of the second kind once: let i=5 to replace S_5 with e. S is now rrefe.
Then, pay 1 yen to perform the operation of the first kind once. S is now refer, which is a palindrome.
Thus, you can make S a palindrome for 3 yen. Since you cannot make S a palindrome for 2 yen or less, 3 is the answer.
Sample Input 2
8 1000000000 1000000000 bcdfcgaa
Sample Output 2
4000000000
Note that the answer may not fit into a 32-bit integer type.