Problem:


Score : 400 points

Problem Statement

You are given N items.

The value of the i-th item (1 \leq i \leq N) is v_i.

Your have to select at least A and at most B of these items.

Under this condition, find the maximum possible arithmetic mean of the values of selected items.

Additionally, find the number of ways to select items so that the mean of the values of selected items is maximized.  

Constraints

1 \leq N \leq 50

1 \leq A,B \leq N

1 \leq v_i \leq 10^{15}

Each v_i is an integer.

Input

The input is given from Standard Input in the following format:

N A B
v_1
v_2
...
v_N

Output

Print two lines.

The first line should contain the maximum possible arithmetic mean of the values of selected items. The output should be considered correct if the absolute or relative error is at most 10^{-6}.

The second line should contain the number of ways to select items so that the mean of the values of selected items is maximized.

Sample Input 1

5 2 2
1 2 3 4 5

Sample Output 1

4.500000
1

The mean of the values of selected items will be maximized when selecting the fourth and fifth items. Hence, the first line of the output should contain 4.5.

There is no other way to select items so that the mean of the values will be 4.5, and thus the second line of the output should contain 1.

Sample Input 2

4 2 3
10 20 10 10

Sample Output 2

15.000000
3

There can be multiple ways to select items so that the mean of the values will be maximized.

Sample Input 3

5 1 5
1000000000000000 999999999999999 999999999999998 999999999999997 999999999999996

Sample Output 3

1000000000000000.000000
1



Sample input:
5 2 2
1 2 3 4 5


Sample output:
4.500000
1

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split())
vlist=list(map(int,input().split()))
vlist.sort(reverse=True)

dp=[[0]*(N+1) for _ in range(N+1)]

for i in range(1,N+1):
  for j in range(1,N+1):
    dp[i][j]=dp[i-1][j]
    dp[i][j]=max(dp[i][j],dp[i-1][j-1]+vlist[i-1])

max_value_avg=0
for j in range(A,B+1):
  #print(j,dp[-1][j])
  value_avg=dp[-1][j]/j
  max_value_avg=max(max_value_avg,value_avg)
  
max_avg_size=[]
for j in range(A,B+1):
  value_avg=dp[-1][j]/j
  if value_avg==max_value_avg:
    max_avg_size.append(j)
#print(max_avg_size)    

def comb(n,r):
  r=min(r,n-r)
  nPr=1
  fact_r=1
  for i in range(r):
    nPr*=n-i
    fact_r*=r-i
  return nPr//fact_r

answer=0
for m in max_avg_size:
  border=vlist[m-1]
  n1=n2=n3=0
  for v in vlist:
    if v>border:
      n1+=1
    elif v==border:
      n2+=1
    else:
      n3+=1
  answer+=comb(n2,m-n1)

print(max_value_avg)
print(answer)

Submission status: Accepted

Solution code:
from collections import Counter

def comb(n,r):
    if n<r: return 0
    comb = 1
    r = min(r,n-r)
    for i in range(r):
        comb = comb * (n-i) // (i+1)
    return comb


n,a,b = map(int,input().split())
v = list(map(int,input().split()))

v.sort(reverse=True)

va_count = Counter(v[:a])
v_count  = Counter(v)

print(sum(v[:a])/a)

if v[0] == v[a-1]:
    print(sum(comb(v_count[v[0]],i ) for i in range(a,b+1)))
else:
    print(comb(v_count[v[a-1]], va_count[v[a-1]]))

Submission status: Accepted

Solution code:
from collections import Counter

n = 50
comb = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(n + 1):
        if j == 0 or j == i:
            comb[i][j] = 1
        else:
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j]

N, A, B, *X = map(int, open(0).read().split())

ctr = Counter(X)
value = 0
cnt = 0
cand = []
for i, (k, v) in enumerate(sorted(ctr.items(), reverse=True)):
    if i == 0 and A <= v:
        value = k * v
        cnt = v
        cand.append((k, v))
        break

    # Add
    c = min(v, A - cnt)
    value += k * c
    cnt += c
    cand.append((k, c))
    if cnt == A:
        break

