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:
#!/usr/bin/env python3
import sys


def combination(n, k):
    if n - k < k:
        return combination(n, n-k)
    
    if k == 0:
        return 1
    
    return combination(n-1, k-1) * n // k


def solve(N: int, A: int, B: int, v: "List[int]"):
    v.sort(reverse=True)
    d = dict()
    for value in v:
        if value not in d:
            d[value] = 1
        else:
            d[value] += 1
    
    average = sum(v[:A]) / A
    print(average)

    count = d[v[A-1]]
    fixed = v.index(v[A-1])
    
    if fixed > 0:
        print(combination(count, A - fixed))
        return

    if B - fixed < count:
        k2 = B - fixed
    else:
        k2 = count
    
    k1 = A - fixed

    ret = 0
    for k in range(k1, k2+1):
        ret += combination(count, k)
    print(ret)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    v = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A, B, v)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, a, b = map(int,input().split())
v = sorted(list(map(int,input().split())),reverse = True)
set_v = set()
cnt_v = []
for i in v:
    if i not in set_v:
        set_v.add(i)
        cnt_v.append(i)

from collections import Counter
from operator import itemgetter
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
c = Counter(v)
sum = 0
cnt = 0
num = 0
if c[v[0]] >= a:
    print(float(v[0]))
    for i in range(a,min(b,c[v[0]]) + 1):
        num += combinations_count(c[v[0]], i)
    print(num)
    exit()
for i in cnt_v:
    if c[i] < a:
        a -= c[i]
        b -= c[i]
        sum += c[i]*i
        cnt += c[i]
    else:
        sum += i*a
        cnt += a
        print(sum/cnt)
        print(combinations_count(c[i],a))
        break

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def fac(n):
    if n== 1 or n == 0:
        return 1
    return n * fac(n-1)

def comb(n, k):
    if k >n:
        return 0
    return fac(n)/(fac(k) * fac(n-k))

def solve():
    n, a, b = f()
    v = f()
    
    v = sorted(v, reverse = True)

    c = v[a-1]

    cnt1 = 0
    total = 0

    for i in range(n):
        if v[i] == c:
            total += 1
            if i < a:
                cnt1 += 1


    print("{:.7f}".format(sum(v[0:a])/a))
    if v[0] == c:
        ans = 0
        for i in range(a, b+1):
            ans += comb(total, i)
        print(int(ans))
    else:
        print(int(comb(total, cnt1)))

solve()

Submission status: Accepted

Solution code:
from math import factorial
from itertools import accumulate
from collections import Counter
N, a, b = [int(item) for item in input().split()]
v = sorted([int(item) for item in input().split()], reverse=True)

vsum = list(accumulate(v))
vcounts = []
for i in range(N):
    vcounts.append(Counter(v[:i+1]))

ans = 0
ans_count = 0
for i in range(a, b+1):
    val = vsum[i-1] / i
    if val > ans:
        n = vcounts[N-1][v[i-1]]
        r = vcounts[i-1][v[i-1]]
        ans_count = factorial(n) // factorial(r) // factorial(n-r)
        ans = val
    elif val == ans:
        n = vcounts[N-1][v[i-1]]
        r = vcounts[i-1][v[i-1]]
        ans_count += factorial(n) // factorial(r) // factorial(n-r)
print(ans)
print(ans_count)

Submission status: Accepted

Solution code:
import math
from collections import Counter
N, A, B = map(int, input().split())
V = sorted(Counter(list(map(int, input().split()))).items(), key=lambda x: x[0], reverse=True)
if A <= V[0][1]:
    print(V[0][0])
    x = min(V[0][1], B)
    num = 0
    for i in range(A, x + 1):
        num += math.factorial(V[0][1]) // (math.factorial(V[0][1] - i) * math.factorial(i))
    print(num)
    exit()
l = []
num = 0
for v, n in V:
    if n >= A:
        l.extend([v] * A)
        num = math.factorial(n) // (math.factorial(n - A) * math.factorial(A))
        break
    else:
        l.extend([v] * n)
        A -= n
        B -= n
