Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
正整数 A,B が与えられます。
A+B の二乗を出力してください。
制約
- 1\leq A,B \leq 2025
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
入力例 1
20 25
出力例 1
2025
(20+25)^2=2025 です。
入力例 2
30 25
出力例 2
3025
入力例 3
45 11
出力例 3
3136
入力例 4
2025 1111
出力例 4
9834496
Score : 100 points
Problem Statement
You are given two positive integers A and B.
Output the square of A + B.
Constraints
- 1 \leq A,B \leq 2025
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print the answer.
Sample Input 1
20 25
Sample Output 1
2025
(20+25)^2=2025.
Sample Input 2
30 25
Sample Output 2
3025
Sample Input 3
45 11
Sample Output 3
3136
Sample Input 4
2025 1111
Sample Output 4
9834496
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
高橋君は、時刻 0 にパソコンの電源をつけ、それからマウスを N 回クリックしました。i(1 \le i \le N) 回目のクリックは時刻 T_i に行われました。
高橋君が時刻 x_1 と時刻 x_2 (ただし x_1 < x_2)にマウスを連続してクリックしたとき、x_2 - x_1 \le D であれば時刻 x_2 にダブルクリックが成立したと言います。
高橋君が最初にダブルクリックを成立させた時刻を求めてください。ただし、高橋君が 1 回もダブルクリックを成立させていないならば -1 を出力してください。
制約
- 1 \le N \le 100
- 1 \le D \le 10^9
- 1 \le T_i \le 10^9(1 \le i \le N)
- T_i < T_{i+1}(1 \le i \le N-1)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D T_1 T_2 \dots T_N
出力
高橋君が 1 回でもダブルクリックを成立させたならば最初にダブルクリックが成立した時刻を、そうでないならば -1 を出力せよ。
入力例 1
4 500 300 900 1300 1700
出力例 1
1300
高橋君は時刻 900,1300 にマウスをクリックしていて、1300 - 900 \le 500 であるため時刻 1300 にダブルクリックが成立しています。
時刻 1300 より前にダブルクリックは成立していないため、1300 を出力してください。
入力例 2
5 99 100 200 300 400 500
出力例 2
-1
高橋君は 1 回もダブルクリックを成立させていません。よって、-1 を出力してください。
入力例 3
4 500 100 600 1100 1600
出力例 3
600
高橋君が複数回ダブルクリックを成立させていても、そのうち最初の時刻のみを出力することに注意してください。
Score : 100 points
Problem Statement
Takahashi turned on a computer at time 0 and clicked the mouse N times. The i-th (1 \le i \le N) click was at time T_i.
If he consecutively clicked the mouse at time x_1 and time x_2 (where x_1 < x_2), a double click is said to be fired at time x_2 if and only if x_2 - x_1 \le D.
What time was a double click fired for the first time? If no double click was fired, print -1 instead.
Constraints
- 1 \le N \le 100
- 1 \le D \le 10^9
- 1 \le T_i \le 10^9(1 \le i \le N)
- T_i < T_{i+1}(1 \le i \le N-1)
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N D T_1 T_2 \dots T_N
Output
If at least one double click was fired, print the time of the first such event; otherwise, print -1.
Sample Input 1
4 500 300 900 1300 1700
Sample Output 1
1300
Takahashi clicked the mouse at time 900 and 1300. Since 1300 - 900 \le 500, a double click was fired at time 1300.
A double click had not been fired before time 1300, so 1300 should be printed.
Sample Input 2
5 99 100 200 300 400 500
Sample Output 2
-1
No double click was fired, so print -1.
Sample Input 3
4 500 100 600 1100 1600
Sample Output 3
600
If multiple double clicks were fired, be sure to print only the first such event.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
文字列 S, T が与えられます。以下の操作を高々 1 回行うことで、S を T と一致させることができるかを判定してください。
- S の隣り合う 2 文字を選び、入れ替える。
なお、上記の操作を一度も行わないことも可能です。
制約
- S, T はそれぞれ英小文字のみからなる、長さ 2 以上 100 以下の文字列
- S の長さと T の長さは等しい
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
問題文中の操作を高々 1 回行うことで S を T と一致させることができるなら Yes を、できないなら No を出力せよ。
入力例 1
abc acb
出力例 1
Yes
S の 2 文字目と 3 文字目を入れ替えることで、S を T と一致させることができます。
入力例 2
aabb bbaa
出力例 2
No
どのように操作を行っても、S を T と一致させることはできません。
入力例 3
abcde abcde
出力例 3
Yes
S と T は既に一致しています。
Score : 200 points
Problem Statement
You are given two strings S and T. Determine whether it is possible to make S and T equal by doing the following operation at most once:
- choose two adjacent characters in S and swap them.
Note that it is allowed to choose not to do the operation.
Constraints
- Each of S and T is a string of length between 2 and 100 (inclusive) consisting of lowercase English letters.
- S and T have the same length.
Input
Input is given from Standard Input in the following format:
S T
Output
If it is possible to make S and T equal by doing the operation in Problem Statement at most once, print Yes; otherwise, print No.
Sample Input 1
abc acb
Sample Output 1
Yes
You can swap the 2-nd and 3-rd characters of S to make S and T equal.
Sample Input 2
aabb bbaa
Sample Output 2
No
There is no way to do the operation to make S and T equal.
Sample Input 3
abcde abcde
Sample Output 3
Yes
S and T are already equal.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
英小文字のみからなる N 個の文字列 S_1,S_2,\ldots,S_N が与えられます。
1 以上 N 以下の 相異なる 整数 i,j であって、S_i と S_j をこの順に連結した文字列が回文となるようなものが存在するか判定してください。
ただし、長さ M の文字列 T が回文であるとは、任意の 1\leq i\leq M について、T の i 文字目と (M+1-i) 文字目が一致していることをいいます。
制約
- 2\leq N\leq 100
- 1\leq \lvert S_i\rvert \leq 50
- N は整数
- S_i は英小文字のみからなる文字列
- S_i はすべて異なる。
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
問題文の条件をみたす i,j が存在するならば Yes を、そうでないならば No を出力せよ。
入力例 1
5 ab ccef da a fe
出力例 1
Yes
(i,j)=(1,4) とすると、S_1=ab と S_4=a をこの順に連結した文字列は aba となり、
これは回文であるため条件をみたしています。
よって、Yes を出力します。
また、(i,j)=(5,2) としても、S_5=fe と S_2=ccef をこの順に連結した文字列は feccef となり、やはり条件をみたしています。
入力例 2
3 a b aba
出力例 2
No
S_1, S_2, S_3 のうち、どの相異なる 2 つの文字列を繋げても回文となりません。
よって、No を出力します。
問題文における i,j は相異なる必要があることに注意してください。
入力例 3
2 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
出力例 3
Yes
Score : 200 points
Problem Statement
You are given N strings S_1,S_2,\ldots,S_N consisting of lowercase English letters.
Determine if there are distinct integers i and j between 1 and N, inclusive, such that the concatenation of S_i and S_j in this order is a palindrome.
A string T of length M is a palindrome if and only if the i-th character and the (M+1-i)-th character of T are the same for every 1\leq i\leq M.
Constraints
- 2\leq N\leq 100
- 1\leq \lvert S_i\rvert \leq 50
- N is an integer.
- S_i is a string consisting of lowercase English letters.
- All S_i are distinct.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
If there are i and j that satisfy the condition in the problem statement, print Yes; otherwise, print No.
Sample Input 1
5 ab ccef da a fe
Sample Output 1
Yes
If we take (i,j)=(1,4), the concatenation of S_1=ab and S_4=a in this order is aba, which is a palindrome, satisfying the condition.
Thus, print Yes.
Here, we can also take (i,j)=(5,2), for which the concatenation of S_5=fe and S_2=ccef in this order is feccef, satisfying the condition.
Sample Input 2
3 a b aba
Sample Output 2
No
No two distinct strings among S_1, S_2, and S_3 form a palindrome when concatenated.
Thus, print No.
Note that the i and j in the statement must be distinct.
Sample Input 3
2 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
現在 AtCoder 高校には K 個のクラスと N 人の生徒が存在し、i 人目 (1\le i\le N) の生徒は A _ i 番目のクラスに所属しています。
高橋くんは 9 月から AtCoder 高校に転入することになりました。 高橋くんは、転入する際に K 個のクラスの中から好きなクラスを 1 つ選び、そのクラスに所属することができます。
高橋くんは、自分が所属しているクラスより多い人数が所属しているクラスがあるとき悲しみ、そうでないとき喜びます。
所属したときに高橋くんが喜ぶクラスがいくつあるか求めてください。
制約
- 1\le N\le2\times10 ^ 5
- 1\le K\le N
- 1\le A _ i\le K\ (1\le i\le N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A _ 1 A _ 2 \ldots A _ N
出力
条件を満たすクラスの個数を出力せよ。
入力例 1
8 5 3 3 5 5 4 4 3 2
出力例 1
3
例えば、高橋くんが 5 番目のクラスを選んで所属したとき、5 番目のクラスに所属している人数は 3 人となります。 このとき、3 人より多い人数が所属しているクラスは存在しないため、高橋くんは喜びます。
一方、例えば高橋くんが 1 番目のクラスを選んで所属したとき、1 番目のクラスに所属している人数は 1 人となります。 このとき、3 番目のクラスに所属している人数は 3 人なので、高橋くんは悲しみます。
3,4,5 番目のクラスを選んだとき、かつそのときに限り高橋くんは喜ぶので、3 を出力してください。
入力例 2
6 1 1 1 1 1 1 1
出力例 2
1
AtCoder 高校にクラスが 1 つしかない場合もあります。
入力例 3
14 8 6 1 5 3 8 4 3 4 3 5 1 2 5 1
出力例 3
4
Score : 300 points
Problem Statement
Currently, AtCoder High School has K classes and N students, and the i-th (1\le i\le N) student belongs to the A _ i-th class.
Takahashi is transferring to AtCoder High School in September. At that time, he can choose any one class among the K classes and belong to that class.
He will be sad if there is a class with more students belonging to it than the class he belongs to. Otherwise, he will be happy.
Find how many classes make him happy if he belongs to them.
Constraints
- 1\le N\le2\times10 ^ 5
- 1\le K\le N
- 1\le A _ i\le K\ (1\le i\le N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A _ 1 A _ 2 \ldots A _ N
Output
Output the number of classes satisfying the condition.
Sample Input 1
8 5 3 3 5 5 4 4 3 2
Sample Output 1
3
For example, if Takahashi chooses the fifth class and belongs to it, the number of students belonging to the fifth class becomes 3. Then, he will be happy since there is no class with more than three students belonging to it.
On the other hand, for example, if he chooses the first class and belongs to it, the number of students belonging to the first class becomes 1. Then, he will be sad since three students belong to the third class.
He will be happy if and only if he chooses the third, fourth, or fifth class, so output 3.
Sample Input 2
6 1 1 1 1 1 1 1
Sample Output 2
1
It is possible that AtCoder High School has only one class.
Sample Input 3
14 8 6 1 5 3 8 4 3 4 3 5 1 2 5 1
Sample Output 3
4