Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
H 行 W 列のマス目があり、そのうち二つの異なるマスに駒が置かれています。
マス目の状態は H 個の長さ W の文字列 S_1, \dots, S_H で表されます。S_{i, j} = o ならば i 行目 j 列目のマスに駒が置かれていることを、S_{i, j} = - ならばそのマスには駒が置かれていないことを表します。なお、S_{i, j} は文字列 S_i の j 文字目を指します。
一方の駒をマス目の外側に出ないように上下左右の隣接するマスに動かすことを繰り返すとき、もう一方の駒と同じマスに移動させるためには最小で何回動かす必要がありますか？
制約
- 2 \leq H, W \leq 100
- H, W は整数
- S_i \, (1 \leq i \leq H) は
oおよび-のみからなる長さ W の文字列 - S_{i, j} =
oとなる整数 1 \leq i \leq H, 1 \leq j \leq W の組がちょうど二つ存在する
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 \vdots S_H
出力
答えを出力せよ。
入力例 1
2 3 --o o--
出力例 1
3
1 行目 3 列目に置かれている駒を 下 \rightarrow 左 \rightarrow 左 と移動すると 3 回でもう一方の駒と同じマスに移動させることができます。2 回以下で移動させることはできないので、3 を出力します。
入力例 2
5 4 -o-- ---- ---- ---- -o--
出力例 2
4
Score : 200 points
Problem Statement
There is a grid with H horizontal rows and W vertical columns, in which two distinct squares have a piece.
The state of the squares is represented by H strings S_1, \dots, S_H of length W. S_{i, j} = o means that there is a piece in the square at the i-th row from the top and j-th column from the left; S_{i, j} = - means that the square does not have a piece. Here, S_{i, j} denotes the j-th character of the string S_i.
Consider repeatedly moving one of the pieces to one of the four adjacent squares. It is not allowed to move the piece outside the grid. How many moves are required at minimum for the piece to reach the square with the other piece?
Constraints
- 2 \leq H, W \leq 100
- H and W are integers.
- S_i \, (1 \leq i \leq H) is a string of length W consisting of
oand-. - There exist exactly two pairs of integers 1 \leq i \leq H, 1 \leq j \leq W such that S_{i, j} =
o.
Input
Input is given from Standard Input in the following format:
H W S_1 \vdots S_H
Output
Print the answer.
Sample Input 1
2 3 --o o--
Sample Output 1
3
The piece at the 1-st row from the top and 3-rd column from the left can reach the square with the other piece in 3 moves: down, left, left. Since it is impossible to do so in two or less moves, 3 should be printed.
Sample Input 2
5 4 -o-- ---- ---- ---- -o--
Sample Output 2
4
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
N 個の整数 A_1,A_2,\dots,A_N が、 1 行に 1 つずつ、 N 行にわたって与えられます。但し、 N は入力では与えられません。
さらに、以下が保証されます。
- A_i \neq 0 ( 1 \le i \le N-1 )
- A_N = 0
A_N, A_{N-1},\dots,A_1 をこの順に出力してください。
制約
- 入力は全て整数
- 1 \le N \le 100
- 1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
- A_N = 0
入力
入力は以下の形式で標準入力から与えられる。
A_1 A_2 \vdots A_N
出力
A_N, A_{N-1},\dots,A_1 をこの順に、改行区切りで整数として出力せよ。
入力例 1
3 2 1 0
出力例 1
0 1 2 3
繰り返しになりますが、 N は入力では与えられないことに注意してください。
この入力においては N=4 で、 A=(3,2,1,0) です。
入力例 2
0
出力例 2
0
A=(0) です。
入力例 3
123 456 789 987 654 321 0
出力例 3
0 321 654 987 789 456 123
Score: 150 points
Problem Statement
You are given N integers A_1,A_2,\dots,A_N, one per line, over N lines. However, N is not given in the input.
Furthermore, the following is guaranteed:
- A_i \neq 0 ( 1 \le i \le N-1 )
- A_N = 0
Print A_N, A_{N-1},\dots,A_1 in this order.
Constraints
- All input values are integers.
- 1 \le N \le 100
- 1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
- A_N = 0
Input
The input is given from Standard Input in the following format:
A_1 A_2 \vdots A_N
Output
Print A_N, A_{N-1}, \dots, A_1 in this order, as integers, separated by newlines.
Sample Input 1
3 2 1 0
Sample Output 1
0 1 2 3
Note again that N is not given in the input. Here, N=4 and A=(3,2,1,0).
Sample Input 2
0
Sample Output 2
0
A=(0).
Sample Input 3
123 456 789 987 654 321 0
Sample Output 3
0 321 654 987 789 456 123
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
りんご市場に N 人の売り手と M 人の買い手がいます。
i 番目の売り手は、A_i 円以上でならりんごを売ってもよいと考えています。
i 番目の買い手は、B_i 円以下でならりんごを買ってもよいと考えています。
次の条件を満たすような最小の整数 X を求めてください。
条件：りんごを X 円で売ってもよいと考える売り手の人数が、りんごを X 円で買ってもよいと考える買い手の人数以上である。
制約
- 1 \leq N,M \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 \ldots A_N B_1 \ldots B_M
出力
答えを出力せよ。
入力例 1
3 4 110 90 120 100 80 120 10000
出力例 1
110
りんごを 110 円で売ってもよいと考える売り手は 1,2 番目の 2 人であり、りんごを 110 円で買ってもよいと考える買い手は 3,4 番目の 2 人であるため、110 は条件を満たします。
110 未満の整数が条件を満たすことはないため、これが答えです。
入力例 2
5 2 100000 100000 100000 100000 100000 100 200
出力例 2
201
入力例 3
3 2 100 100 100 80 120
出力例 3
100
Score : 300 points
Problem Statement
There are N sellers and M buyers in an apple market.
The i-th seller may sell an apple for A_i yen or more (yen is the currency in Japan).
The i-th buyer may buy an apple for B_i yen or less.
Find the minimum integer X that satisfies the following condition.
Condition: The number of people who may sell an apple for X yen is greater than or equal to the number of people who may buy an apple for X yen.
Constraints
- 1 \leq N,M \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 \ldots A_N B_1 \ldots B_M
Output
Print the answer.
Sample Input 1
3 4 110 90 120 100 80 120 10000
Sample Output 1
110
Two sellers, the 1-st and 2-nd, may sell an apple for 110 yen; two buyers, the 3-rd and 4-th, may buy an apple for 110 yen. Thus, 110 satisfies the condition.
Since an integer less than 110 does not satisfy the condition, this is the answer.
Sample Input 2
5 2 100000 100000 100000 100000 100000 100 200
Sample Output 2
201
Sample Input 3
3 2 100 100 100 80 120
Sample Output 3
100
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 枚の靴下があります。i 枚目の靴下の色は A_i です。
あなたは以下の操作をできるだけ多い回数行いたいです。最大で何回行うことができますか？
- まだペアになっていない靴下の中から同じ色の靴下を 2 枚選んでペアにする。
制約
- 1\leq N \leq 5\times 10^5
- 1\leq A_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
6 4 1 7 4 1 4
出力例 1
2
以下のようにして、2 回の操作を行うことができます。
- 色が 1 である靴下を 2 枚選んでペアにする。
- 色が 4 である靴下を 2 枚選んでペアにする。
このとき、色が 4 である靴下と 7 である靴下が 1 枚ずつ残るため、これ以上操作はできません。 また、どのように操作をしても 3 回以上操作を行うことはできないため、2 を出力します。
入力例 2
1 158260522
出力例 2
0
入力例 3
10 295 2 29 295 29 2 29 295 2 29
出力例 3
4
Score : 300 points
Problem Statement
You have N socks. The color of the i-th sock is A_i.
You want to perform the following operation as many times as possible. How many times can it be performed at most?
- Choose two same-colored socks that are not paired yet, and pair them.
Constraints
- 1\leq N \leq 5\times 10^5
- 1\leq A_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print an integer representing the answer.
Sample Input 1
6 4 1 7 4 1 4
Sample Output 1
2
You can do the operation twice as follows.
- Choose two socks with the color 1 and pair them.
- Choose two socks with the color 4 and pair them.
Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.
Sample Input 2
1 158260522
Sample Output 2
0
Sample Input 3
10 295 2 29 295 29 2 29 295 2 29
Sample Output 3
4
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
整数 N が与えられます。以下の条件を満たす N 以下の正整数の組 (i,j) の個数を求めてください。
- i \times j は平方数である。
制約
- 1 \le N \le 2 \times 10^5
- N は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
4
出力例 1
6
(1,1),(1,4),(2,2),(3,3),(4,1),(4,4) の 6 個が条件を満たします。
(2,3) は 2 \times 3 =6 が平方数でないため条件を満たしません。
入力例 2
254
出力例 2
896
Score : 400 points
Problem Statement
You are given an integer N. Find the number of pairs (i,j) of positive integers at most N that satisfy the following condition:
- i \times j is a square number.
Constraints
- 1 \le N \le 2 \times 10^5
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
4
Sample Output 1
6
The six pairs (1,1),(1,4),(2,2),(3,3),(4,1),(4,4) satisfy the condition.
On the other hand, (2,3) does not, since 2 \times 3 =6 is not a square number.
Sample Input 2
254
Sample Output 2
896