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:
from functools import reduce

def binom(n, r):
    if n < r or n < 0 or r < 0: return 0
    
    if n - r < r: r = n - r
    if r == 0: return 1
    elif r == 1: return n

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

    # reduce prod(numerator)//prod(denominator)
    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
    
    # calculate nCr
    return reduce(lambda x, y: x*y, numerator)


N, A, B = map(int, input().split())
*V, = map(int, input().split())
V = sorted(V, reverse=True)
ans = 0
ways = 0
if len(set(V[:A])) == 1:
    ans = V[0]
    n = V.count(ans)
    for i in range(A, min(B, n)+1): ways += binom(n, i)
else:
    ans = sum(V[:A]) / A
    min_num = min(V[:A])
    n_min = V.count(min_num)
    n_min_lst = V[:A].count(min_num)
    ways = binom(n_min, n_min_lst)
print(ans)
print(ways)

Submission status: Accepted

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

C = [[1 for k in range(n + 1)] for n in range(N + 1)]
for n in range(2, N + 1):
    for k in range(1, n):
        C[n][k] = C[n - 1][k] + C[n - 1][k - 1]

x = v[A - 1]
l = 0
while v[l] != x:
    l += 1
r = l + 1
while r < N and v[r] == x:
    r += 1


count = 0
for i in range(A, min(B, r) + 1):
    if sum(v[:A]) * i == sum(v[:i]) * A:
        count += C[r - l][i - l]
