Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 人がテストを受けた。i 番目の人の得点は S_i である。
得点に偏りがあったので、平均が A、最大値と最小値の差が B となるように得点を変換したい。
得点の変換は適切な実数 P, Q を選んで行う。i 番目の人の変換後の得点は P×S_i + Qである。
適切な P,Q があるかどうか判断し、もしあるならばそれを出力せよ。
入力
入力は以下の形式で標準入力から与えられる。
N A B S_1 S_2 : S_N
- 1 行目にはテストを受けた人数を表す整数 N (2 ≦ N ≦ 10^5)、変換後の平均を表す整数 A (1 ≦ A ≦ 10^9)、変換後の最大値と最小値の差を表す整数 B (1 ≦ B ≦ 10^9) が空白区切りで与えられる。
- 2 行目からの N 行のうち i 行目には i 番目の人の得点を表す整数 S_i (0 ≦ S_i ≦ 10^9) が与えられる。
出力
もし適切な変換が存在しないならば -1 を 1 行に出力せよ。
適切な変換が存在するならば、P, Q を空白区切りで 1 行に出力せよ。 出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{-6} 以下であれば許容される。
出力の末尾に改行を入れること。
入力例1
5 2 4 2 4 6 8 10
出力例1
0.5 -1
P = 0.5, Q=-1とすると得点は順に 0, 1, 2, 3, 4 となり平均が 2, 最大値と最小値の差が 4になる。
入力例2
13 29 31 3 1 4 1 5 9 2 6 5 3 5 8 9
出力例2
3.875 10.8173076
入力例3
5 1 2 34 34 34 34 34
出力例3
-1
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君はプログラミングコンテストを開く仕事をしている。
高橋君はストックしている N 個の問題から 4 問を選んでコンテストに出題する。
各問題には「難易度」という正の整数が決められており、 i 番目の問題の難易度は D_i である。
選ぶ問題は以下の 3 つの条件を満たしていなければならない。
- 2 問目の難易度は 1 問目の難易度の 2 倍以上である。
- 3 問目の難易度は 2 問目の難易度の 2 倍以上である。
- 4 問目の難易度は 3 問目の難易度の 2 倍以上である。
上の条件のもとで N 個の問題から 4 問選ぶとき、何通りの選び方があるか求めよ。
この値は非常に大きくなり得るので 1,000,000,007 (= 10^9 + 7) で割った余りを求めよ。
入力
入力は以下の形式で標準入力から与えられる
N D_1 D_2 : D_N
- 1 行目には高橋君がストックしている問題の個数 N (4 ≦ N ≦ 10^5) が与えられる。
- 2 行目からの N 行のうち i 行目には i 番目の問題の難易度を表す整数 D_i (1 ≦ D_i ≦ 10^5) が与えられる。
部分点
この問題には部分点が設定されている。
- 4 ≦ N ≦ 3,000 を満たすデータセットに正解した場合は 50 点が与えられる。
- 4 ≦ N ≦ 10^5 を満たすデータセットに正解した場合はさらに 50 点が与えられる。合計で 100 点となる。
出力
高橋君の問題の選び方の通り数を 1,000,000,007(=10^9+7) で割った余りを1行で出力せよ。 出力の末尾に改行を入れること。
入力例1
5 1 2 4 5 10
出力例1
2
1, 2, 3, 5 問目もしくは 1, 2, 4, 5 問目を選ぶことができます。
入力例2
10 11 12 13 14 15 16 17 18 19 20
出力例2
0
1 つも条件に合う選び方がないこともあります。
入力例3
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
出力例3
94
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
1 から N の整数を並び替えた数列をサイズ N の順列と呼ぶ。
同じサイズの順列 X, Y があるとき、X と Y で順序が入れ替わっている数字の組の数を X と Y の転倒距離と呼ぶ。
例えば [3, 1, 4, 2, 5] と [2, 5, 3, 4, 1] では以下の 7 個の組の順序が入れ替わっているので転倒距離は 7 である。
- (1, 2), (1, 4), (1, 5), (2, 3), (2, 4), (3, 5), (4, 5)
サイズ N の順列 A, B が与えられる。
A とも B とも転倒距離が等しいサイズ N の順列があるか判断し、あるならば 1 つ挙げよ。
答えが複数通りある場合はどれを挙げても良い。
入力
入力は以下の形式で標準入力から与えられる
N A_1 A_2 .. A_N B_1 B_2 .. B_N
- 1 行目には与えられる順列のサイズを表す整数 N (1 ≦ N ≦ 10^5) が与えられる。
- 2 行目には順列 A の要素を表す整数が N 個、空白区切りで与えられる。 i 番目の整数は A の i 番目の要素 A_i(1 ≦ A_i ≦ N) である。
- 3 行目には順列 B の要素を表す整数が N 個、空白区切りで与えられる。 i 番目の整数は B の i 番目の要素 B_i(1 ≦ B_i ≦ N) である。
- i ≠ j ならば A_i ≠ A_j と B_i ≠ B_j が成り立つ。
部分点
この問題には部分点が設定されている。
- 1 ≦ N ≦ 3,000 を満たすデータセットに正解した場合は 30 点が与えられる。
- 1 ≦ N ≦ 10^5 を満たすデータセットに正解した場合はさらに 70 点が与えられる。合計で 100 点となる。
出力
もし条件を満たす順列が存在しなければ -1 を 1 行に出力せよ。 存在するならば、その要素を空白区切りで 1 行に出力せよ。
入力例1
5 1 2 3 4 5 5 4 3 2 1
出力例1
5 2 1 3 4
出力した順列を C とすると、A と Cの転倒距離も B と C の転倒距離も 5 である。
入力例2
5 1 2 3 4 5 1 2 4 3 5
出力例2
-1
A とも B とも同じ転倒距離の順列は存在しません。
入力例3
9 3 1 4 2 5 9 7 6 8 2 1 8 3 5 7 9 4 6
出力例3
3 1 2 8 4 5 7 9 6
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋国には N 個の空き家がある。空き家は 1 から N の整数で番号付けされており、順に東西に一直線に 1 キロメートル間隔で並んでいる。 つまり i 番目の空き家は ある基準点から真東に i キロメートル進んだところにある。
この国に M 世帯の家族が引っ越してきた。 i 番目の家族は P_i 人家族である。 この M 世帯の家族に 1 軒ずつ空き家を振り分けていく。このとき複数の家族に同じ家を振り分けてはならない。
あなたの目標は「住民の距離」を最大化するように空き家を振り分けることである。 「住民の距離」とは引っ越してきた人々の中の全ての 2 人組について、その住んでいる家の距離の総和を取った値である。
最適な振り分け方をしたときの「住民の距離」の最大値を求めよ。
入力
入力は以下の形式で標準入力から与えられる
N M P_1 P_2 : P_M
- 1 行目には高橋国にある空き家の個数を表す整数 N(2 ≦ N ≦ 10^6) と 高橋国に引っ越してくる家族の世帯数 M(2 ≦ M ≦ min(N, 1,000)) が空白区切りで与えられる。
- 2 行目からの M 行のうち i 行目には i 番目の家族を構成する人数 P_i(1 ≦ P_i ≦ 100) が与えられる。
部分点
この問題には部分点が設定されている。
- 2 ≦ N ≦ 10 を満たすデータセットに正解した場合は 10 点が与えられる。
- 2 ≦ N ≦ 10^6を満たすデータセットに正解した場合はさらに 90 点が与えられる。合計で 100 点となる。
出力
「住民の距離」の最大値を 1 行に出力せよ。 出力の末尾に改行を入れること。
入力例1
4 3 1 1 2
出力例1
11
1 つめの家族の構成をAさん。2 つめの家族の構成をBさん。3 つめの家族の構成をCさん、Dさんとする。 1 つめの家族を 1 番目の空き家、 2 つめの家族を 2 番目の空き家、3 つめの家族を 4 番目の空き家に振り分けると、各二人組の距離は以下のようになる。
- AさんとBさんの距離： 1
- AさんとCさんの距離： 3
- AさんとDさんの距離： 3
- BさんとCさんの距離： 2
- BさんとDさんの距離： 2
- CさんとDさんの距離： 0
よって合計は 11 となる。これが「住民の距離」の最大値である。
入力例2
10 10 3 1 4 1 5 9 2 6 5 3
出力例2
2998
入力例3
20 10 2 7 1 8 2 8 1 8 2 8
出力例2
9852