No.3073 Fraction Median
タグ : / 解いたユーザー数 62
作問者 : 👑
AngrySadEight
/ テスター :
遭難者
hamamu
問題文
$N$ 個の正整数 $A_1, A_2, \dots, A_N$ が与えられます．
$1 \leq i, j \leq N$ を満たす相異なる整数組 $(i, j)$ を選ぶことを考えます．この選び方は $N(N - 1)$ 通りありますが，そのそれぞれに対して $\dfrac{A_i}{A_j}$ を考えたときに $\dfrac{N(N-1)}{2}$ 番目に小さいものを求めてください．
答えは互いに素な正の整数 $x, y$ を用いて，$\dfrac{x}{y}$ と表されます．この $x, y$ を出力してください．
制約
- 入力は全て整数
- $2 \leq N \leq 1.5 \times 10^6$
- $1 \leq A_i \leq 10^9$
入力
入力は以下の形式で標準入力から与えられる．
$N$ $A_1$ $A_2$ $\dots$ $A_N$
なお，入力が大きくなる場合があるため，高速な方法で入力を行うことを推奨する．
出力
答えが互いに素な正の整数 $x, y$ を用いて $\dfrac{x}{y}$ と表されるとき，$x, y$ をこの順に空白区切りで出力せよ．
サンプル
サンプル1
入力
4 1 3 5 6
出力
5 6
$\dfrac{A_i}{A_j}$ の値を小さい方から順に $6$ 個並べると，$\dfrac{1}{6}, \dfrac{1}{5}, \dfrac{1}{3}, \dfrac{3}{6}, \dfrac{3}{5}, \dfrac{5}{6}$ となります．
したがって，$\dfrac{A_i}{A_j}$ として $6$ 番目に小さいものは $\dfrac{5}{6}$ となるので，$5, 6$ をこの順に空白区切りで出力してください．
サンプル2
入力
5 10 10 10 10 10
出力
1 1
$\dfrac{A_i}{A_j}$ の値は全て $1$ なので，1 1 と出力してください．
なお，$x, y$ の値は互いに素である必要があります．したがって，例えば 10 10 のような出力は不正解となることに注意してください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。