print(sum(l) / len(l))
print(num)

Submission status: Accepted

Solution code:
#D問題

#factorial(階乗)
def factorial(facn):
    ret=1
    for i in range(facn):
        ret*=(i+1)
    return ret
#combination(組み合わせC)
def comb(comb1,comb2):
    x=min(comb1,comb2)
    y=max(comb1,comb2)
    bunshi=factorial(y)
    bunbo=factorial(x)*factorial(y-x)
    return int(bunshi/bunbo)

N,A,B=map(int,input().split())
v=list(map(int,input().split()))
v.sort(reverse=True)
dp=[0 for i in range(N)]
for i in range(A):
    if i == 0:
        dp[0]=v[0]
    else:
        dp[i]=dp[i-1]+v[i]
MAX=dp[A-1]/A
V=v[A-1]
left=v[:A]
right=v[A:]
LV=left.count(V)
RV=right.count(V)
if V == v[0]:
    Vsum=LV+RV
    com=0
    for i in range(A,min(B+1,Vsum+1)):
        com+=comb(Vsum,i)        
else:
    com=comb(LV+RV,LV)
print(MAX)
print(com)

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
V = sorted([int(i) for i in input().split()], reverse = True)

VA = V[:A]
print(sum(VA) / A)

last = VA[-1]
x = VA.count(last)
y = V.count(last)

def comb(n, k):
    k = min(k, n - k)
    result = 1
    for i in range(n, n - k, -1):
        result *= i
    for i in range(1, k + 1):
        result //= i 
    return result

if V.count(V[0]) > A:
    ans = 0
    u = min(V.count(V[0]), B)
    for i in range(A, u + 1):
        ans += comb(y, i)
else:
    ans = comb(y, x)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
try:
    from scipy.special import comb
except ImportError:
    from scipy.misc import comb

def main():
    input = sys.stdin.readline
    N, A, B = map(int, input().split())
    V = list(map(int, input().split()))
    V = sorted(V, key=lambda x: -x)

    m_ave = sum(V[:A]) / A
    b = A
    while b < B:
        if V[0] == V[b]:
            b += 1
        else:
            break

    if A == b:
        ans = 1
        c = Counter(V[:A])
        d = Counter(V)
        for key in c.keys():
            n = d[key]
            r = c[key]
            ans *= comb(n, r, exact=True)

    else:
        d = Counter(V)
        key = V[0]
        n = d[key]
        ans = 0
        for r in range(A, b+1):
            ans += comb(n, r, exact=True)

    print(m_ave)
    print(ans)


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)

AVERAGE=V[:A]

print(sum(AVERAGE)/A)

MIN=AVERAGE[-1]

MINUSE=0
for a in AVERAGE:
    if a==MIN:
        MINUSE+=1

MAXUSE=0
for a in V[:B]:
    if a==MIN:
        MAXUSE+=1

ALLUSE=0
for a in V:
    if a==MIN:
        ALLUSE+=1

import math

