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
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 700 点
問題文
H 行 W 列のマス目があり,各マスには英小文字が書かれています. 具体的には,上から i 行,左から j 列目のマスに書かれている文字は,文字列 S_i の j 文字目に等しいです.
すぬけ君は,このマス目に対して次の操作を好きな回数行うことができます:
- 2 つの異なる行を選び,入れ替える.または,2 つの異なる列を選び,入れ替える.
すぬけ君は,このマス目が点対称的になるようにしたいです. すなわち,任意の 1 \leq i \leq H, 1 \leq j \leq W に対して,マス目の上から i 行,左から j 列目に書かれている文字と,マス目の上から H + 1 - i 行,左から W + 1 - j 列目に書かれている文字が等しくなるようにしたいです.
すぬけくんがこの目標を達成することが可能かどうか判定してください.
制約
- 1 \leq H \leq 12
- 1 \leq W \leq 12
- |S_i| = W
- S_i は英小文字のみからなる
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 : S_H
出力
マス目を点対称的にできるなら YES
を,できないなら NO
を出力せよ.
入力例 1
2 3 arc rac
出力例 1
YES
下の画像に示すように,左から 2 列目と 3 列目を入れ替えると,マス目が点対称的になります.
入力例 2
3 7 atcoder regular contest
出力例 2
NO
入力例 3
12 12 bimonigaloaf faurwlkbleht dexwimqxzxbb lxdgyoifcxid ydxiliocfdgx nfoabgilamoi ibxbdqmzxxwe pqirylfrcrnf wtehfkllbura yfrnpflcrirq wvcclwgiubrk lkbrwgwuiccv
出力例 3
YES
Score : 700 points
Problem Statement
There is an H \times W grid (H vertical, W horizontal), where each square contains a lowercase English letter. Specifically, the letter in the square at the i-th row and j-th column is equal to the j-th character in the string S_i.
Snuke can apply the following operation to this grid any number of times:
- Choose two different rows and swap them. Or, choose two different columns and swap them.
Snuke wants this grid to be symmetric. That is, for any 1 \leq i \leq H and 1 \leq j \leq W, the letter in the square at the i-th row and j-th column and the letter in the square at the (H + 1 - i)-th row and (W + 1 - j)-th column should be equal.
Determine if Snuke can achieve this objective.
Constraints
- 1 \leq H \leq 12
- 1 \leq W \leq 12
- |S_i| = W
- S_i consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
H W S_1 S_2 : S_H
Output
If Snuke can make the grid symmetric, print YES
; if he cannot, print NO
.
Sample Input 1
2 3 arc rac
Sample Output 1
YES
If the second and third columns from the left are swapped, the grid becomes symmetric, as shown in the image below:
Sample Input 2
3 7 atcoder regular contest
Sample Output 2
NO
Sample Input 3
12 12 bimonigaloaf faurwlkbleht dexwimqxzxbb lxdgyoifcxid ydxiliocfdgx nfoabgilamoi ibxbdqmzxxwe pqirylfrcrnf wtehfkllbura yfrnpflcrirq wvcclwgiubrk lkbrwgwuiccv
Sample Output 3
YES
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 900 点
問題文
高橋くんには (1,2,...,n) の順列 (p_1,p_2,...,p_n) を使い、 次の手順で木を作る能力があります。
頂点 1、頂点 2、 ...、 頂点 n を用意する。 各 i=1,2,...,n について次の操作を行う。
- p_i = 1 である場合、何もしない。
- p_i \neq 1 である場合、p_j < p_i であるような j のうち最大のものを j' とする。 頂点 i と 頂点 j' の間に辺を貼る。
高橋くんはこの能力を使ってお気に入りの木を作ろうとしています。 高橋くんのお気に入りの木は 頂点 1 から頂点 n の n 頂点からなり、 i 番目の辺は頂点 v_i と w_i を結んでいます。 適切な順列を使うことで、高橋くんのお気に入りの木と同型な木を作ることが可能か 判定して下さい。 可能な場合、そのような順列のうち辞書順で最も小さいものを求めて下さい。
注意
木が同型であることの定義はwikipediaを参照して下さい。 直感的には、木と木が同型であるとは、頂点の番号を無視すると同じ木になることを言います。
制約
- 2 \leq n \leq 10^5
- 1 \leq v_i, w_i \leq n
- 与えられるグラフは木である
入力
入力は以下の形式で標準入力から与えられる。
n v_1 w_1 v_2 w_2 : v_{n-1} w_{n-1}
出力
高橋くんのお気に入りの木と同型な木を作ることのできる順列が存在しない場合は -1
を出力せよ。
存在する場合は、辞書順で最小の順列を空白区切りで出力せよ。
入力例 1
6 1 2 1 3 1 4 1 5 5 6
出力例 1
1 2 4 5 3 6
(1, 2, 4, 5, 3, 6) という順列を使って木を作ると、次の図のようになります。
これは入力のグラフと同型です。
入力例 2
6 1 2 2 3 3 4 1 5 5 6
出力例 2
1 2 3 4 5 6
入力例 3
15 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15
出力例 3
-1
Score : 900 points
Problem Statement
Takahashi has an ability to generate a tree using a permutation (p_1,p_2,...,p_n) of (1,2,...,n), in the following process:
First, prepare Vertex 1, Vertex 2, ..., Vertex N. For each i=1,2,...,n, perform the following operation:
- If p_i = 1, do nothing.
- If p_i \neq 1, let j' be the largest j such that p_j < p_i. Span an edge between Vertex i and Vertex j'.
Takahashi is trying to make his favorite tree with this ability. His favorite tree has n vertices from Vertex 1 through Vertex n, and its i-th edge connects Vertex v_i and w_i. Determine if he can make a tree isomorphic to his favorite tree by using a proper permutation. If he can do so, find the lexicographically smallest such permutation.
Notes
For the definition of isomorphism of trees, see wikipedia. Intuitively, two trees are isomorphic when they are the "same" if we disregard the indices of their vertices.
Constraints
- 2 \leq n \leq 10^5
- 1 \leq v_i, w_i \leq n
- The given graph is a tree.
Input
Input is given from Standard Input in the following format:
n v_1 w_1 v_2 w_2 : v_{n-1} w_{n-1}
Output
If there is no permutation that can generate a tree isomorphic to Takahashi's favorite tree, print -1
.
If it exists, print the lexicographically smallest such permutation, with spaces in between.
Sample Input 1
6 1 2 1 3 1 4 1 5 5 6
Sample Output 1
1 2 4 5 3 6
If the permutation (1, 2, 4, 5, 3, 6) is used to generate a tree, it looks as follows:
This is isomorphic to the given graph.
Sample Input 2
6 1 2 2 3 3 4 1 5 5 6
Sample Output 2
1 2 3 4 5 6
Sample Input 3
15 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15
Sample Output 3
-1