print(sum(v[:A]) / A)
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: int, B: int, v: "List[int]"):
    def choose(n, k):
        ret = 1
        k = min(k, n - k)
        for i in range(1, k + 1):
            ret *= (n - i + 1)
            ret //= i
        return ret

    count = {}
    v.sort(reverse=True)
    ave = [0] * N
    for val in v:
        if val in count:
            count[val] += 1
        else:
            count[val]  = 1
    for i in range(A - 1, B):
        ave[i] = sum(v[:i + 1]) / (i + 1)
    mx = max(ave)

    ret = 0
    for i in range(A - 1, B):
        if ave[i] == mx:
            c = 0
            for j in range(i + 1, N):
                if v[j] == v[i]:
                    c += 1
            ret += choose(count[v[i]], c)
    print(mx)
    print(ret)
    return


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:
def main():
	N, A, B = map(int, input().split())
	v = list(map(int, input().split()))
	v.sort(reverse=True)
	ave_ans = sum(v[:A])/A
	cmp_v = v[A-1]
	cmp_v_in = 0
	cmp_v_out = 0
	def get_total(values):
		ans = 0
		for v in values:
			if v == cmp_v:
				ans += 1
		return ans
	cmp_v_in = get_total(v[:A])
	cmp_v_out = get_total(v[A:])
	fact = [0]*51
	fact[0] = 1
	fact[1] = 1
	for i in range(2, 51):
		fact[i] = fact[i-1]*i

	def C(n, k):
		return fact[n]//(fact[k]*fact[n-k])

	print(ave_ans)

	choose_ans = C(cmp_v_in+cmp_v_out, cmp_v_in)
	if cmp_v_in == A:
		for i in range(1, min(B-A+1, cmp_v_out+1)):
			choose_ans += C(cmp_v_in+cmp_v_out, cmp_v_in+i)
	print(choose_ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def Combination(n, k):
    return fact[n] // fact[k] // fact[n-k]

N, A, B = map(int, input().split())
v = sorted(list(map(int, input().split())))[::-1]
MAX = sum(v[:A])
print(MAX/A)
M = max(v[:A])
m = min(v[:A])
if M != m:
    c1, c2 = v[:A].count(m), v.count(m)
    print(Combination(c2, c1))
else:
    c = v.count(m)
    L = min(B, c)
    ans = 0
    for i in range(A, L+1):
        ans += Combination(c, i)
    print(ans)

Submission status: Accepted

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

n,a,b = map(int,input().split())
l = sorted(list(map(int,input().split())),reverse = True)
n_max = l.count(max(l))
ans=0
if n_max>a:
    for i in range(a,min(b+1,n_max+1)):
        ans+=combi(n_max,i)
    print(max(l))
    print(ans)
    exit()
n_min = l.count(l[a-1])
i_min = l.index(l[a-1])
k = a-i_min
ans+=combi(n_min,k)
print(sum(l[:a])/a)
print(ans)

Submission status: Accepted

Solution code:
from scipy.misc import comb
N,A,B = map(int,input().split())
v = list(map(int,input().split()))
v.sort(reverse=True)

ans = 0
if v[A-1] == v[0]:
    mean = v[0]
    count = 0
    for i in range(N):
        if v[i] == v[0]:
            count += 1
    for i in range(A,min(B,count)+1):
        ans += comb(count,i,exact=True)
else:
    mean = sum(v[:A])/A
    count = 0
    j = N
    for i in range(N):
        if v[i] == v[A-1]:
            j = min(i,j)
            count += 1
    ans = comb(count,A-j,exact=True)
print(mean)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from math import factorial
N, A, B = map(int, input().split())
V = sorted(list(map(int, input().split())), reverse=True)

MAX_AVE = sum(V[:A]) / A
C = Counter(V)


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


Ath_V = V[A - 1]
if Ath_V == max(V):
    ans = 0
    for r in range(A, min(B + 1, C[Ath_V] + 1)):
        ans += nCr(C[Ath_V], r)
    print(MAX_AVE)
    print(ans)

else:
    print(MAX_AVE)
    for i, v in enumerate(V):
        if v == Ath_V:
            used = i
            break
    print(nCr(C[Ath_V], A - used))

Submission status: Accepted

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

n,a,b=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
cnt=[0]*50
num=[arr[0]]
tmp=arr[0]
pos=0
for i in arr:
  if i==tmp:
    cnt[pos]+=1
  else:
    pos+=1
    cnt[pos]+=1
    tmp=i
    num.append(i)
ave=0
ans=0
if cnt[0]>=a:
  ave=num[0]
  for i in range(a,min(b,cnt[0])+1):
    ans+=comb(cnt[0],i)
else:
  t=0
  pos=0
  for i in range(n):
    t+=cnt[i]
    ave+=num[i]*cnt[i]
    if t>=a:
      ave-=num[i]*(t-a)
      ans=comb(cnt[i],a-(t-cnt[i]))
      break
  ave=ave/a
print(ave)
print(ans)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np
from scipy.misc import comb

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

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

V.sort(reverse=True)
V = np.array(V)
cs = V.cumsum()
averages = cs / (np.arange(N) + 1)

# 最大の平均
max_average = averages[A - 1:B].max()
# 選ぶべき数
count = averages[A - 1:B].argmax() + A

# しきい値になってるのが何個あるか
threshold = V[count - 1]
threshold_cnt = (V == threshold).sum()

print(float(max_average))
if np.all(V[:count] == V[0]):
    # しきい値 t 個のとき、tCa + tC(a+1) + ... + tCb
    ans = 0
    for r in range(A, B + 1):
        ans += comb(threshold_cnt, r, exact=True)
    print(ans)
else:
    gt_cnt = (V > threshold).sum()
    print(comb(threshold_cnt, count - gt_cnt, exact=True))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

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

# 方針
# 大きい順から選ぶと平均は最大値を取れる
# 選んだ数字の最初と最後が違う場合、A個選んだ場合のみ平均が最大値になる
# よって最後の数の選び方が何通りあるかを求めればよい
# 最初と最後が同じ場合、選んだ数の種類は全て同じ
# よってその数を選ぶ方法は何通りあるかを求める

def main():
  n,a,b=LI()
  l=LI()

  l=sorted(l,key=lambda x:x,reverse=True)

  l2=l[:a]
  print(sum(l2)/len(l2))
  
  if l2[0]!=l2[-1]:
    c=l.count(l2[-1])
    c2=l2.count(l2[-1])
    print(nCr(c,c2))

  else:
    c=l.count(l2[-1])
    sm=0
    for i in range(a,min(b+1,c+1)):
      sm+=nCr(c,i)

    print(sm)

main()

Submission status: Accepted

Solution code:
from sys import stdin

def combination_table(N):
	C = []
	for i in range(N+1):
		C.append([0] * (N+1))
	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]
	return C

