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
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
from fractions import Fraction as frac  #frac(a,b)で正確なa/b
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n,a,b=map(int,input().split())
A=sorted(list(map(int,input().split())))
print(sum(A[n-a:])/a)
q=A[n-a]
cnt=A.count(A[n-a])
kaku= n- biright(A,q)

def C(n, r ,mod=2**62):
    if n-r<r: r=n-r
    if r == 0: return 1
    if r == 1: return n

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

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

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

    return result % mod
ans=0
if cnt==1:
    print(1);exit()

if kaku==0:
    for i in range( a-kaku,min(b-kaku,cnt)+1 ):
        ans+=C(cnt,i)

else:
    ans=C(cnt,a-kaku)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def cmb(n,k):
    over = 1
    under = 1
    for i in range(n-k+1,n+1):
        over *= i
    for i in range(1,k+1):
        under *= i
    return over//under

N,A,B = map(int,input().split())
v = list(map(int,input().split()))
C = Counter(v)
li = sorted(list(C.keys()),reverse=True)
ans = 0
SUM = 0
ave = 0
remain = A
n = C[li[0]]
if n >= A:
    ave = li[0]
    for k in range(A,min(B,n)+1):
        ans += cmb(n,k)
else:
    for i in li:
        if C[i] < remain:
            SUM += i*C[i]
            remain -= C[i]
        else:
            SUM += i*remain
            ans = cmb(C[i],remain)
            ave = SUM/A
            break
print(ave)
print(ans)

Submission status: Accepted

Solution code:
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=map(int,input().split())
lst=list(map(int,input().split()))
lst.sort()

print(sum(lst[-a:])/a)

pin=lst[-a]
ans=0

l=lst[:-a].count(pin)
r=lst[-a:].count(pin)


if pin*a==sum(lst[-a:]):
    cnt=0
    for i in range(a,min(b,l+r)+1):
        cnt+=cmb(l+r,i)
    
    print(cnt)
    exit()


print(cmb(l+r,r))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

#階乗#
lim = 50
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1]

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


N, A, B = MAP()
v = sorted(LIST(), reverse=True)
key = v[A-1]
print(sum(v[:A])/A)

v = v[::-1]
n = bisect(v, key) - bisect_left(v, key)
m = N - bisect(v, key)


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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

#階乗#
lim = 50
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1]

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


N, A, B = MAP()
v = sorted(LIST(), reverse=True)

V_cnt = Counter(v)
V_max = Counter(v[:A])
key = v[A-1]
print(sum(v[:A])/A)

v = v[::-1]

idx_1 = bisect_left(v, key)
idx_2 = bisect(v, key)
n = idx_2 - idx_1
k = bisect(v, key)
m = N - k


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

Submission status: Accepted

Solution code:
import sys
inp = lambda: sys.stdin.readline()
mi = lambda: map(int, inp().split())
li = lambda: list(map(int, inp().split()))
mf = lambda: map(float,inp().split())
lf = lambda: list(map(float,inp().split()))

def nCk(n,k):
    u,s = 1,1
    for i in range(n - k + 1,n + 1):u *= i
    for i in range(1,k + 1):s *= i
    return u // s
N,A,B = mi()
vec = lf()
vec.sort()
vec = vec[::-1]
avr = 0.0
for i in range(A):
    avr += vec[i]
avr /= A
print("{:.08f}".format(avr))
kosu = vec.count(vec[A - 1])
#print(kosu)
if kosu == 1:
    print(1)
    sys.exit()
if vec[0] == vec[A - 1]:
    ans = 0
    for i in range(A,B + 1):
        if vec[i - 1] != vec[0]:
            break
        ans += nCk(kosu,i)
    print(ans)
else:
    K = vec[:A].count(vec[A - 1])
    print(nCk(kosu,K))

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from itertools import product
from random import randint

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def debug(n, a, b, V, ave):
    cnt = 0
    for pattern in product([0, 1], repeat=n):
        if a <= sum(pattern) <= b:
            tot = 0
            for idx, p in enumerate(pattern):
                if p == 1:
                    tot += V[idx]
            res = tot / sum(pattern)
            if abs(res - ave) <= 10 ** -6:
                cnt += 1
    return cnt