if V[0]!=MIN:
    print(math.factorial(ALLUSE)//math.factorial(MINUSE)//math.factorial(ALLUSE-MINUSE))

else: 
    ANS=0
    for use in range(MINUSE,MAXUSE+1):
            ANS+=math.factorial(ALLUSE)//math.factorial(use)//math.factorial(ALLUSE-use)

    print(ANS)

Submission status: Accepted

Solution code:
def fuct(n:int)->int:
    if n<=1:
        return 1
    else:
        return n * fuct(n-1)

def main():
    n,a,b = map(int, input().split())
    v = list(map(int, input().split()))
    v = sorted(v, reverse=True)
    print(sum(v[:a])/a)
    res = 0

    if v[0]==v[a-1]:
        vn = v.count(v[0])
        for r in range(a,b+1):
            res += fuct(vn)//(fuct(vn-r) * fuct(r))
    else:
        vn = v.count(v[a-1])
        r = v[:a].count(v[a-1])
        res += fuct(vn)//(fuct(vn-r) * fuct(r))

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        
# 二項係数
def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod

# nCrの和をとる関数
def comb_sum(base: int, start: int, last: int, mod: int, fac: list, facInv:list):
    ret = 0
    for i in range(start, last+1):
        ret += nCr(base, i, mod, fac, facInv)
        
    return ret

n,a,b = li()
v = list(li())

v.sort(reverse=True)
maxv = max(v)
maxs = v.count(maxv)

MOD = 2**61-1
MAXN = 100
inv = inv_mod(MAXN, MOD)
fac = fact(MAXN, MOD)
fac_inv = fact_inv(MAXN, inv, MOD)


if maxs <= a:
    ans = sum(v[:a]) / a
    lastcnt = v.count(v[a-1])
    pat = nCr(lastcnt, a-v.index(v[a-1]), MOD, fac, fac_inv)
    
elif a < maxs < b:
    ans = maxv
    pat = comb_sum(maxs, a, maxs, MOD, fac, fac_inv)
    
else:
    ans = maxv
    pat = comb_sum(maxs, a, b, MOD, fac, fac_inv)
    
print(ans)
print(pat)

Submission status: Accepted

Solution code:
d = {}

def nCr(n, r):
    if n < r:
        return 0
    if n == r or r == 0:
        return 1
    if (n, r) in d:
        return d[(n, r)]
    d[(n, r)] = nCr(n - 1, r) + nCr(n - 1, r - 1)
    return d[(n, r)]

if __name__ == '__main__':
    n, a, b = map(int, input().split())
    v = sorted((int(s) for s in input().split()), reverse=True)
    print(sum(v[:a]) / a)
    x = v.count(v[a - 1])
    print(nCr(x, v[:a].count(v[a - 1])) if v[0] > v[a - 1] else sum(nCr(x, i) for i in range(a, b + 1)))

Submission status: Accepted

Solution code:
# 組み合わせ　n_C_r
def comb(n,r):
    r = min(r,n-r)
    result = 1
    for i in range(n-r+1,n+1):
        result *= i
    for i in range(1,r+1):
        result //= i
    return result

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

V.sort(reverse=True)

ave = sum(V[:A])/A
pat = 0
note = 0
cnt = 0
for v in V:
    if v > V[A-1]:
        note += 1
    elif v == V[A-1]:
        cnt += 1
    elif v < V[A-1]:
        break

if V[0] == V[A-1]:
    for i in range(A-note,B+1-note):
        if i > cnt:
            break
        pat += comb(cnt,i)
else:
    pat = comb(cnt,A-note)

print(ave)
print(pat)

Submission status: Accepted

Solution code:
N,A,B=list(map(int, input().strip().split()))
v=sorted(list(map(int, input().strip().split())))[::-1]

def frac(n):
    ret=1
    for i in range(2,n+1):
        ret*=i
    return ret
def combi(n,a):
    return frac(n)//frac(a)//frac(n-a)

sm=sum(v[:A])
ave=sm/A
ans=0

minA = v[A-1]
ct_mA = v[:A].count(minA)
nmA = v.count(minA)

if ave == minA:
    i=0
    while A+i <=B and i<=nmA-ct_mA:
        ans+=combi(nmA,i+A)
        i+=1
else:
    ans = combi(nmA,ct_mA)
print(ave)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from bisect import bisect_left
n, a, b = map(int, input().split())
v = sorted(map(int, input().split()))[::-1]
print(sum(v[:a])/a)
prev = v[0]
cnt = 0
rle = []
for i in v:
    if i != prev:
        rle.append(cnt)
        prev = i
        cnt = 1
    else:
        cnt += 1
rle.append(cnt)
cum = [0]
for i in rle:
    cum.append(cum[-1] + i)

left = bisect_left(cum, a)
m = rle[left-1]
a = a - cum[left-1]
if left == 1:
    b = min(cum[left], b) - cum[left-1]
else:
    b = a

from math import factorial
def comb(n, r):
    return factorial(n) // factorial(n-r) // factorial(r)

ans = 0
for i in range(a, b+1):
    ans += comb(m,i)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
import sys
import math
from functools import lru_cache

# 1整数
# n = int(input())

# 空白区切り2変数
from queue import Queue
from operator import mul
from functools import reduce

nCr = {}


def cmb(n, r):
    #print("nCr", n, r)
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n, r) in nCr: return nCr[(n, r)]
    nCr[(n, r)] = cmb(n - 1, r) + cmb(n - 1, r - 1)
    return nCr[(n, r)]


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