if __name__ == "__main__":
	N, A, B = stdin.readline().split(" ")
	N = int(N)
	A = int(A)
	B = int(B)
	V = []
	line = stdin.readline().split(" ")
	unique_elements = dict()
	for e in line:
		V.append(int(e)) 
		if not int(e) in unique_elements:
			unique_elements[int(e)] = 1
		else:
			unique_elements[int(e)] += 1
	V.sort(reverse=True)

	C = combination_table(N)

	# find optimal selections between A and B
	a_th_val_pos = 0
	a_th_val_num = 0
	highest_avg = float(sum(V[:A])) / float(A)
	for i in range(N):
		if V[i] == V[A-1]:
			a_th_val_num += 1
			if i < A:
				a_th_val_pos += 1


	cnt = 0
	if a_th_val_pos == A:
		for i in range(A, B+1):
			cnt += C[a_th_val_num][i]
	else:
		cnt += C[a_th_val_num][a_th_val_pos]

	print ("{:6f}".format(highest_avg))
	print (cnt)

Submission status: Accepted

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

# n,a,b=3,2,2
# v=[2,2,2]

v.sort(reverse=True)
am=0
for i in v[:a]:
    am+=i
maxv=am/a
B=v[a-1]
count=0
k=0
if v[0]==B:
    flag=0
else:
    flag=1

if flag==0:
    for i in range(n):
        if v[i]==B:
            k=i+1
            break
    k1=k
    while  k1<n+1 and v[k1-1]==B:
        count+=1
        k1+=1

    def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    i=a-k+1 #Bを含める数
    ans=0
    while i<b-k+2 and i<count+1:
        ans+=combinations_count(count,i)
        i+=1


    print(maxv)
    print(ans)

else:
    for i in range(n):
        if v[i]==B:
            k=i+1
            break
    k1=k
    while  k1<n+1 and v[k1-1]==B:
        count+=1
        k1+=1

    def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    i=a-k+1 #Bを含める数
    ans=combinations_count(count,i)
    print(maxv)
    print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W
 
# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