# Count combinations
ans = 1
if len(cand) == 1:
    _, n = cand[0]
    ans = 0
    for k in range(A, min(v, B) + 1):
        ans += comb[n][k]
else:
    ans = 1
    for k, c in cand:
        ans *= comb[ctr[k]][c]

print(value / cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, A, B = map(int, input().split())
V = list(map(int, input().split()))

dp = [-1] * (N + 1)
dp[0] = 0
cnt = [0] * (N + 1)
cnt[0] = 1

for i in range(N):
    for j in range(N, 0, -1):
        if dp[j - 1] < 0:
            continue
        if dp[j] < dp[j - 1] + V[i]:
            dp[j] = dp[j - 1] + V[i]
            cnt[j] = cnt[j - 1]
        elif dp[j] == dp[j - 1] + V[i]:
            cnt[j] += cnt[j - 1]

up = -1
btm = -1
s = 0

for i in range(A, B + 1):
    if dp[i] < 0:
        continue
    if up < 0:
        up, btm = dp[i], i
        s = cnt[i]
    elif up * i < dp[i] * btm:
        up, btm = dp[i], i
        s = cnt[i]
    elif up * i == dp[i] * btm:
        s += cnt[i]


print(up / btm)
print(s)

Submission status: Accepted

Solution code:
def d_maximum_average_sets():
    from functools import reduce
    N, A, B = [int(i) for i in input().split()]
    V = sorted([int(i) for i in input().split()], reverse=True)

    def combination(n, r):
        numerator = reduce(lambda x, y: x * y, range(n, n - r, -1))
        denominator = reduce(lambda x, y: x * y, range(1, r + 1))
        return numerator // denominator

    if V[0] == V[A - 1]:  # V の上位 A 個がすべて同じ値 (v_max とおく)
        # V で値が v_max である x 個から A 個以上 B 個以下選ぶ
        x = V.count(V[0])
        count = sum([combination(x, i) for i in range(A, B + 1)])
    else:
        # 上位 A 個のうち最も値が小さな要素の値を v_min とおき、
        # v_min が上位 A 個のうち a 個あったとする。
        # V で値が v_min である x 個から a 個選ぶ。
        v_min = V[A-1]
        x, a = V.count(v_min), V[:A].count(v_min)
        count = combination(x, a)
    return '{}\n{}'.format(sum(V[:A]) / A, count)

print(d_maximum_average_sets())

Submission status: Accepted

Solution code:
import sys
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n,a,b = map(int,input().split())
v_list = list(map(int,input().split()))

v_list.sort(reverse=True)
max_mean = sum(v_list[:a])/a

number = v_list[a-1]

if v_list[:a].count(number) == a:
    count = 0
    for i in range(a,b+1):
        rest_list = v_list[i:]
        all_num = v_list.count(number)
        rest_num = rest_list.count(number)
        if rest_num > 0 or v_list[i-1] == number:
            count += comb(all_num,rest_num)
    print(max_mean)
    print(count)
else:
    rest_list = v_list[a:]
    all_num = v_list.count(number)
    rest_num = rest_list.count(number)
    print(max_mean)
    print(comb(all_num,rest_num))

Submission status: Accepted

Solution code:
from collections import Counter
def nCr(n, r):
    t = 1
    for i in range(n - r + 1, n + 1):
        t *= i
    for i in range(2, r + 1):
        t //= i
    return t

def main():
    N, A, B = map(int, input().split())
    V = list(map(int, input().split()))
    VV = Counter(V)
    m = 0
    c = 0
    for v in sorted(VV.keys(), reverse=True):
        vc = VV[v]
        if c + vc <= A:
            m += v * vc
            c += vc
            continue
        break
    else:
        print(m / c)
        print(1)
        return
    min_c = A - c
    max_c = min(B - c, vc)
    m += v * min_c
    c += min_c
    print(m / c)
    if m != c * v:
        max_c = min_c
    r = 0
    for i in range(min_c, max_c + 1):
        r += nCr(vc, i)
    print(r)

main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np
from math import factorial

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, A, B = lr()
V = np.array(lr())
V.sort()
ave = V[-A:].sum() / A
print(ave)
border = V[-A]
left_i = np.searchsorted(V, border, side='left')
right_i = np.searchsorted(V, border, side='right')
seg = right_i - left_i  # 使える数字たち
done = N - right_i
use = A - done  # 使う幅

def combinations_count(n, r):  # 組み合わせ
    return factorial(n) // factorial(n - r) // factorial(r)

answer = combinations_count(seg, use)
if border == ave:
    for x in range(use+1, min(B-done, seg)+1):
        answer += combinations_count(seg, x)

print(answer)
# 05

Submission status: Accepted

Solution code:
class cmbs(object):
    def __init__(self, mod=9007199254740997):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 2 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

def main():
    N, A, B = map(int, input().split())
    v = list(map(int, input().split()))
    v.sort(reverse=True)
    m = sum(v[:A])/A
    print(m)
    if v.count(v[A-1]) == N:
        c = cmbs()
        a = 0
        for i in range(A, B+1):
            a += c.cmb(N, i)
        print(a)
    elif v[0] == v[A-1]:
        c = cmbs()
        a = 0
        for i in range(A, min(v.count(v[A-1]), B) + 1):
            a += c.cmb(v.count(v[A-1]), i)
        print(a)
    elif v.count(v[A-1]) == 1:
        print(1)
    else:
        c = cmbs()
        r = A - v.index(v[A-1])
        print(c.cmb(v.count(v[A-1]), r))
main()

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
V = list(map(int, input().split()))
V.sort(reverse=True)

N = 50
C = [[0]*(N+1) for i in range(N+1)] #C[n][k] > nCk

for i in range(N+1):
    for j in range(i+1):
        if j == 0 or j == i:
            C[i][j] = 1
        else:
            C[i][j] = C[i-1][j-1]+C[i-1][j]

def comb3(n, k):
    return C[n][k]

ans = 0
x = 0
y = 0
for i in range(n):
    if i <= a-1:
        ans += V[i]
        if V[i] == V[a-1]:
            x += 1
            y += 1
    else:
        if V[i] == V[a-1]:
            x += 1

if V[0] != V[a-1]:
    cnt = comb3(x, y)
    print(ans/a)
    print(cnt)
else:
    cnt = 0
    for i in range(a, b+1):
        if i <= x:
            cnt += comb3(x, i)
    print(ans/a)
    print(cnt)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
V = list(map(int, input().split()))
V.sort(reverse=True)

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 0
x = 0
y = 0
for i in range(n):
    if i <= a-1:
        ans += V[i]
        if V[i] == V[a-1]:
            x += 1
            y += 1
    else:
        if V[i] == V[a-1]:
            x += 1

if V[0] != V[a-1]:
    cnt = combinations_count(x, y)
    print(ans/a)
    print(cnt)
else:
    cnt = 0
    for i in range(a, b+1):
        if i <= x:
            cnt += combinations_count(x, i)
    print(ans/a)
    print(cnt)

Submission status: Accepted

Solution code:
def main():
    from decimal import Decimal

    N, A, B = map(int, input().split())
    *v, = map(Decimal, input().split())

    v.sort(reverse=True)

    max_average = sum(v[:A]) / A

    tail = v[A - 1]
    contained = [0] * (N + 1)
    s = 0
    for i, x in enumerate(v, start=1):
        if x == tail:
            s += 1
        contained[i] = s

    def choose(n, a):
        if n - a < a:
            return choose(n, n - a)
        x, y = 1, 1
        for i in range(a):
            x = x * (n - i)
            y = y * (i + 1)
        return x // y

    count = 0
    for k in range(A, B + 1):
        if (k > A) and (v[k - 1] != max_average): break
        count += choose(contained[-1], contained[k])

    print(max_average)
    print(count)


if __name__ == '__main__':
    main()

# editorial
# K個選んだときの品物の価値の平均の最大値と
# K+1個個選んだときの品物の価値の平均の最大値の差を比較

# v[:A]は一つの値からなる->平均値を下げずに要素を追加できる可能性
# v[:A]は異なる値を含む->範囲外の値はより小さいので要素を追加できない

Submission status: Accepted

Solution code:
def main():
    from decimal import Decimal

    N, A, B = map(int, input().split())
    *v, = map(Decimal, input().split())

    v.sort(reverse=True)

    max_average = sum(v[:A]) / A

    tail = v[A - 1]
    contained = [0] * (N + 1)
    s = 0
    for i, x in enumerate(v, start=1):
        if x == tail:
            s += 1
        contained[i] = s

    def choose(n, a):
        x, y = 1, 1
        for i in range(a):
            x = x * (n - i)
            y = y * (i + 1)
        return x // y

    count = 0
    for k in range(A, B + 1):
        if (k > A) and (v[k - 1] != max_average): break
        count += choose(contained[-1], contained[k])

    print(max_average)
    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,a,b=map(int,input().split())
v=sorted(list(map(int,input().split())),reverse=1)
tmp=sum(v[:a])
ans=(tmp,a)
x=[a-1]
for i in range(a,b):
    tmp+=v[i]
    if ans[0]*(i+1)<=ans[1]*tmp:
        if ans[0]*(i+1)==ans[1]*tmp:
            x.append(i)
        else:
            x=[i]
print(ans[0]/ans[1])
ans=0
for i in x:
    a,b=v.count(v[i]),v[i+1:].count(v[i])
    ans+=comb(a,b)
print(ans)

Submission status: Accepted

Solution code:
C = [[0 for j in range(51)] for i in range(51)]
for i in range(51):
    C[i][0] = 1
for i in range(1, 51):
    for j in range(1, 51):
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
n, a, b = map(int, input().split())
*V, = map(int, input().split())
V.sort(reverse=True)
print(sum(V[:a]) / a)
if V[0] == V[a - 1]:
    x = V.count(V[a - 1])
    print(sum([C[x][y] for y in range(a, b + 1)]))
else:
    x = V.count(V[a - 1])
    y = a - len([v for v in V if v > V[a - 1]])
    print(C[x][y])

Submission status: Accepted

Solution code:
MOD = 1
m = 100
COMB_table = [[0]*(m+1) for _ in range(m+1)]

fac = [0] * m
finv = [0] * m
inv = [0] * m


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            finv[i] = finv[i - 1] * inv[i] % MOD


def COMB(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


def make_COMB_table(m):
    for i in range(m+1):
        for j in range(i+1):
            if j == 0 or j == i:
                COMB_table[i][j] = 1
            else:
                COMB_table[i][j] = COMB_table[i-1][j-1] + COMB_table[i-1][j]


def COMB_2(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return COMB_table[n][k]


make_COMB_table(m)


def main():
    from collections import Counter
    N, A, B = (int(i) for i in input().split())
    V = [int(i) for i in input().split()]
    V.sort(reverse=True)
    ans = sum(v for v in V[:A])/A
    c = Counter(V)
    c_ans = Counter(V[:A])
    cnt = 0
    if V[0] != V[A-1]:
        cnt = COMB_2(c[V[A-1]], c_ans[V[A-1]])
    else:
        for i in range(A, B+1):
            cnt += COMB_2(c[V[0]], i)
    print(ans)
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
m = 100
COMB_table = [[0]*(m+1) for _ in range(m+1)]


def make_COMB_table(m):
    for i in range(m+1):
        for j in range(i+1):
            if j == 0 or j == i:
                COMB_table[i][j] = 1
            else:
                COMB_table[i][j] = COMB_table[i-1][j-1] + COMB_table[i-1][j]


def COMB_2(n, k):
    return COMB_table[n][k]


make_COMB_table(m)


def main():
    from collections import Counter
    N, A, B = (int(i) for i in input().split())
    V = [int(i) for i in input().split()]
    V.sort(reverse=True)
    ans = sum(v for v in V[:A])/A
    c = Counter(V)
    c_ans = Counter(V[:A])
    cnt = 0
    if V[0] != V[A-1]:
        cnt = COMB_2(c[V[A-1]], c_ans[V[A-1]])
    else:
        for i in range(A, B+1):
            cnt += COMB_2(c[V[0]], i)
    print(ans)
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N,A,B=map(int,readline().split())
    v=list(map(int,readline().split()))
    v.sort(reverse=True)

    #average
    average=sum(v[:A])/A

    #combination
    res=0
    x=v[A-1]
    x_count=v.count(x)
    x_count_copy=x_count
    if x==v[0]:
        up=1
        down=1
        for i in range(1,A):
            up*=x_count_copy
            x_count_copy-=1
            down*=i
        if x_count>=B:
            for i in range(A,B+1):
                up*=x_count_copy
                x_count_copy-=1
                down*=i
                res+=up//down
        else:
            for i in range(A,x_count+1):
                up*=x_count_copy
                x_count_copy-=1
                down*=i
                res+=up//down
    else:
        m=A
        for i in range(A):
            if v[i]>x:
                m-=1
            else:
                break
        up=1
        down=1
        for i in range(1,m+1):
            up*=x_count_copy
            x_count_copy-=1
            down*=i
        res=up//down

    print(average)
    print(res)
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
V = list(map(int,input().split()))

V.sort(reverse = True)
s = 0
m = V[a-1]
ans = sum(V[:a])/a
print(ans)
cnt = V.count(m)
left = V.index(m)
ans = 0
memo = {}
def combi(m,k):
    if m*100+k in memo:
        return memo[m*100+k]
    elif k == 0:
        return 1
    else:
        memo[m*100+k] = combi(m,k-1)*(m-k+1)//k
        return memo[m*100+k]

if left == 0:
    for i in range(a,min(b,cnt)+1):
        ans += combi(cnt,i)
else:
    ans += combi(cnt,a-left)
    # if (sum(V[:a])/a).is_integer():
    #     ans *= pow(2,V.count(int(V[:a]/a)))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def combination_mod(n, r):
    # mod取りながらcombination
    if r > n:
        return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i)
        rf = rf * (i + 1)
    return nf // rf


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/abc057/tasks/abc057_d
# ソートしておけば、平均の最大化は簡単 (上位A個選べばよい)
# 通りの数は？
# もし単調増加なら必ず1通り

# 平均の最大化が変わらないとは...?
# 大きい方からA個目の数(cとする)が複数ある場合は別のを選らべる(通りが増える)
# 具体的にはn_c C rの通りの数が存在する(rは上位A個の中に存在するcの数)

# 三種類の場合があるな
# 単調増加のときは簡単

N, A, B = read_ints()
V = read_ints()
V.sort(reverse=True)
V_A = V[:A]
ans1 = sum(V_A) / A
# 単調増加の場合
if V[A] != V[A - 1]:
    print(ans1)
    print(1)
    exit()

# A個選ぶのが最適の場合
if V_A[0] != V_A[-1]:
    c = V_A[-1]
    n_c = V.count(c)
    r = V_A.count(c)
    # print(n_c, r)
    ans2 = combination_mod(n_c, r)
    print(ans1)
    print(ans2)
    exit()

# 全部同じ場合
n_same = V.count(V[0])
if n_same > A:
    ans2 = 0
    r_max = min(n_same, B)  # 最大これだけ選べる
    for i in ra(A, r_max + 1):
        ans2 += combination_mod(n_same, i)
    print(ans1)
    print(ans2)
    exit()


raise ValueError('CE出てほしい')

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
V = list(map(int, input().split()))

def comb(n,r):
    ans = 1
    for i in range(r):
        ans *= n-i
    for i in range(r):
        ans //= i+1
    return ans

V.sort(reverse=True)
print(sum(V[:A])/A)

def solve(V,A,B):
    if V[A-1]>V[A]:
        return 1
    a = V[A-1]
    l,r = -1,-1
    for i in range(N):
        if l==-1 and V[i]==a:
            l = i
        if r==-1 and V[i]<a:
            r = i
    if r==-1:
        r = N
    lower = A-l
    upper = min(r,B)-l
    total = r-l
    ans = 0
    if V[0]==a:
        for i in range(lower,upper+1):
            ans += comb(total,i)
    else:
        ans += comb(total,lower)
    return ans
print(solve(V,A,B))

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
v = list(map(int, input().split()))
v = sorted(v,reverse=True)

# (合計, 個数)
max_avg = (sum(v[:A]), A)

t = v[A-1]
num1 = v[:A].count(t)
num2 = v[A:].count(t)

fact = [0]*(N+1)
ifact = [0]*(N+1)
inv = [0]*(N+1)
p=170141183460469231731687303715884105727

def combination(n,fact,ifact):
    fact[0] = 1
    fact[1] = 1
    ifact[0] = 1
    ifact[1] = 1
    inv[1] = 1
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%p
        inv[i] = p - inv[p%i]*(p//i)%p
        ifact[i] = (ifact[i-1]*inv[i])%p
def op(n,k):
    if k<0 or k>n or n<0:
        return 0
    return (fact[n]*ifact[k]*ifact[n-k])%p

combination(N,fact,ifact)

res = int(op(num1+num2, num1))
if v[0]==v[-1]:
    res = 0
    for i in range(A,B+1):
        res += int(op(N, i))
elif v[0] == v[B-1]:
    res = 0
    for i in range(A, B+1):
        res += int(op(num1+num2,i))
elif v[0] == v[A-1]:
    res = 0
    for i in range(A, min(B, A+num2)+1):
        res += int(op(num1+num2, i))
print(max_avg[0]/max_avg[1])
print(res)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
v = list(map(int, input().split()))

# dp[i] := i個選ぶときの価値の最大値
# dq[i] := i個選ぶときの価値の最大値の個数
dp = [0] * (n + 1)
dq = [0] * (n + 1)

dq[0] = 1

for i in range(n):
    val = v[i]
    # i番目を選ぶとき
    for j in range(n)[::-1]:
        if dp[j + 1] == dp[j] + val:
            dq[j + 1] += dq[j]
        if dp[j + 1] < dp[j] + val:
            dp[j + 1] = dp[j] + val
            dq[j + 1] = dq[j]
        else:
            continue

max_ans = 0
max_cnt = 10 ** 30
for i in range(a, b + 1):
    if max_cnt * dp[i] > max_ans * i:
        max_ans = dp[i]
        max_cnt = i

ans = 0
for i in range(a, b + 1):
    if max_cnt * dp[i] == max_ans * i:
        ans += dq[i]

print(max_ans / max_cnt)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N, A, B = map(int, input().split())
V = list(map(int, input().split()))
V.sort(reverse=True)

S = sum(V[:A])
cnt = A
mx = S / cnt
L = [cnt]

for v in V[A:]:
    if cnt == B:
        break
    cnt += 1
    S += v
    if mx < S / cnt:
        mx = S / cnt
        L = []
    if mx == S / cnt:
        L.append(cnt)

def ncr(n, r):
    ret = 1
    for i in range(r):
        ret *= (n - i)
    for i in range(1, r + 1):
        ret //= i
    return ret

print(mx)
ans = 0
cntV = Counter(V)
for c in L:
    cnt = Counter(V[:c])
    prd = 1
    for x, c in cnt.items():
        prd *= ncr(cntV[x], c)
    ans += prd
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, A, B = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
res = 0
xi = 0
xis = []
for i in range(A - 1, B):
  t = 0
  for j in range(i + 1): t += a[j]
  t /= i + 1
  if res < t:
    res = t
    xi = i + 1
    xis = [i + 1]
  elif res == t:
    xis.append(i + 1)
resc = 0
while len(xis):
  xi = xis.pop()
  d = dd(int)
  for x in a: d[x] += 1
  d2 = dd(int)
  for i in range(xi): d2[a[i]] += 1
  #print(d, d2)
  tt = 1
  for k in d2.keys():
    t = 1
    for i in range(d[k], 0, -1):
      if i <= d[k] - d2[k]: break
      t *= i
    for i in range(1, d2[k] + 1): t //= i
  #print(k, t, d[k], d2[k])
    tt *= t
  resc += tt

print(res)
print(resc)

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
V = list(map(int, input().split()))
V.sort(reverse = True)

total = sum(V[:A])

ave = total / A

tmp = V[A - 1]

count = V.count(tmp)

def combination(n, r): #nCrを求める
    if n - r > r:
        r = n - r
    tmp = 1
    for i in range(n - r + 1, n + 1):
        tmp *= i
    for i in range(1, r + 1):
        tmp //= i
    return tmp





if V[0] == V[A - 1]: #上からA個が同じ
    ans = 0
    for i in range(A, min(B, count) + 1):
        ans += combination(count, i)

else: #A個ちょうど取るのがいいとき
    count2 = V[:A].count(tmp)
    ans = combination(count, count2)

print (ave)
print (ans)

Submission status: Accepted

Solution code:
import collections
N,A,B=map(int,input().split())
v=list(map(int,input().split()))
v.sort(reverse=True)
l=[]
frac=[1]*51
modfrac=[1]*51
avg=0
for i in range(1,51):
    frac[i]=frac[i-1]*i
for i in range(A):
    l.append(v[i])
avg=(sum(l)/len(l))
mi=min(l)
cnt=0
c1 = collections.Counter(l)
c2 = collections.Counter(v)
if len(set(l))==1:
    n=c2[mi]
    for i in range(A,min(B+1,n+1)):
        up=1
        down=1
        for j in range(1,i+1):#nCi
            up=up*(n-i+j)
            down=down*j
        cnt=cnt+(up//down)
else:
    n=c2[mi]
    r=c1[mi]
    up=1
    down=1
    for i in range(1,r+1):
        up=up*(n+1-i)
        down=down*i
    cnt=(up//down)
print(avg)
print(cnt)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# ソートして上位A個を使うと最大
# 場合の数は，vの最大値がA個以上あるかで場合分け

N,A,B = LI()
v = LI()

def linear_nCk(n,k):
    a = [1]*(k+1)
    for i in range(1,k+1):
        a[i] = a[i-1]*(n-k+i)//i
    return a[-1]

v.sort(reverse=True)

d = defaultdict(int)
use = defaultdict(int)

for i in range(N):
    d[v[i]] += 1
    if i < A:
        use[v[i]] += 1

if v[0] == v[A-1]:
    num = d[v[0]]
    ans = 0
    for i in range(A,min(B+1,num+1)):
        ans += linear_nCk(num,i)
    print(v[0])
    print(ans)
else:
    max_val = 0
    ans = 1
    for k,v in use.items():
        ans *= linear_nCk(d[k],v)
        max_val += k*v
    print(max_val/A)
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from copy import deepcopy
from fractions import Fraction

def main():
    n, a, b = map(int, input().split())
    v = list(map(int, input().split()))
    dp = [[0, 0] for i in range(n + 1)]
    dp[0] = [0, 1]
    for j in range(n):
        dppre = deepcopy(dp)
        for i in range(n):  # 配る
            vnew = dppre[i][0] + v[j]
            ways = dppre[i][1]
            if vnew > dp[i + 1][0]:
                dp[i + 1] = [vnew, ways]
            elif vnew == dp[i + 1][0]:
                dp[i + 1][1] += ways

    maxave = 0
    for i in range(a, b + 1):
        maxave = max(maxave, Fraction(dp[i][0], i))
    ways = 0
    for i in range(a, b + 1):
        if Fraction(dp[i][0], i) == maxave:
            ways += dp[i][1]
    print(float(maxave))
    print(ways)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from copy import deepcopy

def main():
    n, a, b = map(int, input().split())
    v = list(map(int, input().split()))
    dp = [[0, 0] for i in range(n + 1)]
    dp[0] = [0, 1]
    for j in range(n):
        dppre = deepcopy(dp)
        for i in range(n):  # 配る
            vnew = dppre[i][0] + v[j]
            ways = dppre[i][1]
            if vnew > dp[i + 1][0]:
                dp[i + 1] = [vnew, ways]
            elif vnew == dp[i + 1][0]:
                dp[i + 1][1] += ways

    maxave = 0.0
    for i in range(a, b + 1):
        maxave = max(maxave, dp[i][0] / i)
    ways = 0
    for i in range(a, b + 1):
        if dp[i][0] / i == maxave:
            ways += dp[i][1]
    print(maxave)
    print(ways)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

C = [[0]*(61) for _ in range(61)]

for i in range(61):
    C[i][0] = 1
    
    for j in range(1, 61):
        C[i][j] = C[i-1][j-1]+C[i-1][j]

N, A, B = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse=True)
cnt1 = Counter(v)
S = sum(v[:A])
print(S/A)

ans = 0

for i in range(A, B+1):
    s = sum(v[:i])
    
    if s*A!=S*i:
        break
    
    cnt2 = Counter(v[:i])
    mark = v[:i][-1]
    ans += C[cnt1[mark]][cnt2[mark]]

print(ans)

Submission status: Accepted

Solution code:
# solution
import io
from scipy.misc import comb

nim, mike, kite = map(int, input().split())
V = list(map(int, input().split()))
V.sort(reverse=True)
print(sum(V[:mike]) / mike)
Ath_CNT = V.count(V[mike - 1])
V_than_Ath_CNT = len([v for v in V if v > V[mike - 1]])
if max(V) == V[mike - 1]:
    ans = 0
    for k in range(mike, kite + 1):
        ans += comb(Ath_CNT, k, 1)
else:
    ans = comb(Ath_CNT, mike - V_than_Ath_CNT, 1)
print(ans)

Submission status: Accepted

Solution code:
import math
def nCr(n,r):
    return (math.factorial(n)//(math.factorial(r)*math.factorial(n-r)))
N, A, B = map(int,input().split())
v = sorted(list(map(int,input().split())), reverse = True)
print(sum(v[:A])/A)

t = v[A-1]
m, u = 0, 0
for k in range(A):
    if v[k] == t:
        m += 1
for k in range(A,N):
    if v[k] == t:
        u += 1
if m == A:
    ans = 0
    for k in range(A,min(A+u+1,B+1)):
        ans += nCr(m+u,k)
    print(ans)
else:
    print(nCr(m+u,m))

Submission status: Accepted

Solution code:
def comb(n, r):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
    return x // y

n, a, b = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse = True)
c = b - a + 1
s = [0] * c
for i in range(c):
    s[i] = sum(v[0 : a + i]) / (a + i)
m = max(s)
ans = 0
for i in range(c):
    if s[i] == m:
        r = v[0 : a + i].count(v[a + i - 1])
        l = v.count(v[a + i - 1])
        ans += comb(l, min(r, l - r))
print(m)
print(ans)

Submission status: Accepted

Solution code:
import math
n, a, b = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse=True)
c = 0
def comb(N, R):
	if N < R:
		return 0
	return math.factorial(N) // (math.factorial(N - R) * math.factorial(R))
if len(set(v[:a])) == 1:
	x = v[:a][0]
	d = 0
	for i in v:
		if i == x:
			d += 1
	for i in range(a,min(d+1,b+1)):
		c += comb(d,i)
	print (x)
	print (c)
else:
	x = v[:a][0]
	y = sorted(v[:a])
	av = sum(v[:a])/a
	z = y[0]
	d = 0
	for i in v:
		if i == z:
			d += 1
	e = 0
	for i in y:
		if i == z:
			e += 1
	c = comb(d,e)
	print (av)
	print (c)