def resolve():
    n, a, b = map(int, input().split())
    V = list(map(int, input().split()))

    V.sort(reverse=True)
    ave = 0
    for i in range(a, b + 1):
        tot = sum(V[:i])
        if ave <= tot / i:
            ave = tot / i
            used = V[:i]

    if len(set(used)) == 1:
        cnt = V.count(used[0])
        ave = used[0]
        cmb = [0] * len(used)
        for i in range(a, len(used) + 1):
            x = y = 1
            for j in range(1, i + 1):
                x *= (cnt + 1 - j)
                y *= j
            cmb[i - 1] = x // y
        res = sum(cmb)
    else:
        use_cnt = Counter(used)
        used = set(used)
        D = Counter(V)
        res = 1
        for num in used:
            cnt = use_cnt[num]
            x = y = 1
            for j in range(1, cnt + 1):
                x *= (D[num] + 1 - j)
                y *= j
            res *= x // y
    print(ave)
    print(res)
    # print(debug(n, a, b, V, ave))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

AAA = sum(v[N-A:])/A
print(AAA)

p = 0
import math
for i in range(A,B+1):
    ans = v[N-i:]
    if sum(ans)/i == AAA:
        rest = v[:N-i]
        m = ans.count(ans[0])
        n = rest.count(ans[0])
        C = math.factorial(n+m)//(math.factorial(m)*math.factorial(n))
        p += C

print(p)

Submission status: Accepted

Solution code:
N,A,B=list(map(int,input().split()))
l=list(map(int,input().split()))
l.sort(reverse=True)
all_n=l.count(l[0])
from scipy.special import comb
from collections import Counter
l2=l[0:A]
l_c=Counter(l)
max_mean=sum(l2)/A
l2=Counter(l2).items()
print(max_mean)
ans=1
if l[0]==l[A-1]:
   ans=0
   for i in range(A,B+1):
      ans+=comb(all_n,i,exact=True)
   print(ans)
   exit()
for i,j in l2:
   ans*=comb(l_c[i],j,exact=True)
print(ans)

Submission status: Accepted

Solution code:
from math import factorial
from collections import Counter

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

ma=sum(v[:a])/a
print(ma)
cnt=Counter(v)

if v[a-1]==v[0]:
    m=cnt[v[0]]
    ans=0
    for i in range(a,min(b,m)+1):
        ans+=factorial(m)//(factorial(i)*factorial(m-i))
    
    print(ans)