def C(n,r):
    f = math.factorial
    return int(f(n) // f(r) // f(n-r))

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

sort_v = sorted(v, reverse=True)
ans_1 = sum(sort_v[:A])/A
print(ans_1)

max_v = sort_v[A-1]
max_v_count = sort_v.count(max_v)
max_v_count_in_ans = sort_v[:A].count(max_v)

if max_v != sort_v[0]: # 1つでも増やすと平均が減少する場合
    ans = C(max_v_count, max_v_count_in_ans)
else:
    ans = 0
    for i in range(A, min(B, max_v_count) + 1):
        ans += C(max_v_count, i)

print(int(ans))

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict
from operator import itemgetter, attrgetter
inf=float('inf')
mod = 10 ** 9 + 7
def combination(n, r):  # n個からr個選ぶ場合の数
    if n < r:
        return 0
    else:
        return factorial(n)//(factorial(r) * factorial(n-r))


def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, A, B = MI()
    V = LI()
    v_dict = defaultdict(int)
    for v in V:
        v_dict[v] += 1
    VN = [(v, num) for v, num in v_dict.items()]
    VN.sort(reverse=True)
    A_copy = A
    ans_1 = 0
    for (v, n) in VN:
        if A_copy > n:
            A_copy -= n
            ans_1 += v*n
        else:
            ans_1 += A_copy * v
            break
    print(ans_1/A)
            
    if VN[0][1] > A:
        ans_2 = 0
        for choose_num in range(A, min(B, VN[0][1]) + 1):
            ans_2 += combination(n, choose_num)
        print(ans_2)
    else:
        for (v, n) in VN:
            if A > n:
                A -= n
            else:
                ans_2 = combination(n, A)
                break
        print(ans_2)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
def cmb(n, r):
    if n-r<0:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

def main():
    n,a,b,*v=map(int,open(0).read().split())
    v.sort(reverse=1)
    m=sum(v[:a])/a
    print(m)
    n=v[a-1]
    x,y=v[:a].count(n),v.count(n)
#    print(x,y)
    ans=0
    if m==n and y-x>0:
        for i in range(x,x+b-a+1):
            ans+=cmb(y,i)
        print(ans)
    else:
        print(cmb(y,x))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
def cmb(n, r):
    if n-r<0:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

def main():
    n,a,b,*v=map(int,open(0).read().split())
    v.sort(reverse=1)
    m=sum(v[:a])/a
    print(m)
    n=v[a-1]
    x,y=v[:a].count(n),v.count(n)
#    print(x,y)
    ans=0
    if m==n and y-x>0:
        for i in range(x,x+b-a+1):
            ans+=cmb(y,i)
        print(ans)
    else:
        print(cmb(y,x))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,A,B=map(int, input().split())
V=list(map(int, input().split()))
d={}
for v in V:
    if v in d:
        d[v]+=1
    else:
        d[v]=1
k=sorted(d.keys(),reverse=True)
def comb1(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    a=b=1
    for i in range(1,k+1):
        a=a*(n-k+i)
        b=b*i
    return a//b
ans=0
if d[k[0]]>=A:
    for x in range(A,min(B,d[k[0]])+1):
        ans+=comb1(d[k[0]],x)
    ave=k[0]
else:
    n=d[k[0]]
    a=[k[0]]*d[k[0]]
    for i in range(1,len(k)):
        if n+d[k[i]]>=A:
            break
        else:
            n+=d[k[i]]
            a+=[k[i]]*d[k[i]]
    ans=comb1(d[k[i]],A-n)
    a+=[k[i]]*(A-n)
    from statistics import mean
    ave=mean(a)
print(ave)
print(ans)

Submission status: Accepted

Solution code:
N,A,B = list(map(int,input().split()))
 
v = list(map(int,input().split()))
 
v.sort()
v=v[::-1]
 
a=v[A-1]
is_first = True
end=-1
for i in range(N):
    if v[i]==a:
        if is_first:
            first=i
            is_first=False
    else:
        if not is_first:
            end=i
            break
 
def comb(n,k):
    a = 1
    b = 1
    for i in range(min(n-k,k)):
        a*=n-i
        b*=i+1
    return a//b
#print(comb(3,1))
if end==-1:
    end=N
if first==0:
    print(a)
    print(sum([comb(end,i) for i in range(A,min(B,end)+1)]))
else:
    print(sum(v[:A])/A)
    print(comb(end-first,A-first))

Submission status: Accepted

Solution code:
from math import factorial
from collections import defaultdict
def nCr(n,r):
    return int(factorial(n)/(factorial(n-r)*factorial(r)))
N,A,B=map(int,input().split())
V=list(map(int,input().split()))
dict=defaultdict(int)
for i in V:
    dict[i]+=1
V.sort(reverse=True)
v=[]
value=0
tmp=0
for i in range(N):
    if value!=V[i]:
        tmp=1
        value=V[i]
    else:
        tmp+=1
    v.append([V[i],tmp])
ans=0
print(sum(V[:A])/A)
if V[0]==V[A-1]:
    for i in range(A,B+1):
        if V[0]==V[i-1]:
            ans+=nCr(dict[V[0]],i)
    print(ans)

else:
    print(nCr(dict[V[A-1]],v[A-1][1]))

Submission status: Accepted

Solution code:
from collections import Counter

def comb(x,y):
    c=1
    for i in range(y):
        c*=(x-i)
        c//=(i+1)
    return c

n,a,b=map(int,input().split())
V=list(map(int,input().split()))
V.sort(reverse=True)
print(sum(V[:a])/a)
c=Counter(V)
cnt=0
for v in V:
    i=c[v]
    cnt+=i
    if cnt>=a:
        break
if V[0]==V[a-1]:
    ans=0
    for j in range(a,min(cnt,b)+1):
        ans+=comb(i,j)
    print(ans)
else:
    print(comb(i,a+i-cnt))

Submission status: Accepted

Solution code:
from collections import Counter
from math import factorial
n, a, b = map(int, input().split())
v = sorted(list(map(int, input().split())), reverse = True)
max_value = sum(v[:a])/a
cnt1 = Counter(v)[v[a-1]]
cnt2 = Counter(v[:a])[v[a-1]]
comb = factorial(cnt1)//factorial(cnt2)//factorial(cnt1-cnt2)
if v[a-1]==v[0]:
    comb=0
    for i in range(a, min(cnt1, b)+1):
        comb += factorial(cnt1)//factorial(i)//factorial(cnt1-i)
print(max_value)
print(comb)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import mul

def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))