value = list(map(int, input().split()))

# 価値の高い順にソート
value = list(reversed(sorted(value)))

# 対象よりも高いものの個数を数える
takai = 0
avg = 0
for i in range(a):
    if value[i] > value[a]:
        takai += 1
    avg += value[i]
# 上からA番目まで選ぶのが最も平均が高い
avg /= a
print(avg)

cc = value.count(value[a])

# 以下組み合わせ
##最も高価なものとA番目のものが同じときa個からb個まで  nCccの組み合わせ数
if value[0] == value[a]:
    sum = 0
    #print(a, b, cc, min(cc, b) + 1,1)
    for i in range(a, min(cc, b) + 1):
        sum += cmb(cc , i)
    print(sum)
else:
    print(cmb(cc, a - takai))

##違うときは a-takai個を (b-takai) or ccの組み合わせ数

Submission status: Accepted

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

V.sort(reverse=True)

mean = sum(V[:A]) / A
mean = float(mean)

print(mean)


def fact(n):
    if n == 0 or n == 1: return 1
    return fact(n-1) * n

def comb(n,a):
    return fact(n)//fact(a)//fact(n-a)

from collections import Counter
c = Counter(V)
n = c[V[0]]


if V[0] != V[A-1]:
    n = c[V[A-1]]
    if n > 1:
        idx = V.index(V[A-1]) 
        _A = A - idx
        print( comb( n, _A ) )
    else:
        print(1); exit()

if V[0] == V[A-1]:
    ans = 0
    for i in range(A, min(n+1, B+1)):
        ans += comb(n, i)

    print( ans )

Submission status: Accepted

Solution code:
from math import factorial as ff
def cc(n,r):
  return ff(n)//ff(n-r)//ff(r)
n,a,b = map(int, input().split())
l = sorted(list(map(int, input().split())), reverse = True)
ans = 0
x = l[:a]
ave = sum(x)/a
m = l.count(x[0-1])
if len(set(x)) == 1:
  for i in range(a,min(b,m)+1):
    ans += cc(m,i)
else:
  p = x.count(x[-1])
  ans = cc(m,p)
print(ave)
print(ans)

Submission status: Accepted

Solution code:
FACT = [1] * 51
for i in range(1, 51):
    FACT[i] = FACT[i-1] * i


def combination(n, r):
    return FACT[n] // FACT[r] // FACT[n-r]


def main():
    N, A, B = map(int, input().split())
    V = list(map(int, input().split()))
    V.sort(reverse=True)
    print(sum(V[:A]) / A)
    x = V[A-1]
    y = V.count(x)
    ans = 0
    begin = V[:A].count(x)
    end = V[:B].count(x)+1
    for i in range(begin, end):
        if i != begin and x != V[0]:
            continue
        ans += combination(y, i)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def conb(a,b):
    now=1
    for i in range(b):
        now=int(now*(a-i)/(i+1))
    return now
N,A,B=map(int,input().split())
V=list(map(int,input().split()))
V.sort(reverse=True)
line=V[A-1]
if V[0]==line:
    ans=0
    for i in range(A,min(V.count(V[0]),B)+1):
        ans+=conb(V.count(V[0]),i)
    print(V[0])
    print(ans)
elif line>V[A]:
    print(sum(V[:A])/A)
    print(1)
else:
    idx=V.index(line)
    cnt=V.count(line)
    print((sum(V[:idx])+line*(A-idx))/A)
    print(conb(cnt,A-idx))

Submission status: Accepted

Solution code:
import numpy

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

v.sort()

res = numpy.average(v[n - a:])
x = min(v[n - a:])

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

if v[n - 1] != x:
    print(res)
    c = v[n-a:].count(x)
    m = v.count(x)
    print(cmb(m, c))