else:
    m=cnt[v[a-1]]
    r=Counter(v[:a])[v[a-1]]

    print(factorial(m)//(factorial(r)*factorial(m-r)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 2**3217-1
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

N,A,B = IL()
V = IL()

dic = DD(int)
for v in V:
  dic[v] += 1
keys = [k for k in dic]
keys.sort(reverse = True)

count = 0
S = 0
p = 0
while count < A:
  k = keys[p]
  S += k * dic[k]
  count += dic[k]
  p += 1
  
S -= k * dic[k]
count -= dic[k]
if count:
  left = A-count
  S += k * left
  count = A
  print(S/count)
  print(nCr(dic[k],left))
else:
  print(k)
  ans = 0
  for i in range(A,min(B,dic[k])+1):
    ans += nCr(dic[k],i)
  print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 170141183460469231731687303715884105727
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

N,A,B = IL()
V = IL()

dic = DD(int)
for v in V:
  dic[v] += 1
keys = [k for k in dic]
keys.sort(reverse = True)

count = 0
S = 0
p = 0
while count < A:
  k = keys[p]
  S += k * dic[k]
  count += dic[k]
  p += 1
  
S -= k * dic[k]
count -= dic[k]
if count:
  left = A-count
  S += k * left
  count = A
  print(S/count)
  print(nCr(dic[k],left))
else:
  print(k)
  ans = 0
  for i in range(A,min(B,dic[k])+1):
    ans += nCr(dic[k],i)
  print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**20+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  """
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret
  """
  ans = 1
  for i in range(r):
    ans *= n-i
  for i in range(r):
    ans //= i+1
  return ans

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

N,A,B = IL()
V = IL()

dic = DD(int)
for v in V:
  dic[v] += 1
keys = [k for k in dic]
keys.sort(reverse = True)

count = 0
S = 0
p = 0
while count < A:
  k = keys[p]
  S += k * dic[k]
  count += dic[k]
  p += 1
  
S -= k * dic[k]
count -= dic[k]
if count:
  left = A-count
  S += k * left
  count = A
  print(S/count)
  print(nCr(dic[k],left))
else:
  print(k)
  ans = 0
  for i in range(A,min(B,dic[k])+1):
    ans += nCr(dic[k],i)
  print(ans)

Submission status: Accepted

Solution code:
import math

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

v.sort(reverse = True)
total = 0

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

for i in range(A):
    total = total + v[i]
else:
    print(total / A)
    
count = 0
min = v[A-1]
number = v.count(min)

if(v.index(min) == 0):
    for i in range(A,number+1):
        if(i>B):
            break
        count = combinations_count(number,i) + count
    print(count)
else:
    print(combinations_count(number,A - v.index(min)))

Submission status: Accepted

Solution code:
N,A,B=map(int, input().split())
D=list(map(int, input().split()))
D=sorted(D)[::-1]
import math
from math import comb
print(sum(D[:A])/A)
ans=0
if D[0]!=D[A-1]:
  n=D.count(D[A-1])
  k=D[:A].count(D[A-1])
  print(comb(n,k))
else:
  ans=0
  n=D.count(D[A-1])
  for i in range(A,min(n,B)+1):
    ans+=comb(n,i)
  print(ans)

Submission status: Accepted

Solution code:
import math
def C(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)
print(sum(l[:a])/a)
if l.count(l[a-1]) > 1:
    ans = 0
    x = l[a-1]
    y = l[:a].count(x)
    z = l.count(x)
    if l[0] != x:
        print(C(z, y))
    else:
        ans = 0
        for i in range(a, min(b, z)+1):
            ans += C(z, i)
        print(ans)
else:
    print(1)

Submission status: Accepted

Solution code:
def nCr(n,r):
    return fac[n]//fac[r]//fac[n-r]

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

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

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

Cnt=v.count(v[A-1])
res=0

if v[0]==v[A-1]:
    for i in range(A,B+1):
        res+=nCr(Cnt,i)

else:
    M=v[:A].count(v[A-1])
    res=nCr(Cnt,M)

print(res)

Submission status: Accepted

Solution code:
from collections import Counter

def nCr(n,r):
    return fac[n]//fac[r]//fac[n-r]

N,A,B=map(int,input().split())
v=sorted(map(int,input().split()),reverse=True)
fac=[1]
for i in range(N):
    fac.append(fac[-1]*(i+1))
print(sum(v[:A])/A)
c=Counter(v)
if v[0]==v[A-1]:
    Cnt=c[v[0]]
    res=0
    for i in range(A,B+1):
        res+=nCr(Cnt,i)
    print(res)
else:
    All=c[v[A-1]]
    M=v[:A].count(v[A-1])
    print(nCr(All,M))

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
V = sorted([int(x) for x in input().split()],reverse=True)
from statistics import mean
from math import comb
maxmean = mean(V[:A])
if V[0] != V[A-1]:
    n = V.count(V[A-1])
    k = V[:A].count(V[A-1])
    way = comb(n, k)
else:
    n = V.count(V[A-1])
    way = sum(comb(n, k) for k in range(A, min(n,B)+1))
print(maxmean)
print(way)

Submission status: Accepted

Solution code:
import collections
import math

N, A, B = map(int, input().split())
v = list(map(int, input().split()))
d = list(reversed(sorted(v)))
c = collections.Counter(v)

start = A
end = A
if c[d[0]] >= A:
  end = min(c[d[0]], B)
  
ans = 0
ans_com = 0
for i in range(start, end+1):
  sel = i
  com = 1
  total = 0
  for j in range(len(d)):
    p = c[d[j]]
    com *= math.factorial(p)
    total += d[j] * p
    if sel <= p:
      com /= (math.factorial(sel) * math.factorial(p-sel))
      total -= d[j] * (p - sel)
      break
    sel -= p
  ave = total / i
  ans = ave
  ans_com += int(com)
print(ans)
print(ans_com)

Submission status: Accepted

Solution code:
import math
import sys
N, A, B = map(int, input().split())

v = list(map(int, input().split()))
v.sort()
    
def reduce(x):
  a = x[0]
  b = x[1]
  c = math.gcd(a,b)
  return (a//c, b//c)

def add_dict(dic, a, s):
  if a in dic:
    dic[a] += s
  else:   
    dic[a] = s
    
def comb(a, b):
  b = min(b, a-b)
  ans = 1
  for i in range(a,a-b,-1):
    ans *= i
  for j in range(1,b+1):
    ans //= j
  return ans

ct = {}
v.reverse()
sm = 0 #価値の和
i_prv = -1 #前回のvの値がでてくる最後の項数を示す
i_nxt = 0
search = True
dict_keys_list = []
for i in range(B):
  if search: # i_nxtを探す
    j = i
    while j < N-1 and v[j] == v[j+1]:
      j += 1
    i_nxt = j
    search = False
    
  sm += v[i]
  if A-1 <= i <= B-1: #品物はA個以上B個以下選ぶ
    add_dict(ct, reduce((sm, i+1)), comb(i_nxt-i_prv, i-i_prv))
    dict_keys_list.append(reduce((sm, i+1)))
    
  if i == i_nxt: #値が次に減る時は、i_prvを更新
    i_prv = i_nxt
    search = True
    

dict_keys_list.sort(key = lambda x: x[0]/x[1])
print(dict_keys_list[-1][0] / dict_keys_list[-1][1])
#print(dict_keys_list)
#print(ct)
print(ct[dict_keys_list[-1]])

Submission status: Accepted

Solution code:
from math import factorial

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

a = 0
for i in range(A):
    a += V[i]
a /= A
print(a)

c = 0

if V[0] != V[A-1]:
    r = 0
    while True:
        r += 1
        if V[A-1-r] != V[A-1]:
            break
    n = 0
    while True:
        if A+n > N-1:
            break
        if V[A+n] != V[A-1]:
            break
        n += 1
    n += r
    c = round(factorial(n) / factorial(r) / factorial(n-r))

else:
    n = 0
    while True:
        n += 1
        if n > N-1:
            break
        if V[n] != V[0]:
            break
    B = min(B, n)
    for i in range(B-A+1):
        c += round(factorial(n) / factorial(A+i) / factorial(n-A-i))

print(c)

Submission status: Accepted

Solution code:
N,A,B = map(int,input().split())
V = sorted(list(map(int,input().split())))[::-1]
W = sum(V[:A])/A
print(W)

f = [1]
for n in range(50):
  f+=[f[-1]*(n+1)]
x = V.count(V[A-1])
if V[0]==V[A-1]:
  print(sum(f[x]//(f[x-n]*f[n]) for n in range(A,B+1)))
else:
  y=V[:A].count(V[A-1])
  print(f[x]//(f[x-y]*f[y]))

Submission status: Accepted

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

v.sort(reverse=True)

maximum = sum(v[:a])

print(maximum / a)

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

# 選ぶ品物の価値が全て等しい時
if v[0] == v[a-1]:
    num = v.count(v[0])
    ans = 0
    for i in range(a, b+1):
        ans += comb(num, i)
    print(ans)
else:
    num = v.count(v[a-1])
    r = v[:a].count(v[a-1])
    print(comb(num, r))

Submission status: Accepted

Solution code:
import math
 
def combination(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

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

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

v_count = {}

for v in V:
    if v not in v_count:
        v_count[v] = 1
    else:
        v_count[v] += 1

v_count = sorted(v_count.items(), key=lambda x:-x[0])

tmp_count = [0]
ans = 0
for val,count in v_count:
    tmp_count.append(tmp_count[-1]+count)
    if tmp_count[-1] < A:
        ans += val*count
    else:
        ans += val*(A-tmp_count[-2])
        print(ans/A)
        break
#print(tmp_count, ans)
if v_count[0][1] < A:
    comb = A-tmp_count[-2]
    root = combination(v_count[len(tmp_count)-2][1],comb)
else:
    root = 0
    for i in range(A, min(v_count[0][1],B)+1):
        root += combination(v_count[0][1],i)

print(root)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

def nCr(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 = (int(x) for x in input().split())
V = list(int(x) for x in input().split())
V.sort(reverse=True)

avg = sum(V[:a]) / a
k = V[:a].count(V[a - 1])
m = V.count(V[a - 1])
if k == a:
    ans = sum(nCr(m, i) for i in range(k, min(m, b) + 1))
else:
    ans = nCr(m, k)
print(avg)
print(ans)

Submission status: Accepted

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


def main():
    n, a, b = map(int, input().split())
    v = list(map(int, input().split()))
    
    dp = [[0, 0] for _ in range(n+1)]
    dp[0][1] = 1
    for i in range(n):
        for j in range(n-1, -1, -1):
            if dp[j][1]:
                if dp[j+1][0] < dp[j][0]+v[i]:
                    dp[j+1][0] = dp[j][0]+v[i]
                    dp[j+1][1] = dp[j][1]
                elif dp[j+1][0] == dp[j][0]+v[i]:
                    dp[j+1][1] += dp[j][1]
    
    index, value, count = a, dp[a][0], dp[a][1]
    for i in range(a+1, b+1):
        if value*i == index*dp[i][0]:
            count += dp[i][1]
        elif value*i < index*dp[i][0]:
            value = dp[i][0]
            index = i
            count = dp[i][1]
                
    print(value/index)
    print(count)
    
if __name__ == "__main__":
    main()