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:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser


def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N,A,B = map(int, input().split())
    vs = list(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    vs.sort(reverse=True)
    cs=Counter(vs)
    tot=0
    cnt=0
    pr=-1

    
    for i in range(A):
        cur=vs[i]
        tot+=cur
        if cur!=pr:
            cnt=1
        else:
            cnt+=1
        pr=cur
    ave=tot/A
    print(ave)

    

    
        #float計算用のcombination, 最後にexpを取るのを忘れない、積は和でとること
    maxn=N
    
    lfact=[1]*(maxn+1)#NはnCrの最大のn
    for i in range(1,maxn+1):
        lfact[i]=lfact[i-1]*i
    def lcomb(n,r): return lfact[n]//lfact[n-r]//lfact[r]

    tc=cs[cur]
    if cnt==A:
        ans=0
        for cnt in range(A,B+1):
            ans+=(lcomb(tc,cnt))
    else:
        ans=(lcomb(tc,cnt))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


def comb(n, k):
    if k > n:
        return 0
    x = 1
    for j in range(n - k + 1, n + 1):
        x = x * j
    for l in range(1, k + 1):
        x = x // l
    return x

n, a, b = LI()
V = LI()
V.sort(reverse=True)
s = V[a - 1]
cnt1 = V.count(s)
cnt2 = V[:a].count(s)
print(sum(V[:a]) / a)
if cnt2 != a:
    print(comb(cnt1, cnt2))
    exit()
ret = 0
for i in range(a, b + 1):
    ret += comb(cnt1, i)
    cnt2 += 1

print(ret)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
from collections import defaultdict
from operator import mul
from functools import reduce
def input(): return sys.stdin.readline().strip()

def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

    num_kind = defaultdict(int)
    same_kind = [1] * N
    pre = V[0]
    num_kind[V[0]] += 1
    for i in range(1, N):
        num_kind[V[i]] += 1
        if pre == V[i]:
            same_kind[i] = same_kind[i - 1] + 1
        pre = V[i]

    S = [0] + list(accumulate(V))
    average = defaultdict(int)
    max_val = 0
    for i in range(A, B + 1):
        val = S[i] / i
        if val >= max_val:
            max_val = val
            n, r = num_kind[V[i - 1]], same_kind[i - 1]
            average[max_val] += comb(n, r)
    print(max_val)
    print(average[max_val])



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import factorial
n, a, b = map(int, input().split())
V = sorted(map(int, input().split()), reverse=True)

av = sum(V[:a]) / a
print(av)

def comb(m, k):
    ans = 1
    if k == 0:
        return 1
    else:
        for i in range(k):
            ans *= m - i
            ans //= i + 1
        return ans

num = V[a]
m = V.count(num)
k = V[:a].count(num)
#print(m, k, a)
if a != k:
    ans = factorial(m) // (factorial(k) * factorial(m - k))
else:
    #mCi(i:　a=>b)
    ans = 0
    for k in range(a, b+1):
        ans += comb(m, k)
print(ans)

Submission status: Accepted

Solution code:
from scipy.special import comb
ans=0
N,A,B=map(int,input().split())
L=list(map(int,input().split()))
#Aこの平均でよい
L=sorted(L,reverse=True)
if len(set(L))==1:
  print(L[0])
  for i in range(A,B+1):
    ans+= comb(N, i, exact=True)
  print(ans)
  exit()
print(sum(L[:A])/A)
R=list(L[:A])
c=L[A-1]
if len(set(R))==1:
  n=L.count(c)
  for i in range(A,min(n,B)+1):
    ans+= comb(n, i, exact=True)
  print(ans)
  exit()
a=L.count(c)
b=R.count(c)
print(comb(a,b,exact=True))

Submission status: Accepted

Solution code:
from collections import Counter
from math import prod

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

factorial=[1 for i in range(N+1)]
for i in range(1,N+1):
    if i==1:factorial[i]=1
    else:factorial[i] = factorial[i-1]*i

def comb(n,k):
    return factorial[n]*pow(factorial[n-k]*factorial[k], -1)
  
v = sorted(v,reverse=True)
  
if len(set(v[:A]))==1:
  print(v[0])
  ans=0
  for i in range(A,B+1):
    if i > 1 and v[i-1] != v[i-2]:break
    ans += comb(Counter(v)[v[0]],i)
  print(int(ans))
  exit()

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

c = Counter(v)
thr = v[A-1]

if c[thr] == 1 or v[A-1] != v[A]:
  res=[]
  for k in c.keys():
    if k >= thr:
      res.append(c[k])
    
  print(prod(res))
  exit()
  
res=[]
for k in c.keys():
  if k > thr:
    res.append(c[k])

ans=prod(res)

idx = v[:A].index(v[A-1])-1

print(int(ans*comb(c[v[A-1]],A-1-idx)))

Submission status: Accepted

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

n, a, b = map(int, input().split())
vs = list(map(int, input().split()))
vs.sort(reverse=True)
rsw = [0]*(n+1)
for i in range(1,n+1):
    rsw[i] = sum(vs[:i])/i
#print(vs)
#print(rsw)
res = -float('inf')
for i in range(a,b+1):
    res = max(res,rsw[i])
print(res)
mut = []
res_lists = []
for i in range(1,b+1):
    if i < a:
        mut.append(vs[i-1])
    elif i == a:
        res_lists.append(mut.copy()+[vs[i-1]])
    else:
        if rsw[i] < res:
            break
        res_lists.append(res_lists[-1].copy() + [vs[i - 1]])
#print(res_lists)
res = 0
for lis in res_lists:
    x = lis[-1]
    r = lis.count(x)
    N = 0
    for i in range(n):
        if vs[i] == x:
            N += 1
    res += combinations_count(N,r)
print(res)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,A,B = MI()
v = LI()
v.sort(reverse=True)

print(sum(v[0:A])/A)

kaijou = [1]
for i in range(1,N+1):
    kaijou.append(kaijou[-1]*i)

def nCr(n,r):
    if n < r:
        return 0
    else:
        return (kaijou[n]//kaijou[r])//kaijou[n-r]

if v[0] != v[A-1]:
    a,b = 0,0  # v[A-1] より大きい元の個数、v[A-1] と等しい元の個数
    for i in range(N):
        if v[i] > v[A-1]:
            a += 1
        elif v[i] == v[A-1]:
            b += 1
    print(nCr(b,A-a))
else:
    a = v.count(v[A-1])
    print(sum(nCr(a,i) for i in range(A,B+1)))

Submission status: Accepted

Solution code:
import itertools, bisect
from fractions import Fraction
from math import factorial


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


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

Ave = [Fraction(a, i) for i, a in enumerate(itertools.accumulate(V), 1)]
max_num = max(Ave[A - 1:B])
max_indices = [i for i, v in enumerate(Ave) if A <= i + 1 <= B and v == max_num]

Vm = [-v for v in V]
C = 0
for ind in max_indices:
    l = bisect.bisect_left(Vm, Vm[ind])
    r = bisect.bisect_right(Vm, Vm[ind])
    C += comb(r - l, ind - l + 1)
print(float(max_num))
print(C)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

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

def sub(x):
    """x個の最大値・個数
    """
    val = (sum(v[-x:]), x)
    tmp = v[-x]
    n0 = 0
    n1 = 0
    for i in range(n-x, n):
        if v[-x]==v[i]:
            n1 += 1
        else:
            break
    for i in range(n-x-1, -1, -1):
        if v[-x]==v[i]:
            n0 += 1
        else:
            break
    # cmb(n0+n1, n1)
    num = 1
    for i in range(1,n1+n0+1):
        num *= i
    for i in range(1, n1+1):
        num //= i
    for i in range(1, n0+1):
        num //= i
    return val, num
ans = None
for x in range(a, b+1):
    val, num = sub(x)
    if ans is None:
        ans = (val, num)
    else:
        if ans[0][0]*val[1]==ans[0][1]*val[0]: # 0/1
            ans = (ans[0], num+ans[1])
        elif ans[0][0]*val[1]<ans[0][1]*val[0]:
            ans = (val, num)
ans = (ans[0][0]/ans[0][1], ans[1])
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:

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

v = sorted(v)[::-1]

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

i = A
## n = 1
n_min = A
n_max = B
while (i<B):
    ## v_new = (i*v_ref + v[i]) / (i+1)
    v_new = v_ref + v[i]
    ## if v_new < v_ref:
    if i*v_new < (i+1)*v_ref:
        n_max = i
        break
    ## if v_new > v_ref:
    if i*v_new > (i+1)*v_ref:
        n_min = i+1
    v_ref = v_new
    i+=1

def comb(n, k):
    r = 1
    for x,y in zip(range(n,n-k,-1), range(1,k+1)):
        r = r * x
        assert r % y == 0
        r = r // y
    return r

result = 0
for n in range(n_min, n_max+1):
    v_min = min(v[:n])
    num_min = sum([v_ == v_min for v_ in v])
    num_fixed = sum([v_ > v_min for v_ in v[:n]])
    num_selected = n - num_fixed
    result += comb(num_min, num_selected)

v_max_avg = sum(v[:n_min]) / n_min

print(f"{v_max_avg:.6f}")
print(result)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, A, B = getNM()
V = sorted(getList(), reverse = True)

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

dict = defaultdict(int)
for i in range(N):
    dict[V[i]] += 1

r = A
n = 0
for i in dict.items():
    if r - i[1] >= 0:
        r -= i[1]
    else:
        n = i[1]
        break

def cmb_1(n, r):
    r = min(n - r, r)
    if (r < 0) or (n < r):
        return 0
        
    if n == 0:
        return 1

    if r == 0:
        return 1

    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

ans = 0
if r > 0 and V[0] == V[A - 1]:
    for i in range(r, B + 1):
        ans += cmb_1(n, i)
else:
    ans += cmb_1(n, r)

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from decimal import Decimal
from scipy.special import comb
n, a, b = map(int, input().split())
v = list(map(lambda x:-int(x), input().split()))
v.sort()
li = [[None]*2 for _ in range(n+1)]
for k in range(a, b+1):
    li[k][0] = -sum(v[:k])
    li[k][1] = comb(bisect_right(v, v[k-1])-bisect_left(v, v[k-1]), k-bisect_left(v, v[k-1]), exact=True)
ans = [Decimal(0), 0]
for i in range(n+1):
    if li[i][0] is None:
        continue
    tmp = Decimal(li[i][0]) / Decimal(i)
    if ans[0]==tmp:
        ans[1] += li[i][1]
    elif ans[0]<tmp:
        ans[0] = tmp
        ans[1] = li[i][1]
print(ans[0])
print(ans[1])

Submission status: Accepted

Solution code:
def main():
    N,A,B=map(int,input().split())
    v=list(map(int,input().split()))
    v.sort(reverse=True)
    Amxv=sum(v[:A])
    c=v[A-1]
    m=v[:A].count(c) 
    n=v.count(c)
    fl=[1]*(N+1)
    for i in range(N):
        fl[i+1]=fl[i]*(i+1)
    print(Amxv/A)
    if v[0]-c==0:
        print(sum([fl[n]//(fl[i]*fl[n-i]) for i in range(A,min(B,n)+1)]))
    else:
        print(fl[n]//(fl[m]*fl[n-m]))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, A, B = mapint()
Vs = list(mapint())
Vs.sort(reverse=True)
from collections import defaultdict, Counter
from math import factorial, gcd

count = defaultdict(int)
c = Counter(Vs)
ans = 0
ans_2 = (0, 0)
for i in range(A, B+1):
    val = sum(Vs[:i])
    if val/i>=ans-0.000000000000001:
        ans = val/i
        lowest_cnt = 0
        lowest = Vs[i-1]
        for j in range(i):
            if Vs[j]==lowest:
                lowest_cnt += 1
        val, i = val//gcd(val, i), i//gcd(val, i)
        count[(val, i)] += factorial(c[lowest])/factorial(lowest_cnt)/factorial(c[lowest]-lowest_cnt)
        ans_2 = (val, i)

print(ans)
print(round(count[ans_2]))

Submission status: Accepted

Solution code:
memo = {}
def f(m,k):
    if k>m:
        return 0
    if m==1:
        return 1
    if k==0:
        return 1
    if k==1:
        return m
    if (m,k) in memo:
        return memo[(m,k)]
    memo[(m,k)]=f(m-1,k-1)+f(m-1,k)
    return memo[(m,k)]

N,A,B = map(int,input().split())
V = sorted(list(map(int,input().split())),reverse=True)
amin = 10**15+10
for i in range(A):
    amin = min(amin,V[i])
av = sum(V[:A])/A
cnt = 0
for i in range(N):
    if V[i]==amin:
        cnt += 1
cntB = 0
for i in range(B):
    if V[i]==amin:
        cntB += 1
cntA = 0
for i in range(A):
    if V[i]==amin:
        cntA += 1
print(av)
if V[0]>amin:
    print(f(cnt,cntA))
else:
    tot = 0
    for i in range(cntA,cntB+1):
        tot += f(cnt,i)
    print(tot)

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

#mo=10**9+7
mo=2305843009213693951
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################
class Comb:
    def __init__(self,n,mo=2305843009213693951):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo


show_flg=False
show_flg=True

ans=0


F=[1]
for i in range(110):F+=F[i]*-~i,
C=lambda A,B:(A>=B>=0)*F[A]//F[A-B]//F[B]
    

n,a,b=LI()
v=LI()
v=sorted(v)[::-1]
print(sum(v[:a])/a)
m=v[a-1]
x=v[:a].count(m)
y=v[a:].count(m)
ans=1
if x!=a:
    ans=C(x+y,x)
    print(ans)
else:
    ans=0
    for i in range(a,min(b,x+y)+1):
        ans+=C(x+y,i)
    print(ans)

Submission status: Accepted

Solution code:
def bikkuri(x):
  if x <= 0:
    return 1
  temp = 1
  for i in range(1,x+1):
    temp *= i
  return temp

def ncr(n,r):
  return bikkuri(n)//(bikkuri(r)*bikkuri(n-r))
  
#print(bikkuri(3))
#print(ncr(5,3))
from collections import defaultdict
dic = defaultdict(int)
N,A,B = map(int,input().split())
v = list(map(int,input().split()))
MAX = max(v)
for x in v:
  dic[x] += 1
ans = 0
w = sorted(v, reverse=True)
Maxv = [] #(sum,i個)を保存
for i in range(A,B+1): #A-Bまで
  #print(Maxv)
  dic2 = defaultdict(int)
  SUM = 0
  for j in range(i):
    dic2[w[j]] += 1
    SUM += w[j]
  L = list(dic2.keys())
  if len(Maxv) == 0 or Maxv[0][0]*i == SUM*Maxv[0][1]:
    Maxv.append((SUM,i))
    temp = 1
    nokori = i*1
    for x in L:
      if dic[x] >= nokori:
        temp *= ncr(dic[x],nokori)
        #print(dic[x],nokori,ncr(dic[x],nokori))
      elif dic[x] == dic2[x]:
        nokori -= dic[x]
      if nokori == 0:
        break
        
    ans += temp
  elif Maxv[0][0]*i < SUM*Maxv[0][1]:
    ans = 0
    Maxv = [(SUM,i)]
    temp = 1
    for x in L:
      if dic[x] != dic2[x]:
        temp *= ncr(dic[x],dic2[x])
        #print(temp,x,dic[x],dic2[x])
    ans += temp
#print(Maxv)
print(Maxv[0][0]/Maxv[0][1])
print(ans)

Submission status: Accepted

Solution code:
import itertools,collections
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def main():
    n,a,b=map(int, input().split())
    v=[int(i) for i in input().split()]
    v.sort(reverse = True)
    tmp = v[0:a]
    dd = collections.defaultdict(int)

    for i in v:
        dd[i]+=1

    cnt = 0
  
    k = 0
    for i in tmp:
        k+=i
    s = min(tmp)
    avg = k/len(tmp)
    if(tmp[0]!=s):
        howmany = v.count(s)
        nantoori = tmp.count(s)
        #howmany個からnantoori個選ぶ方法
        res = howmany

        for i in range(nantoori-1):
            res *= (howmany-i+1)
        res2 = 1
        for i in range(nantoori):
            res2 *= (i+1)
        print(avg)
        print(combinations_count(howmany,nantoori))
    else:
        howmany = dd[s]
        res=0
        for i in range(a,min(b+1,howmany+1)):
            res += combinations_count(howmany, i)


        print(avg)
        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)
a=v[:A]
b=v[:B]
avg=sum(a)/A
print(avg)
c=[[0]*51 for _ in range(51)]
c[0][0]=1
for i in range(50):
  c[i+1][0]=1
  c[i+1][i+1]=1
  for j in range(i):
    c[i+1][j+1]=c[i][j]+c[i][j+1]
if a[0]==a[-1]:
  ans=0
  x=v.count(a[0])
  for i in range(A,B+1):
    if i<=x:
      ans+=c[x][i]
else:
  x=v.count(a[-1])
  y=a.count(a[-1])
  ans=c[x][y]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from math import factorial

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

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

V_C=Counter(V)

max_val=max(V)
CC=V_C[max_val]
if A<=CC:
    ans=0
    for v in range(A,min(B,CC)+1):
        ans+=comb(CC,v)
    print(max_val)
    print(ans)
    exit()

tmp_sum=0
tmp_num=0

for key in sorted(V_C.keys(),reverse=True):
    val = V_C[key]
    #追加しても大丈夫なら加える(加えないとAに行かないから加えないといけない)
    #ぎりAに届くように追加するのが良い
    if A<=tmp_num+val:
        rest=A-tmp_num

        tmp_num+=rest
        tmp_sum+=key*rest
        print(tmp_sum/tmp_num)
        print(comb(val,rest))
        exit()
    else:
        tmp_num+=val
        tmp_sum+=key*val

Submission status: Accepted

Solution code:
from collections import Counter
from math import factorial

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

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

V_C=Counter(V)

max_val=max(V)
CC=V_C[max_val]
if A<=CC:
    ans=0
    for v in range(A,min(B,CC)+1):
        ans+=comb(CC,v)
    print(max_val)
    print(ans)
    exit()

tmp_sum=0
tmp_num=0

for key in sorted(V_C.keys(),reverse=True):
    val = V_C[key]
    assert tmp_num<A
    #追加しても大丈夫なら加える(加えないとAに行かないから加えないといけない)
    #ぎりAに届くように追加するのが良い
    if A<=tmp_num+val:
        rest=A-tmp_num

        tmp_num+=rest
        tmp_sum+=key*rest
        assert tmp_num==A
        assert rest<=val
        assert rest!=0
        print(tmp_sum/tmp_num)
        print(comb(val,rest))
        exit()
    else:
        tmp_num+=val
        tmp_sum+=key*val
        assert tmp_num<A

assert 1==2

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

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

# 大きいほうからA個選んだときの平均値が求める平均値
# 大きいほうからA位の数字をPとすると、
# ・A位までの数字がすべてPのとき：Pの個数から、A～B個選ぶ場合の数
# ・そうでないとき：Pの個数から、A位までに必要なPの個数を選ぶ場合の数

V = sorted(V, reverse = True)

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

from scipy.special import comb

P = V[A - 1]
pcnt = V.count(P)

if V[0] == P:
  ans = 0
  for i in range(A, B + 1):
    ans += comb(pcnt, i, exact = True)
  print(ans)
else:
  pneed = (V[:A]).count(P)
  print(comb(pcnt, pneed, exact = True))

Submission status: Accepted

Solution code:
import math 

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

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

vl.sort(reverse=True)
if vl[0] == vl[a-1]:
    v = vl[0]
    print(v)
    v_cnt = vl.count(v)
    max_r = min(v_cnt,b)
    ans = 0
    for r in range(a,max_r+1):
        ans += com(v_cnt,r)
    print(ans)

else:
    print(sum(vl[:a])/a)
    last_val = vl[a-1]
    last_val_cnt = vl[0:a].count(last_val)
    all_last_val_cnt = vl.count(last_val)
    print(com(all_last_val_cnt,last_val_cnt))

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
V=list(map(int,input().split()))
V.sort(reverse=True)
A=V[:a]
B=V[:b]
ave=sum(A)/a
print(ave)
C=[[0]*51 for _ in range(51)]
C[0][0]=1
for i in range(50):
    C[i+1][0]=1
    C[i+1][i+1]=1
    for j in range(i):
        C[i+1][j+1]=C[i][j]+C[i][j+1]
if A[0]==A[-1]:
    ans=0
    x=V.count(A[0])
    for i in range(a,b+1):
        if i<=x:
        	ans+=C[x][i]
else:
    x=V.count(A[-1])
    y=A.count(A[-1])
    ans=C[x][y]
print(ans)

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split())
V=sorted(list(map(int,input().split())),reverse=True)
D=dict()
for i in range(N):
  D[V[i]]=D.get(V[i],0)+1
X=[1]
for i in range(1,51):
  X.append(X[-1]*i)
def cmb(n,r):
  return X[n]//(X[r]*X[n-r])

P=0
if V[0]==V[A-1]:
  for i in range(A,B+1):
    if i>D[V[0]]:
      break
    P+=cmb(D[V[0]],i)
else:
  Q=0
  for i in range(A-1,-1,-1):
    if V[i]!=V[A-1]:
      break
    Q+=1
  P=cmb(D[V[A-1]],Q)
print(sum(V[:A])/A)
print(P)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
v=list(map(int,input().split()))
fact=[1]
for i in range(1,51):
    fact.append(i*fact[-1])
def cmb(n,r):
    return fact[n]//(fact[n-r]*fact[r])
v.sort(reverse=True)
print(sum(v[:a])/a)
cntv,cntr=0,0
for i in range(n):
    if i<a:
        if v[i]==v[a-1]:
            cntv+=1
    else:
        if v[i]==v[a-1]:
            cntr+=1
#print(cntv,cntr)
if cntv<a:
    print(cmb(cntv+cntr,cntv))
else:
    ans=0
    for r in range(a,min(b,cntv+cntr)+1):
        ans+=cmb(cntv+cntr,r)
        #print(ans)
    print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def combdp():
    n = 50
    comb = [[0] * (n + 1) for _ in range(n + 1)]
    comb[0][0] = 1

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

    return comb


def main():
    n, a, b = map(int, readline().split())
    v = list(map(int, readline().split()))
    v.sort()
    v.reverse()

    comb = combdp()
    val = [0] * (n + 1)
    cnt = [0] * (n + 1)

    for i in range(a, b + 1):
        val[i] = sum(v[:i])
        mn = min(v[:i])
        c1 = v.count(mn)
        ct = 0
        for j in range(n):
            if v[j] > mn:
                ct += 1
        c2 = i - ct
        cnt[i] = comb[c1][c2]

    ans_val = 0
    ans_cnt = 0

    for i in range(a, b + 1):
        for j in range(a, b + 1):
            x = val[i] * j
            y = val[j] * i
            if x >= y:
                pass
            else:
                break
        else:
            ans_val = val[i] / i
            ans_cnt += cnt[i]

    print(ans_val)
    print(ans_cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from decimal import Decimal as de
l=sorted(list(map(int,input().split())),reverse=1)
fact=[1]
for i in range(1,51):
    fact.append(fact[-1]*i)
from collections import Counter as co
if l[0]==l[a-1]:
    def comb(x,y):
        return fact[x]//(fact[y]*fact[x-y]) if x>=y>=0 else 0
    x=co(l)[l[0]]
    print(l[0])
    print(sum(comb(x,i)for i in range(a,b+1)));exit()
ave=de(str(sum(l[:a])))/a
print(ave)

y=co(l[:a])[l[a-1]]
x=co(l)[l[a-1]]
print(fact[x]//(fact[y]*fact[x-y]))