Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 人の人が高橋大学の入学試験を受けた。試験には「国語」「数学」「理科」「英語」「塗り絵」の 5 科目がある。各受験生について、その人の「国語」「数学」「理科」「英語」の 4 科目の得点の合計に、「塗り絵」の得点の 110 / 900 倍を加えたものがその人の最終得点となる。
各受験生の各試験の得点が与えられる。N 人のうち最も最終得点が高い受験生の最終得点を求めよ。
入力
入力は以下の形式で標準入力から与えられる。
N a_1 b_1 c_1 d_1 e_1 a_2 b_2 c_2 d_2 e_2 : a_N b_N c_N d_N e_N
- 1 行目には、高橋大学の受験生の数を表す 1 個の整数 N (2 ≦ N ≦ 3049) が与えられる。
- 2 行目から N + 1 行目までの N 行には、各受験生の各試験の得点が与えられる。i + 1 行目には、i 番目の受験生の「国語」「数学」「理科」「英語」「塗り絵」の得点をそれぞれ表す 5 個の整数 a_i, b_i, c_i, d_i, e_i (各 1 ≦ i ≦ N に対し 0 ≦ a_i ≦ 80, 0 ≦ b_i, c_i, d_i ≦ 120, 731 ≦ e_i ≦ 900) がスペース区切りで与えられる。
出力
N 人のうち最も最終得点が高い受験生の最終得点を 1 行目に出力せよ。審判の出力との絶対誤差が 0.0001 以下であるとき正答とみなされる。
末尾の改行を忘れないこと。
入力例1
2 37 54 68 66 802 58 108 106 103 871
出力例1
481.4555555555555555
1 番目の受験生の最終得点は 37 + 54 + 68 + 66 + 802 × 110 / 900 = 323.02222... 点であり、2 番目の受験生の最終得点は 58 + 108 + 106 + 103 + 871 × 110 / 900 = 481.45555... 点である。2 番目の受験生の最終得点を出力すればよい。
入力例2
2 80 120 120 120 900 0 0 0 0 731
出力例2
550
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
正整数 n に対し、n の十進表記における各桁の数の和を f(n) で表す。例えば、 f(123) = 1 + 2 + 3 = 6, f(4) = 4 となる。
正整数 N が与えられる。等式 x + f(x) = N を満たす正整数 x を全て求めよ。
入力
入力は以下の形式で標準入力から与えられる。
N
- 1 行目に、1 個の整数 N (1 ≦ N ≦ 1018) が与えられる。
部分点
この問題には部分点が設定されている。
- 20 点分のテストケースは 1 ≦ N ≦ 1000 を満たす。
出力
等式を満たす正整数 x の値の個数を k とする。1 行目に k の値を出力し、続く k 行に等式を満たす正整数 x の値を昇順で各行に 1 個ずつ出力せよ。
末尾の改行を忘れないこと。
入力例1
8
出力例1
1 4
問題文で述べたように f(4) = 4 であり、 4 以外に題意を満たす正整数は存在しない。
入力例2
101
出力例2
2 91 100
複数の解が存在することがある。
入力例3
108
出力例3
0
解が存在しないこともある。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
2 個の正整数 A, B が与えられる。 A! の約数であり、かつ B! の倍数でもあるような正整数の個数を 1,000,000,007 で割った余りを求めよ。
入力
入力は以下の形式で標準入力から与えられる。
A B
- 1 行目に、2 個の整数 A, B (1 ≦ B ≦ A ≦ 10^9, A - B ≦ 100) がスペース区切りで与えられる。
部分点
この問題には部分点が設定されている。
- 5 点分のテストケースは 1 ≦ B ≦ A ≦ 15 を満たす。
- 別の 35 点分のテストケースは 1 ≦ B ≦ A ≦ 10^6, A - B ≦ 100 を満たす。
出力
題意を満たす正整数の個数を 1,000,000,007 で割った余りを 1 行目に出力せよ。
末尾の改行を忘れないこと。
入力例1
3 2
出力例1
2
正整数 n に対し、 n! は n の階乗 n × (n - 1) × (n - 2) × ... × 1 を表す。
3! = 3 × 2 × 1 = 6 の約数であり、かつ 2! = 2 × 1 = 2 の倍数であるような正整数は 2, 6 の 2 個存在する。
入力例2
15 4
出力例2
2592
入力例3
1000000 999900
出力例3
21398499
入力例4
1000000000 999999900
出力例4
745508745
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
A + B + C 枚のカードがある。そのうち A 枚にはそれぞれ赤い数字で整数が 1 つ書かれている。別の B 枚にはそれぞれ青い数字で整数が 1 つ書かれている。残りの C 枚にはそれぞれ "湯たんぽ" が書かれている。高橋君はこれらのカードを用いて、以下の手順に従いゲームを行う。
- 1. A + B + C 枚のカードを一束にまとめ、偏りなくシャッフルしてテーブルの上に置き、山札とする。
- 2. 高橋君の得点を 0 とする。
- 3. 山札から一番上のカードを引く。
- 3-A. 引いたカードに赤い数字で整数が書かれていた場合、その整数を a として高橋君の得点が a だけ増加する。
- 3-B. 引いたカードに青い数字で整数が書かれていた場合、その整数を b として高橋君の得点が b 倍になる。
- 3-C. 引いたカードに "湯たんぽ" が書かれていた場合、ゲームオーバーである。その時点での高橋君の得点を高橋君の最終得点とし、ゲームを終了する（下記の手順 4 は行わない）。
- 4. 引いたカードを破り捨て、手順 3 を再び行う。
高橋君の最終得点の期待値を求めよ。
入力
入力は以下の形式で標準入力から与えられる。
A B C a_1 a_2 .. a_A b_1 b_2 .. b_B
- 1 行目には、3 個の整数 A, B, C (1 ≦ A, B, C ≦ 50) がスペース区切りで与えられる。これらはそれぞれ、赤い数字で整数が書かれたカードの枚数、青い数字で整数が書かれたカードの枚数、"湯たんぽ" が書かれたカードの枚数を表す。（ここで C ≧ 1 であることから、ゲームは必ず問題文の手順 3-C により終了する。）
- 2 行目には、赤い数字で整数が書かれたカード A 枚に書かれた A 個の整数 a_1, a_2, ..., a_A (1 ≦ i ≦ A なる各 i に対し 1 ≦ a_i ≦ 100) がスペース区切りで与えられる。
- 3 行目には、青い数字で整数が書かれたカード B 枚に書かれた B 個の整数 b_1, b_2, ..., b_B (1 ≦ i ≦ B なる各 i に対し 1 ≦ b_i ≦ 100) がスペース区切りで与えられる。
部分点
この問題には部分点が設定されている。
- 5 点分のテストケースは 1 ≦ A, B, C ≦ 3 を満たす。
- 別の 15 点分のテストケースは 1 ≦ A, B, C ≦ 8 を満たす。
- さらに別の 20 点分のテストケースは 1 ≦ A, C ≦ 50, 1 ≦ B ≦ 8 を満たす。
出力
高橋君の最終得点の期待値を 1 行目に出力せよ。審判の出力との絶対誤差または相対誤差が 10-6 以下であるとき正答とみなされる。指数表記で出力してもよい。
末尾の改行を忘れないこと。
入力例1
1 1 1 10 2
出力例1
6.666666666666666667
赤い数字で 10 が書かれたカード、青い数字で 2 が書かれたカード、"湯たんぽ" が書かれたカードがそれぞれ 1 枚ずつ、合計で 3 枚のカードがある。これら 3 枚のカードが偏りなくシャッフルされて山札となる。山札でカードが上から「赤、青、湯たんぽ」の順に並ぶと、最終得点は (0 + 10) × 2 = 20 となり、その確率は 1/6 である。順番が「赤、湯たんぽ、青」または「青、赤、湯たんぽ」の場合、最終得点はそれぞれ 0 + 10, 0 * 2 + 10 でいずれも 10 となり、その確率は合計で 1/6 + 1/6 = 2/6 である。これら以外の順番にカードが並ぶと最終得点は 0 となる。従って、最終得点の期待値は 20 × 1/6 + 10 × 2/6 = 20/3 である。
入力例2
4 1 1 1 1 1 3 2
出力例2
4
入力例3
7 2 2 1 1 1 1 5 5 5 5 5
出力例3
29.13333333333333333
入力例4
20 8 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8
出力例4
19030.73484848484849
入力例5
15 15 1 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
出力例5
5.626676749671402077e+030
このように指数表記で出力してもよい。