n,a,b = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse = True)
if v[0] == v[a-1]:
  print(v[0])
  c = v.count(v[a-1])
  ans = 0
  for i in range(a,min(c+1,b+1)):
    ans += cmb(c,i)
  print(ans)
else:
  print(sum(v[:a]) / a)
  c = v.count(v[a-1])
  d = 0
  for key,value in enumerate(v):
    if value == v[a-1]:
      d = key
      break
  print(cmb(c,a-d))

Submission status: Accepted

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

V.sort(reverse = True) # desc order

x = V[A-1]
large = V.index(x) # xより大きなものの個数
cnt = V.count(x)

import numpy as np
comb = np.zeros((N+1,N+1),dtype=np.int64)
comb[:,0] = 1
for n in range(1,N+1):
  comb[n,1:] = comb[n-1,1:] + comb[n-1,:-1]

max_avg = sum(V[:A]) / A
pattern = 0
if V[0] == V[A-1]:
  for choose in range(A-large, B-large+1):
    pattern += comb[cnt,choose]
else:
  pattern = comb[cnt,A-large]
  
print(max_avg)
print(pattern)

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)
def comb(n,r):
    if r > n:
        return 0
    else:
        return factorial(n)//(factorial(n-r)*factorial(r))
n,a,b = map(int,input().split())
v = list(map(int,input().split()))
v.sort(reverse=True)
max_mean = sum(v[0:a])/a
print(max_mean)
#選び方の総数を求める
c = Counter(v)
i = 0
num = 0
ans = 0
while num<a:
    if num+c[v[i]]>=a:
        num += c[v[i]]
    else:
        num += c[v[i]]
        i += 1
num -= c[v[i]]

if i > 0:
        ans += comb(c[v[i]],a-num)
        print(ans)
else:
    for j in range(a,b+1):
        if c[v[0]] >=j:
            ans += comb(c[v[0]],j)
    print(ans)

Submission status: Accepted

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

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

m = v[a-1]
l = -1
while v[l+1] > m:
  l += 1
r = a-1
while r+1 <= n-1 and v[r+1] == m:
  r += 1
#print(l,r)
print(sum(v[:a])/a)
ans = 0
if l == -1:
  for k in range(a,b+1):
    ans += comb(r-l,(k-1-l))
else:
  ans += comb(r-l,(a-1-l))
print(ans)
#print(comb(1,1))

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

N,A,B = map(int,input().split())
v = [int(i) for i in input().split()]


dp = [[0 for j in range(B+1)] for i in range(N)]
for i in range(N):
    dp[i][0] = max(v[:i+1])

for i in range(N-1):
    for j in range(min(B,i+1)):
        dp[i+1][j+1] = max(dp[i][j+1],(dp[i][j]*(j+1)+v[i+1])/(j+2))

ans = max(dp[-1][A-1:B+1])
# v.sort()
# v.reverse()
# ans = 0
# for i in range(A):
#     ans += v[i]
# ans /= A
print(ans)

v.sort()
v.reverse()

