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 collections
import math
N,A,B  = map(int, input().split())
v = list(map(int,input().split()))

nums = collections.defaultdict(int)
for x in v:
    nums[x] += 1
ave = [[0 for i in range (B - A + 1)] for j in range(2)]
v.sort(reverse = True)
for i in range(A , B + 1):
    ave[0][i - A] = sum(v[:i]) / i
    ave[1][i - A] = v[:i]
ans = max(ave[0])
print(ans)

indexes = [i for i in range(B - A + 1) if ave[0][i] == ans]
max_counter = [] * len(indexes)
ans = 0
for i in indexes:
    counter = collections.Counter(ave[1][i])
    tmp_ans = 1
    for x in counter:
        tmp_ans *= math.factorial(nums[x]) // math.factorial(counter[x]) // math.factorial(nums[x] - counter[x])
    ans += tmp_ans
print(ans)

Submission status: Accepted

Solution code:
from math import factorial


def comb(a, b):
    if b < 0 or a < b:
        return 0
    return factorial(a) // factorial(b) // factorial(a - b)


N, A, B = map(int, input().split())
V = [int(s) for s in input().split()]
V.sort(reverse=True)
ans1 = sum(V[:A]) / A
num = V.count(V[A - 1])
if V[0] == V[A - 1]:
    ans2 = sum([comb(num, m) for m in range(A, B + 1)])
else:
    m = V[:A].count(V[A - 1])
    ans2 = comb(num, m)
print(ans1)
print(ans2)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
v=[int(i) for i in input().split()]
v.sort()
v.reverse()
ans=0
from collections import Counter
c=Counter()
k=0
tmp=0
for i in range(n):
    if i<a-1:
        ans+=v[i]
        c[v[i]]+=1
    elif i==a-1:
        tmp=v[i]
        c[v[i]]+=1
        ans+=v[i]
    else:
        if tmp!=v[i]:
            break
        else:
            c[v[i]]+=1
            k+=1
ans=ans/a
print(ans)
def f(n,m):
    import math
    if n-m<0:
        return 0
    return(math.factorial(n)//math.factorial(n-m)//math.factorial(m))
ans2=0

if ans==tmp:
    for i in range(c[tmp]-k,c[tmp]-k+b-a+1):
        ans2+=f(c[tmp],i)
    print(ans2)
else:
    print(f(c[tmp],k))

Submission status: Accepted

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

def combi(n, m):
    from math import factorial
    return factorial(n) // (factorial(m) * factorial(n-m))

val.sort(reverse=True)
ave = sum(val[:A])/A

l = val.index(val[A-1])
x = val.count(val[A-1])
ct = 0

if val[0] == val[A-1]:
    for i in range(A, x+1):
        if i > B:
            break
        else:
            ct += combi(x, i)
else:
    ct = combi(x, A-l)
print(ave)
print(ct)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,a,b=map(int,input().split())
v_list=list(map(int,input().split()))
v_list.sort(reverse=True)
x=v_list[a-1]
print(sum(v_list[:a])/a)
import math
if v_list[0]==x:
    count=0
    for i in range(n):
        if v_list[i]==x:
            count+=1
    ans=0
    for i in range(a,min(b,count)+1):
        ans+=math.factorial(count)//(math.factorial(i)*math.factorial(count-i))
    print(ans)
else:
    counta=0
    for i in range(a):
        if v_list[i]==x:
            counta+=1
    count=0
    for i in range(n):
        if v_list[i]==x:
            count+=1
    ans=math.factorial(count)//(math.factorial(counta)*math.factorial(count-counta))
    print(ans)

Submission status: Accepted

Solution code:
nCk = [[0 for i in range(51)] for j in range(51)]

nCk[1][0] = 1
nCk[1][1] = 1
for i in range(2, 51):
    for j in range(51):
        if j > 0:
            nCk[i][j] = nCk[i-1][j-1] + nCk[i-1][j]
        else:
            nCk[i][j] = nCk[i-1][j]

N, A, B = map(int,input().split())
kouho = []
V = list(map(int,input().split()))
V.sort(reverse = True)
acc = 0
for i in range(B):
    if i < A-1:
        acc += V[i]
    else:
        acc += V[i]
        kouho.append(acc / (i+1))

print(str(kouho[0]))

cnt = 0
for i in range(len(kouho)):
    m = 0
    n = 0
    if kouho[i] != kouho[0]:
        break
    for j in range(N):
        if V[j] == V[A+i-1]:
            if j < A+i:
                m+=1
            n+=1
    cnt += nCk[n][m]
print(str(cnt))

Submission status: Accepted

Solution code:
from bisect import bisect_left
from operator import mul
from functools import reduce

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

V.sort(reverse=True)




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

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

c = 0
for i in range(A-1, B):
    if V[i] == V[A-1]:
        c += 1
#print(V, V[A-1])

for i, v in enumerate(V):
    if v == V[A-1]:
        ia = i
        break
l = A - ia
maxl = V.count(V[A-1])
#print(A, ia, l, maxl, c)
if ia == 0:
    ans = 0
    for d in range(c):
        ans += cmb(maxl, l+d)
else:
    ans = cmb(maxl, l)
print(ans)

Submission status: Accepted

Solution code:
import collections
from math import factorial
def comb(n,r):
    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)
