Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
猫と犬が合わせて A + B 匹います. このうち A 匹は猫であることがわかっていますが,残りの B 匹は猫と犬のどちらであるかわかっていません.
この A + B 匹の中に,猫がちょうど X 匹いるということはありうるかどうか判定してください.
制約
- 1 \leq A \leq 100
- 1 \leq B \leq 100
- 1 \leq X \leq 200
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
A B X
出力
猫がちょうど X 匹いるということがありうるならば YES
を,ありえないならば NO
を出力せよ.
入力例 1
3 5 4
出力例 1
YES
B = 5 匹のうち,猫が 1 匹,犬が 4 匹であれば,猫の数は合計で X = 4 匹になります.
入力例 2
2 2 6
出力例 2
NO
B = 2 匹すべてが猫であっても,猫の数の合計は X = 6 匹に足りません.
入力例 3
5 3 2
出力例 3
NO
B = 3 匹すべてが犬であっても,猫の数の合計は X = 2 匹より多くなってしまいます.
Score : 100 points
Problem Statement
There are a total of A + B cats and dogs. Among them, A are known to be cats, but the remaining B are not known to be either cats or dogs.
Determine if it is possible that there are exactly X cats among these A + B animals.
Constraints
- 1 \leq A \leq 100
- 1 \leq B \leq 100
- 1 \leq X \leq 200
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B X
Output
If it is possible that there are exactly X cats, print YES
; if it is impossible, print NO
.
Sample Input 1
3 5 4
Sample Output 1
YES
If there are one cat and four dogs among the B = 5 animals, there are X = 4 cats in total.
Sample Input 2
2 2 6
Sample Output 2
NO
Even if all of the B = 2 animals are cats, there are less than X = 6 cats in total.
Sample Input 3
5 3 2
Sample Output 3
NO
Even if all of the B = 3 animals are dogs, there are more than X = 2 cats in total.
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
N + 1 個のマスが左右に一列に並んでいます. これらのマスには,左のマスから順に 0, 1, ..., N の番号が付けられています.
あなたは,最初マス X にいます. 隣り合うマスの間は自由に移動することができ,マス 0 またはマス N にたどり着くとゴールすることができます. ただし,i = 1, 2, ..., M について,マス A_i には料金所があり,そのためマス A_i に移動してくる際には 1 のコストがかかります. なお,マス 0,マス X,マス N には料金所がないことが保証されます.
ゴールするまでにかかるコストの最小値を求めてください.
制約
- 1 \leq N \leq 100
- 1 \leq M \leq 100
- 1 \leq X \leq N - 1
- 1 \leq A_1 < A_2 < ... < A_M \leq N - 1
- A_i \neq X
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M X A_1 A_2 ... A_M
出力
ゴールするまでにかかるコストの最小値を出力せよ.
入力例 1
5 3 3 1 2 4
出力例 1
1
次のようにするのが最適です.
- まず,マス 3 から,マス 4 へ移動する.このとき,マス 4 には料金所があるので,コスト 1 がかかる.
- 次に,マス 4 から,マス 5 へ移動する.このときはコストはかからない.
- マス 5 に到着したので,ゴールする.
このようにすると,コストは合計で 1 になります.
入力例 2
7 3 2 4 5 6
出力例 2
0
まったくコストがかからないこともあります.
入力例 3
10 7 5 1 2 3 4 6 8 9
出力例 3
3
Score : 200 points
Problem Statement
There are N + 1 squares arranged in a row, numbered 0, 1, ..., N from left to right.
Initially, you are in Square X. You can freely travel between adjacent squares. Your goal is to reach Square 0 or Square N. However, for each i = 1, 2, ..., M, there is a toll gate in Square A_i, and traveling to Square A_i incurs a cost of 1. It is guaranteed that there is no toll gate in Square 0, Square X and Square N.
Find the minimum cost incurred before reaching the goal.
Constraints
- 1 \leq N \leq 100
- 1 \leq M \leq 100
- 1 \leq X \leq N - 1
- 1 \leq A_1 < A_2 < ... < A_M \leq N
- A_i \neq X
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M X A_1 A_2 ... A_M
Output
Print the minimum cost incurred before reaching the goal.
Sample Input 1
5 3 3 1 2 4
Sample Output 1
1
The optimal solution is as follows:
- First, travel from Square 3 to Square 4. Here, there is a toll gate in Square 4, so the cost of 1 is incurred.
- Then, travel from Square 4 to Square 5. This time, no cost is incurred.
- Now, we are in Square 5 and we have reached the goal.
In this case, the total cost incurred is 1.
Sample Input 2
7 3 2 4 5 6
Sample Output 2
0
We may be able to reach the goal at no cost.
Sample Input 3
10 7 5 1 2 3 4 6 8 9
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
l が奇数のとき,l 個の数 a_1, a_2, ..., a_l の中央値とは,a_1, a_2, ..., a_l の中で \frac{l+1}{2} 番目に大きい値のことを言います.
N 個の数 X_1, X_2, ..., X_N が与えられます.ここで,N は偶数です. i = 1, 2, ..., N に対して,X_1, X_2, ..., X_N から X_i のみを除いたもの,すなわち X_1, X_2, ..., X_{i-1}, X_{i+1}, ..., X_N の中央値を B_i とします.
i = 1, 2, ..., N に対して,B_i を求めてください.
制約
- 2 \leq N \leq 200000
- N は偶数
- 1 \leq X_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X_1 X_2 ... X_N
出力
N 行出力せよ. i 行目には B_i を出力せよ.
入力例 1
4 2 4 4 3
出力例 1
4 3 3 4
- X_2, X_3, X_4 の中央値は 4 なので,B_1 = 4 です.
- X_1, X_3, X_4 の中央値は 3 なので,B_2 = 3 です.
- X_1, X_2, X_4 の中央値は 3 なので,B_3 = 3 です.
- X_1, X_2, X_3 の中央値は 4 なので,B_4 = 4 です.
入力例 2
2 1 2
出力例 2
2 1
入力例 3
6 5 5 4 4 3 3
出力例 3
4 4 4 4 4 4
Score : 300 points
Problem Statement
When l is an odd number, the median of l numbers a_1, a_2, ..., a_l is the (\frac{l+1}{2})-th largest value among a_1, a_2, ..., a_l.
You are given N numbers X_1, X_2, ..., X_N, where N is an even number. For each i = 1, 2, ..., N, let the median of X_1, X_2, ..., X_N excluding X_i, that is, the median of X_1, X_2, ..., X_{i-1}, X_{i+1}, ..., X_N be B_i.
Find B_i for each i = 1, 2, ..., N.
Constraints
- 2 \leq N \leq 200000
- N is even.
- 1 \leq X_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X_1 X_2 ... X_N
Output
Print N lines. The i-th line should contain B_i.
Sample Input 1
4 2 4 4 3
Sample Output 1
4 3 3 4
- Since the median of X_2, X_3, X_4 is 4, B_1 = 4.
- Since the median of X_1, X_3, X_4 is 3, B_2 = 3.
- Since the median of X_1, X_2, X_4 is 3, B_3 = 3.
- Since the median of X_1, X_2, X_3 is 4, B_4 = 4.
Sample Input 2
2 1 2
Sample Output 2
2 1
Sample Input 3
6 5 5 4 4 3 3
Sample Output 3
4 4 4 4 4 4
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
n 個のものから順番を無視して r 個を選ぶ場合の数を {\rm comb}(n,r) と書くことにします。 n 個の非負の整数 a_1, a_2, ..., a_n から 2 つの数 a_i > a_j を {\rm comb}(a_i,a_j) が最大になるように選んで下さい。 最大になる組が複数ある場合、どれを選んでも構いません。
制約
- 2 \leq n \leq 10^5
- 0 \leq a_i \leq 10^9
- a_1,a_2,...,a_n は互いに相異なる
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
n a_1 a_2 ... a_n
出力
選んだ 2 つの数を空白区切りで降順に出力せよ。
入力例 1
5 6 9 4 2 11
出力例 1
11 6
それぞれ計算すると
- \rm{comb}(4,2)=6
- \rm{comb}(6,2)=15
- \rm{comb}(6,4)=15
- \rm{comb}(9,2)=36
- \rm{comb}(9,4)=126
- \rm{comb}(9,6)=84
- \rm{comb}(11,2)=55
- \rm{comb}(11,4)=330
- \rm{comb}(11,6)=462
- \rm{comb}(11,9)=55
となるため、11 と 6 を出力します。
入力例 2
2 100 0
出力例 2
100 0
Score : 400 points
Problem Statement
Let {\rm comb}(n,r) be the number of ways to choose r objects from among n objects, disregarding order. From n non-negative integers a_1, a_2, ..., a_n, select two numbers a_i > a_j so that {\rm comb}(a_i,a_j) is maximized. If there are multiple pairs that maximize the value, any of them is accepted.
Constraints
- 2 \leq n \leq 10^5
- 0 \leq a_i \leq 10^9
- a_1,a_2,...,a_n are pairwise distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
n a_1 a_2 ... a_n
Output
Print a_i and a_j that you selected, with a space in between.
Sample Input 1
5 6 9 4 2 11
Sample Output 1
11 6
\rm{comb}(a_i,a_j) for each possible selection is as follows:
- \rm{comb}(4,2)=6
- \rm{comb}(6,2)=15
- \rm{comb}(6,4)=15
- \rm{comb}(9,2)=36
- \rm{comb}(9,4)=126
- \rm{comb}(9,6)=84
- \rm{comb}(11,2)=55
- \rm{comb}(11,4)=330
- \rm{comb}(11,6)=462
- \rm{comb}(11,9)=55
Thus, we should print 11 and 6.
Sample Input 2
2 100 0
Sample Output 2
100 0