else:
    print(res)
    ans = 0
    m = v.count(x)
    for i in range(a, min(m, b) + 1):
        ans += cmb(m, i)
    print(ans)

Submission status: Accepted

Solution code:
import math
N,A,B = map(int,input().split())
V = list(map(int,input().split()))
V.sort()
V.reverse()
cur = 0
selectlist = []
for i in range(A,B+1):
    S = 0
    for j in range(i):
        S += V[j]
    S = S/i
    if cur < S:
        cur = S
        selectlist = [i]
    elif cur == S:
        selectlist.append(i)
ans = 0
for p in range(len(selectlist)):
    nowselect = 1
    s = 0
    K = []
    for i in range(selectlist[p]):
        K.append(V[i])
    P = list(set(K))
    P.sort()
    P.reverse()
    for j in range(len(P)):
        cnt = V.count(P[j])
        s += cnt
        if s >= selectlist[p]:
            res = K.count(P[j])
            nowselect *= math.factorial(cnt)//(math.factorial(res)*math.factorial(cnt-res))
            ans += nowselect
        else:
            nowselect *= cnt
print(cur)
print(ans)

Submission status: Accepted

Solution code:
n, a ,b = map(int, input().split())
v = list(map(int, input().split()))
d = {}
for i in range(n):
  d.setdefault(v[i], 0)
  d[v[i]] += 1
c = sorted(list(set(v)), reverse=True)
c.append(0)
d[0] = 0
fact = [1 for _ in range(n+1)]
for i in range(n):
  fact[i+1] = fact[i] * (i+1)
ave = 0
cnt = 0
for i in range(a, b+1):
  t = i; cur = 0; sum=0
  while(cur<len(c)-1 and d[c[cur]]<=t):
    sum += c[cur] * d[c[cur]]
    t -= d[c[cur]]
    cur += 1
  sum += c[cur] * t
  if ave < (sum / i):
    ave = sum / i
    cnt = fact[d[c[cur]]] // fact[t] // fact[d[c[cur]]-t]
  elif ave == (sum / i):
    cnt += fact[d[c[cur]]] // fact[t] // fact[d[c[cur]]-t]