cnt = 0
if v[0] != v[A-1]:
    m = v.count(v[A-1])
    n = v[:A].count(v[A-1])
    cnt = math.factorial(m)//(math.factorial(n)*math.factorial(m-n))
else:
    m = v.count(v[0])
    n = A
    for i in range(n,B+1):
        if m-i < 0:
            pass
        else:
            cnt += math.factorial(m)//(math.factorial(i)*math.factorial(m-i))

print(cnt)

Submission status: Accepted

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

items = V[:]

items = sorted(items, reverse=True)
sub_items = items[:A]
ave = sum(sub_items)/len(sub_items)
rest_items = items[A:]

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

if ave != sub_items[0]:
    # nCr
    r = sub_items.count(sub_items[-1])
    n = rest_items.count(sub_items[-1]) + r
    pattern = combinations_count(n, r)
else:
    n = items.count(ave)
    pattern = 0
    for r in range(A, min(n+1, B+1)):
        pattern += combinations_count(n, r)


print(ave)
print(pattern)

Submission status: Accepted

Solution code:
import math
def f(n):
    return math.factorial(n)
n,a,b=map(int,input().split())
V=[int(i) for i in input().split()]
V.sort()
if n==a:
  print(sum(V)/a)
  print(1)
else:
  ans=sum(V[n-a:])/a
  count1=V[n-a:].count(V[n-a])
  count2=V[:n-a].count(V[n-a])
  print(ans)
  if count1==a:
    ans2=0
    for i in range(min(count2+1,b-a+1)):
      ans2+=f(count1+count2)/f(count1+i)/f(count2-i)
    print(round(ans2))
  else:
    print(round(f(count1+count2)/f(count1)/f(count2)))

Submission status: Accepted

Solution code:
from math import factorial

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

u = sorted(v, reverse=True)
m = sum(x == u[A - 1] for x in v)


# 非負の整数n, k について、二項係数nCkを返す関数
def c(n, k):
    return factorial(n) // (factorial(n - k) * factorial(k))


# 平均の最大値は価値の高いものから順にA個選んだときの平均値
# そのような選び方は二項係数を用いて求める
ans = '{}\n{}'.format(
    sum(u[:A]) / A,
    (
        c(
            m,
            A - sum(x > u[A - 1] for x in v)
        ) if u[A - 1] < u[0] else
        sum(
            c(m, k)
            for k in range(A, min(m + 1, B + 1))
        )
    )
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
N,A,B = map(int,input().split())
*v, = sorted(map(int,input().split()))[::-1]
f = [1]*51
for i in range(1,51):
    f[i] = f[i-1]*i
def comb(n,r):
    return f[n]//f[r]//f[n-r]
print(sum(v[:A])/A)
a = v[:A].count(v[A-1])
b = v[A:].count(v[A-1])+a
ans = comb(b,a)
if a == A:
    for k in range(A+1,B+1):
        ans += comb(b,k)
print(ans)

Submission status: Accepted

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

v.sort(reverse=1)

V = v[A-1]
print(sum(v[:A]) / A)

before = 0
after = 0
all = False
for i in range(A):
    if v[i] == V:
        if i == 0:
            all = True
        before = A - i
        break
for i in range(A, N):
    if v[i] == V:
        after += 1
    else:
        break

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

if all:
    ans = 0
    for i in range(before, min(B+1, before+after+1)):
        ans += C(before+after, i)
    print(ans)
else:
    print(C(before+after, before))

Submission status: Accepted

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

ma = sum(V[:A]) / A
num = 0

MOD = 10 ** 9 + 7
M = 60
fact = [0] * M
fact[0] = 1
for i in range(1, M):
    fact[i] = fact[i - 1] * i


def comb(n, k):
    return fact[n] // fact[n - k] // fact[k]


num = 0
pos = 0
for i in range(N):
    if V[i] == V[A - 1]:
        num += 1
        if i < A:
            pos += 1
ans = 0
if pos == A:
    for i in range(A, B + 1):
        ans += comb(num, i)
else:
    ans += comb(num, pos)


print(ma)
print(ans)

Submission status: Accepted

Solution code:
from scipy.misc import comb
N, A, B = map(int, input().split())
V = list(map(int, input().split()))


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


Ath_CNT = V.count(V[A - 1])
V_than_Ath_CNT = len([v for v in V if v > V[A - 1]])
if max(V) == V[A - 1]:
    ans = 0
    for k in range(A, B + 1):
        ans += comb(Ath_CNT, k, 1)
else:
    ans = comb(Ath_CNT, A - V_than_Ath_CNT, 1)
print(ans)

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())
v = list(map(int, input().split()))