c=collections.Counter(v)
k=min(v[:a])
if c[max(v)]<a:
    ans=comb(c[k],v[:a].count(k))
else:
    ans=0
    for i in range(a,min(b,c[k])+1):
        ans+=comb(c[k],i)
print(sum(v[:a])/a)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from statistics import mean
from bisect import bisect_left
INF = float("inf")


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

    numer = [n - r + k + 1 for k in range(r)]
    denom = [k + 1 for k in range(r)]

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

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

    return result


def solve(N: int, A: int, B: int, v: "List[int]"):
    v.sort()
    ave = mean(v[N-A:])
    ma = v[-1]
    print(ave)

    num = v.count(v[N-A])
    hamidashi = v[:N-A].count(v[N-A])
    if ma == ave and hamidashi > 0:
        # すべて同じ価値の場合
        # A個に拘らなくて良い。
        tot = 0
        for i in range(A, B+1):
            # print(num, hamidashi+i)
            tot += cmb(num, i)
        print(tot)
    else:
        print(cmb(num, hamidashi))
    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:

from collections import Counter

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

v = list(map(int, input().split()))
v.sort(reverse=True)

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

counter = Counter(v)
cnt = counter[v[0]]
#最大のｖが一つだけなら残りの選び方、複数あるならその選び方も考慮
ans = 0
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 cnt < A:
    m = v[A-1]
    n = counter[m] # 最小値の個数
    r = v[:A].count(m)
    ans = cmb(n,r)
elif cnt == A:
    ans = 1
    
else:
    for i in range(A, min(cnt, B) + 1):

        ans += cmb(cnt, i)

print(ave_max)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意


def choose(n,k):
    if 0 <= k <= n:
        res = 1
        for i in range(k):
            res *= n-i
            res //= (i+1)
        return res
    else:
        return 0

#n = int(input())
n,a,b = [int(i) for i in readline().split()]
v = [int(i) for i in readline().split()]

v.sort(reverse=True)
s = sum(v[:a])

print(s/a)
from bisect import *

c = v[a]
ans = 0
if v[a-1] != v[a]:
    ans = 1
else:    
    v.sort()
    l = bisect_left(v,c)
    r = bisect_right(v,c)
    if r != n:
        ans = choose(r-l,r+a-n)
    else:
        for i in range(r+a-n,r+b-n+1):
            ans += choose(r-l,i)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    print((a+b)%24)
    return

#B
def B():
    n, m = LI()
    ab = LIR(n)
    cd = LIR(m)
    for a, b in ab:
        ans = inf
        an = 0
        for num, cdi in enumerate(cd):
            c, d = cdi
            if ans > abs(a - c) + abs(b - d):
                ans = abs(a - c) + abs(b - d)
                an = num
        print(an+1) 
    return