print(ave)
print(cnt)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n = I()
ans = int(math.log10(n)+1)
for i in range(2,int(n**0.5)+1):
    if n%i == 0:
        ans = min(ans, max(int(math.log10(i)+1),int(math.log10(n//i)+1)))
print(ans)
"""

#D
n,a,b = LI()
v = LI()
v.sort()
v = v[::-1]
ans = v[:a]
d = {}
d[ans[-1]] = 0
if ans[0] != ans[-1]:
    for i in ans:
        if i == ans[-1]:
            d[i] += 1
    k = d[i]
    d[i] = 0
    for i in v:
        if i == ans[-1]:
            d[i] += 1
    c = 1
    for j in range(min(k,d[ans[-1]]-k)):
        c *= d[ans[-1]]-j
        c //= j+1
else:
    for i in v:
        if i == ans[-1]:
            d[i] += 1
    c = 0
    for k in range(a,min(d[ans[-1]],b)+1):
        p = 1
        for j in range(min(k,d[ans[-1]]-k)):
            p *= d[ans[-1]]-j
            p //= j+1
        c += p
print(sum(ans)/a)
print(c)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
import math
N,A,B=map(int,input().split())
v = input().split()
for i in range(N):
    v[i] = int(v[i])

v.sort(reverse=True)

ans1=0
for i in range(A):
    ans1 += v[i]
ans1 /= A
print(ans1)

p = v[A-1]
q = v.count(p)
r = v.index(p)
ans2=0
if not v[0] == v[A-1]:
    #q P A-r
    ans2 = math.factorial(q) // math.factorial(q+r-A) // math.factorial(A-r)
else: # N==q
    for i in range(A,min(q,B)+1):
        # q P i
        ans2 += math.factorial(q) // math.factorial(q-i) // math.factorial(i)
print(ans2)

Submission status: Accepted

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

v = sorted(v,reverse=True)
max_ave = sum(v[0:a])/a
index_max_ave = -1
for i in range(a,b+1)[::-1]:
  max_ave = max(sum(v[0:i])/(i),max_ave)
  if max_ave == sum(v[0:i])/(i):
    index_max_ave = i

print(max_ave)

def combination(n,r):
    r = min(r,n-r)
    result = 1
    for i in range(n-r+1,n+1):
        result *= i
    for i in range(1,r+1):
        result //= i
    return result


num = v[index_max_ave-1]
for i in range(index_max_ave):
  if num != v[i]:
    print(combination(v[0:index_max_ave].count(num)+v[index_max_ave:n].count(num),v[0:index_max_ave].count(num)))
    exit()

cnt = v.count(num)
ans = 0
for i in range(a,min(b+1,cnt+1)):
  ans += combination(cnt,i)
print(ans)

Submission status: Accepted

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

def fac(n):
  if n<= 1: return 1
  return n*fac(n-1)
def c (a,b): 
  if b==0: return 1
  return fac(a)//fac(b)//fac(a-b)


print(sum(V[:A])/A)

if V.count(V[0]) >= A:
  ans=0
  for i in range(A, min(B+1,V.count(V[0])+1)):
    ans+=c(V.count(V[0]),i)
else:
  ans=c(V.count(V[A-1]), V[:A].count(V[A-1]))
print(ans)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
v=list(map(int,input().split()))
v.sort()
def f(x,y):
    c=1
    d=1
    for i in range(x):
        c*=(i+1)
        d*=(y-i)
    return d//c
p=v[n-a:]
g=sum(p)/a
print(sum(p)/a)
w=0
for i in range(a,b+1):
    p=v[n-i:]
    h=sum(p)/i
    if h<g:
        break
    else:
        q=p[0]
        d=v.count(q)
        e=p.count(q)
        w+=f(e,d)
print(w)

Submission status: Accepted

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

cc = [[0 for _ in range(51)] for _ in range(51)]
for i in range(51):
  for j in range(i+1):
    if j == 0 or j == i:
      cc[i][j] = 1
    else:
      cc[i][j] = cc[i-1][j-1] + cc[i-1][j]

avg = sum(vlist[:a]) / a
avaln, avalp = 0, 0
for i in range(n):
  if vlist[i] == vlist[a-1]:
    avaln += 1
    if i < a:
      avalp += 1

cnt = 0
if avalp == a:
  for ap in range(a, b+1):
    cnt += cc[avaln][ap]
else:
  cnt += cc[avaln][avalp]

print('%.8f' % avg)
print(cnt)

Submission status: Accepted

Solution code:
import bisect
from math import factorial
def comb_cnt(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

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

maxsum = sum(vs[-a:])
val = vs[-a]
l, r = bisect.bisect_left(vs, val), bisect.bisect_right(vs, val)
nmin, nmax = r - (n - a), r - max(l, n - b)
if r != n:
    ans = comb_cnt(r - l, nmin)
else:
    ans = 0
    for i in range(nmin, nmax + 1):
        ans += comb_cnt(r - l, i)

print(maxsum / a)
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections

def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result



def main():
    N, A, B = [int(_) for _ in sys.stdin.readline().split()]
    V = sorted([int(_) for _ in sys.stdin.readline().split()], reverse=True)
    D = collections.defaultdict(lambda: 0)
    ans = 0

    for v in V:
        D[v] += 1

    for C in range(A, B+1):
        if (sum(V[:C]) / C) == (sum(V[:A]) / A):
            ans += comb(D[V[C-1]], V[:C].count(V[C-1]))

    print((sum(V[:A]) / A))
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    N, A, B = [int(_) for _ in sys.stdin.readline().split()]
    V = sorted([int(_) for _ in sys.stdin.readline().split()], reverse=True)
    D = collections.defaultdict(lambda: 0)
    ans = 0

    for v in V:
        D[v] += 1

    for C in range(A, B+1):
        if (sum(V[:C]) / C) == (sum(V[:A]) / A):
            ans += comb(D[V[C-1]], V[:C].count(V[C-1]))

    print((sum(V[:A]) / A))
    print(ans)

main()