v.sort()
v.reverse()

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

c = v.count(v[a-1])
d = v[:a].count(v[a-1])

if v[0]!=v[a-1]:
    print(combinations_count(c,d))
else:
    ans = 0
    lim = min(c,b)
    for i in range(a,lim+1):
        ans += combinations_count(c,i)
    print(ans)

Submission status: Accepted

Solution code:
from collections import*
from itertools import*
from bisect import*
from operator import mul
from functools import reduce
 
def cmb(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
 
n,a,b,*v=map(int,open(0).read().split())
v=sorted(Counter(v).items(),reverse=1,key=lambda x:x[0])
vindex=[0]+list(accumulate(V for K,V in v))+[float("inf")]
#print(v,vindex)
lower=vindex[bisect_left(vindex,a)-1]
upper=vindex[bisect_left(vindex,a)]
count=0
ans=0
 
if a<=vindex[1]:
    ans=0
    for i in range(a,min(b,vindex[1])+1):
        ans+=cmb(vindex[1],i)
    print(float(v[0][0]))
    print(ans)
 
else:
    for s,t in v:
        count+=t
        if count>lower:
            ans+=s*(a-lower)
            break
        else:
            ans+=s*t
    print(ans/a)
    print(cmb(upper-lower,a-lower))

Submission status: Accepted

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

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

v.sort(reverse=True)
d = dict()
for c in v:
    if d.__contains__(c):
        d[c]+=1
    else:
        d[c]=1

def C(x,y):
    if y>x:
        return 0
    if y>x//2:
        y = x-y
    res = 1
    for i in range(x,x-y,-1):
        res *= i
    for i in range(1,y+1):
        res //= i
    return res
m_sum = 0
m_cnt = 1
for i in range(a,b+1):
    if sum(v[:i])*m_cnt > i*m_sum:
        m_sum = sum(v[:i])
        m_cnt = i
m_idx = []
for i in range(a,b+1):
    if sum(v[:i])*m_cnt == i*m_sum:
        m_idx.append(i)
print("%0.6f"%(m_sum/m_cnt))

res_cnt = 0
for idx in m_idx:
    cnt_in = 0
    for i in range(idx-1,-1,-1):
        if v[i]==v[idx-1]:
            cnt_in+=1
        else:
            break
    res_cnt += C(d[v[idx-1]],cnt_in)
print(res_cnt)

Submission status: Accepted

Solution code:
def value_and_count(x):
    d = {}
    for xi in x:
        if xi in d.keys():
            d[xi] += 1
        else:
            d[xi] = 1
    return d

def comb(n, k):
    k = min(n - k, k)
    denominator = 1 # 分母
    numerator = 1 # 分子
    for i in range(k):
        denominator *= i + 1
        numerator *= n - i
    return numerator // denominator

n, a, b = map(int, input().split())
v = list(map(int, input().split()))
d_v = value_and_count(v)
v.sort(reverse=True)
sum_v = sum(v[:a])
mean_v = sum_v / a
print(mean_v)

ans = 0
d_vk = None
for k in range(a, b + 1):
    vk = v[:k]
    sum_vk = sum(vk)
    if sum_vk / k < mean_v:
        break

    if d_vk is None:
        d_vk = value_and_count(vk)
    else:
        d_vk[vk[-1]] += 1

    ans_k = 1
    for vi, ci in d_vk.items():
        ans_k *= comb(d_v[vi], ci)
    ans += ans_k

print(ans)