#C
def C():
    n = II()
    ans = inf
    for i in range(1, int(math.sqrt(n)) + 1):
        if not n % i:
            ans = min(ans, max(int(math.log(i, 10)), int(math.log(n // i, 10))))
    print(ans+1)
    return

#D
def D():
    _, a, b = LI()
    v = LI()
    v.sort(reverse=True)
    d = defaultdict(int)
    ans = defaultdict(int)
    for vi in v:
        d[vi] += 1
    for i in range(a, b + 1):
        res = v[:i]
        r = res[-1]
        tmp = res.count(r)
        r = math.factorial(d[r]) / math.factorial(tmp) / math.factorial(d[r] - tmp)
        ans[sum(res) / i] += math.ceil(r-0.5)
    ans = list(ans.items())
    ans.sort(reverse=True, key = lambda x:x[0])
    print(ans[0][0])
    print(ans[0][1])
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
from math import factorial as f
def cmb(n,r):
    if n<r:return 0
    else:return f(n)//f(r)//f(n-r)

n,a,b=map(int,input().split())
v=sorted(map(int,input().split()),reverse=True)
m=sum(v[:a])/a
print(m)
i=j=a-1
while 1:
    if i==0:break
    elif v[i-1]!=v[a-1]:break
    else:i-=1
while 1:
    if j==n-1:break
    elif v[j+1]!=v[a-1]:break
    else:j+=1
ans=0
if i==0:
    for r in range(a,b+1):ans+=cmb(j+1,r)
else:
    ans+=cmb(j-i+1,a-i)
print(ans)

Submission status: Accepted

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


def comb(n):
    dp = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1
        dp[i][i] = 1
    for i in range(2, n + 1):
        for j in range(1, i):
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    return dp


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

v.sort(reverse=True)
comb_list = comb(n)

ans = 0.0
for i in range(a):
    ans += v[i]
ans /= a

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

cnt = 0
if y == a:
    for i in range(a, b+1):
        cnt += comb_list[x][i]
else:
    cnt += comb_list[x][y]

print(ans)
print(cnt)

Submission status: Accepted

Solution code:
import collections
import functools
import sys


sys.setrecursionlimit(10 ** 9 + 7)

@functools.lru_cache(maxsize=None)
def c(x, y):
    if y == 0 or x == y:
        return 1
    else:
        return c(x - 1, y - 1) + c(x - 1, y)


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

v.sort(reverse=True)
avg = sum(v[:a]) / a

counter = collections.Counter(v)
if v[0] == v[a - 1]:
    x = counter[v[0]]
    comb = sum(c(x, y) for y in range(a, min(x, b) + 1))
else:
    comb = 1
    for z, y in collections.Counter(v[:a]).items():
        x = counter[z]
        comb *= c(x, y)

print(avg)
print(comb)

Submission status: Accepted

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

items.sort(reverse=True)

maxAvg = sum(items[:A]) / A

print(maxAvg)

fact = [1 for _ in range(N + 10)]

for i in range(1, N + 10):
    fact[i] = (fact[i - 1] * i)

def comb(n, r):
    if 0 < r < n:
        return fact[n] // fact[r] // fact[n - r]
    if r == 0 or r == n:
        return 1
    return 0


if items[0] == items[A - 1]:
    right = A - 1
    while right < N and items[right] == items[0]:
        right += 1
    ans = 0
    for take in range(A, B + 1):
        ans += comb(right, take)
    print(ans)
else:
    left = A - 1
    while left >= 0 and items[left] == items[A - 1]:
        left -= 1
    right = A - 1
    while right < N and items[right] == items[A - 1]:
        right += 1
    ans = comb(right - left - 1, A - left - 1)
    print(ans)

Submission status: Accepted

Solution code:
from scipy.misc import comb 
from collections import defaultdict, deque, Counter
import sys
#from scipy.special import comb
import heapq
import math

input = sys.stdin.readline

sys.setrecursionlimit(10000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N, A, B = [int(a) for a in input().split()]
    V = sorted([int(a) for a in input().split()], reverse=True)

    s = sum(V[:A]) / A
    target = V[A - 1]
    if target == V[0]:
        co = V.count(target)
        t = sum(
            comb(co, c, exact=True)
            for c in range(A, min(B, co) + 1)
        )
        print(s)
        print(t)
        return

    c1 = V[:A].count(target)
    c2 = V.count(target)
    t = comb(c2, c1, exact=True)
    print(s)
    print(t)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

# print(N, A, B, V)

V.sort(reverse=True)

max_list = V[:A]
max_sum = sum(max_list)
print(max_sum / A)

replace = max_list[-1]

num_replace = V.count(replace)

if num_replace == 1:
    print(1)
    exit()

num_replace_in_list = max_list.count(replace)

def combinations(n, m):
    return math.factorial(n) // (math.factorial(n - m) * math.factorial(m))

if replace * A != max_sum:
    ans = combinations(num_replace, num_replace_in_list)
    print(ans)
    exit()


ans = 0
for i in range(A, B + 1):
    if i > num_replace:
        break
    ans += combinations(num_replace, i)

print(ans)

Submission status: Accepted

Solution code:
import math

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

# print(N, A, B, V)

V.sort(reverse=True)

max_list = V[:A]
max_sum = sum(max_list)
print(max_sum / A)

replace = max_list[-1]

num_replace = 0
for v in V:
    if v == replace:
        num_replace += 1

if num_replace == 1:
    print(1)
    exit()

num_replace_in_list = 0
for v in max_list:
    if v == replace:
        num_replace_in_list += 1

if replace * A != max_sum:
    ans = math.factorial(num_replace) // (math.factorial(num_replace - num_replace_in_list) * math.factorial(num_replace_in_list))
    print(ans)
    exit()


ans = 0
for i in range(A, B + 1):
    if i > num_replace:
        break
    ans += math.factorial(num_replace) // (math.factorial(num_replace - i) * math.factorial(i))

print(ans)

Submission status: Accepted

Solution code:
import math

def conbination(n, r): #nCrを求める
    # nCr = n! //(r! * (n-r)!)
    return math.factorial(n) //(math.factorial(r) * math.factorial(n-r))

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

tmp_count = 1 #最初のA個の中にA番目と同じものが何個あるか
tmp = v[0]
for i in range(1, A):
    if v[i] == tmp:
        tmp_count += 1
    else:
        tmp = v[i]
        tmp_count = 1

total_count = tmp_count #全体でA番目と同じものが何個あるか
for i in range(A, N):
    if tmp == v[i]:
        total_count += 1
    else:
        break

ans = 0
if ave == tmp: #ここまで全て同じとき
    # print ('A')
    # for i in range(A, total_count + 1):
    for i in range(A, min(total_count + 1, B + 1)):
        ans += conbination(total_count, i)
else:
    ans += conbination(total_count, tmp_count)

print (ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

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

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

if v[A-1] != v[0] :
    ret = 0
    a = v.count(v[A-1])
    r = v[:A].count(v[A-1])
    print(comb(a, r))

else :
    a = v.count(v[A-1])
    ret = 0
    for i in range(A, min(B, a) + 1) :
        ret += comb(a, i)
    print(ret)

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n,a,b = map(int,input().split())
v = list(map(int,input().split()))
v.sort(reverse = True)
fact = [1]
for i in range(1,n+1):
    fact.append(fact[i-1]*(i))
def comb(n,r):
    return fact[n]// fact[r] //fact[n-r]
ans = sum(v[:a])/a
print(ans)
M,m = max(v[:a]),min(v[:a])
if M != m:
    c1,c2 = v[:a].count(m),v.count(m)
    print(comb(c2,c1))
else:
    ans = 0
    c = v.count(m)
    for i in range(a,b+1):
        if c >= i:
            ans += comb(c,i)
    print(ans)

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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

Submission status: Accepted

Solution code:
def comb(n,k): #nCkを出力する関数
    ans = [[1]]
    tem = []
    for i in range(1,n+1):
        tem = []
        for j in range(i+1):
            if(j==0 or j==i):
                tem.append(1)
            else:
                tem.append(ans[i-1][j-1]+ans[i-1][j])
        ans.append(tem)
    return ans[n][k] 

n,a,b = map(int,input().split())
v = list(map(int,input().split()))
v.sort(reverse = True)
sum = 0
for i in range(a):
    sum+=v[i]
print(sum/a)
count = v.count(v[0])
if count<a:
    count = v.count(v[a-1])
    check = 0
    for i in range(a,n):
        if v[i]!=v[a-1]:
            break
        check+=1
    print(comb(count,check))
else:
    ans = 0
    for i in range(a,min(b+1,count+1)):
        ans += comb(count,i)
    print(ans)

Submission status: Accepted

Solution code:
def f(N):
    C = [[0] * 51 for _ in range(51)]
    for i in range(N + 1):
        for j in range(i + 1):
            if j == 0 or i == j:
                C[i][j] = 1
            else:
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
    return C


def main():
    N, A, B = map(int, input().split())
    V = sorted(list(map(int, input().split())), reverse=True)
    avg = sum(V[:A]) / A
    n = V.count(V[A - 1])
    p = V[:A].count(V[A - 1])
    C = f(N)
    ans = 0
    if p == A:
        for i in range(A, B + 1):
            ans += C[n][i]
    else:
        ans += C[n][p]
    print(avg)
    print(ans)


main()

Submission status: Accepted

Solution code:
#組み合わせ
def comb(a, b):
    if b > a - b:
        return comb(a, a-b)
    ansMul = 1
    ansDiv = 1
    for i in range(b):
        ansMul *= a - i
        ansDiv *= i + 1

    ans = ansMul // ansDiv
    return ans

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

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

for i in range(N):
    for j in range(N):
        if j > i:
            continue
        dp[i+1][j+1] = max(dp[i+1][j+1], (dp[i][j] * j + v[i]) / (j + 1))
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

ans = 0
for i in range(A, B+1):
    ans = max(ans, dp[N][i])

v.sort()
v.reverse()

c = v.count(v[0])
cnt = 0
if v[0] == v[A-1]:
    for i in range(A, B+1):
        if c < i:
            break
        cnt += comb(c, i)
else:
    a = v[:A].count(v[A-1])
    all_a = v.count(v[A-1])
    cnt = comb(all_a, a)

print(ans)
print(cnt)

Submission status: Accepted

Solution code:
import math

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

v.sort()
max_avg = sum(v[-A:]) / A

min_selected = v[- A]
selected = 0
for i in range(len(v) - A, len(v)):
    if v[i] == min_selected:
        selected += 1
    else:
        break
        
not_selected = 0
for i in range(0, len(v) - A):
    if v[i] == min_selected:
        not_selected +=  1
        
case_num = 0
if selected != A:        
    case_num = math.factorial(selected + not_selected) // (math.factorial(selected) * math.factorial(not_selected))
else:
    for i in range(A, min(B, selected + not_selected) + 1):
        case_num += math.factorial(selected + not_selected) // (math.factorial(i) * math.factorial(selected + not_selected - i))
print(max_avg)
print(case_num)

Submission status: Accepted

Solution code:
conb_list = [ [ 1 for i in range(51) ] for j in range(51) ]
for i in range(1,51):
    for j in range(1,51):
        conb_list[i][j] = conb_list[i-1][j] + conb_list[i][j-1]


n, a, b = [ int(v) for v in input().split() ]
num_list = sorted([ int(v) for v in input().split() ], reverse = True)

def mean(inlist):
    return sum(inlist) / len(inlist)

ans = 0
for i in range(a,b+1):
    if i == a:
        min_element = num_list[i-1]
        min_element_count = num_list.count(min_element)
        min_element_index = num_list.index(min_element)
        max_mean = mean(num_list[:i])

        ans += (conb_list[min_element_count - i + min_element_index][i - min_element_index])
    else:
        if max_mean > mean(num_list[:i]):
            break
        else:
            ans += (conb_list[min_element_count - i + min_element_index][i - min_element_index])

print(max_mean)    
print(ans)

Submission status: Accepted

Solution code:
from statistics import mean
from collections import Counter
n,a,b=map(int,input().split())
v=sorted(list(map(int,input().split())),reverse=True)
avg=mean(v[:a])
print(avg)

p=Counter(v[:a])[v[a-1]]
q=Counter(v)[v[a-1]]

def n_func(n):
    ans=1
    for i in range(1,n+1):ans=(ans*i)
    return ans

def nCr(n,r):
    return (n_func(n)//n_func(r))//n_func(n-r)

if v[0]==v[a-1]:
    print(sum([nCr(q,a+i) for i in range(0,min(b,q)-a+1)]))
else:
    print(nCr(q,p))

Submission status: Accepted

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

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

v.sort(reverse = True)
average = sum(v[:a]) / a
print(average)
amount = [a]
for i in range(a + 1, b + 1):
    average2 = sum(v[:i]) / i
    if average == average2:
        amount.append(i)
    else:
        break
com = 0
for i in amount:
    v1 = v[:i]
    v2 = v[i:]
    min_v = min(v1)
    m1 = v1.count(min_v)
    m2 = v2.count(min_v)
    com += combination(m1 + m2, min(m1, m2))
print(com)

Submission status: Accepted

Solution code:

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


def main():
    num, min_num, max_num = map(int, input().split())
    data = list(map(int, input().split()))
    data.sort(reverse=True)

    last_ind = 0
    for i in range(num):
        if data[0] == data[i]:
            last_ind = i
        else:
            break

    sum_now = sum(data[:min_num])
    avg = sum_now / min_num
    now_ind = min_num
    ans_count = 0

    while 1:
        if now_ind >= num:
            break
        if data[now_ind] < avg:
            break
        sum_now += data[now_ind]
        now_ind += 1
        avg = sum_now / now_ind

    in_count = 0
    for i in range(now_ind):
        if data[now_ind - 1] == data[i]:
            in_count += 1

    out_count = 0
    for i in range(now_ind, num):
        if data[now_ind - 1] == data[i]:
            out_count += 1

    # print(in_count, out_count)

    if now_ind - 1 <= last_ind:
        toori = 0
        for i in range(min_num, min(now_ind + 1, max_num + 1)):
            toori += combinations_count(last_ind + 1, i)
    else:
        toori = combinations_count(in_count + out_count, in_count)

    # print(in_count, out_count, last_ind, now_ind)

    print(avg)
    print(toori)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import factorial

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

def max_ave():
    N, A, B = map(int, input().split())
    v = list(map(int, input().split()))
    sort_v = sorted(v, reverse=True)

    # 平均の最大値を求める
    sum_A = 0
    for i in range(A):
        sum_A += sort_v[i]
    max_ave_v = sum_A / A

    print(max_ave_v)

    # 選び方を求める
    V = sort_v[:A]
    num = v.count(min(V))
    a = V.count(min(V))
    cnt = 0
    if max(V) == min(V):
        for i in range(A,B+1):
            if num < i:
                continue
            cnt += combinations_count(num,i)
    else:
        cnt = combinations_count(num,a)
    
    print(cnt)

max_ave()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
INF=1e10

def comb(a, b):
    res=1
    for i in range(b):
        res*=(a-i)
    for i in range(b):
        res//=(b-i)
    return res

from collections import defaultdict
N,A,B=map(int, input().split())
V=list(map(int, input().split()))
V=sorted(V, reverse=True)
cnts = defaultdict(lambda: 0)
for v in V:
    cnts[v]+=1

ans, cnt = -INF, 0
for n in range(A, B+1):
    tmp = sum(V[:n])/n
    if tmp < ans:
        continue
    if tmp > ans:
        ans=tmp
        cnt=0
    nb = 0
    for i in range(n):
        if V[i]==V[n-1]:
            nb+=1
    cnt += comb(cnts[V[n-1]], nb)
print(ans)
print(cnt)

Submission status: Accepted

Solution code:
def com(n, k):
  P = [1]
  for i in range(1, n + 1):
    P.append(P[i - 1] * i)
  return P[n] / P[n - k] / P[k]


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

v.sort(reverse = True)
su = 0
for i in range(A):
  su += v[i]

ac = 0
t = v[A - 1]
k = 100
for i in range(N):
  if v[i] == t:
    ac += 1
    k = min(k, i)

print(su / A)
if k == 0:
  ans = 0
  for i in range(A, min(B, ac) + 1):
    ans += com(ac, i)
  print(int(ans))
else:
  print(int(com(ac, A - k)))

Submission status: Accepted

Solution code:
import numpy as np
import copy
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0 or r == n: 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 = np.sort(v)[::-1]
    ave_max = np.mean(v[:A])

    print(ave_max)


    m = np.sum(v > v[A-1])
    n = np.sum(v == v[A-1])

    if m > 0:
        print(cmb(n, A-m))
    else:
        ans = 0
        for k in range(A, min(B, n)+1):
            ans += cmb(n, k)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
def input_as_int():
    return list(map(int,input().split()))

def get_comb(n):  # n C n まで

    fac = get_fact(n)
    com  = [["error" for _ in range(n+1)] for _ in range (n + 1)]
    for i in range(n + 1):
        for j in range(i + 1):
            if  i >= j:
                com[i][j] = fac[i] // (fac[i-j] * fac[j])
    return com

def get_fact(n):
    temp = 1
    fac = [1]
    for i in range(1, n + 1):
        temp *= i
        fac.append(temp)
    return fac

N,A,B = input_as_int()
Vs = input_as_int()
Vs.sort(reverse= True)
nums = defaultdict(lambda :0)
kose = defaultdict(lambda :0)
com = get_comb(N)
for v in Vs:
    nums[v] += 1
total = 0
for i in range(A):
    total += Vs[i]
    kose[Vs[i]] += 1
av = total / A
i = A
ans = 0
while True:
    temp = 1
    for k,v in kose.items():
        n = nums[k]
        temp *= com[n][v]

    ans += temp
    if i ==B or Vs[i] != Vs[0] :
        break
    else:
        kose[Vs[i]] +=1
        i += 1
print(av)
print(ans)