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 math import factorial
from collections import Counter

def cmb(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)
l=Counter(v)

avg=0
cnt=0
for i in range(A,B+1):
    tmp=sum(v[:i])/i
    if tmp>avg:
        avg=tmp
        cnt=cmb(l[v[A-1]],v[:i].count(v[i-1]))
    elif tmp==avg:
        cnt+=cmb(l[v[A-1]],v[:i].count(v[i-1]))
print(avg)
print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
import math
n,a,b = map(int,input().split())
v = sorted(list(map(int,input().split())))[::-1]
l = Counter(v)
su = 0
ko = 0

def C(a,b):
  return math.factorial(a)//(math.factorial(b)*math.factorial(a-b))
for i in range(a,b+1):
  v1 = v[:i]
  s = sum(v1)/i
  if su<s:
    su = s
    ko = C(l[v[a]],v1.count(v1[-1]))
  elif su==s:
    ko += C(l[v[a]],v1.count(v1[-1]))
 # print(s,ko)
print(su)
print(ko)

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache
def comb(n, k):
    if k == 0:
        return 1
    elif n == k:
        return 1
    else:
        return comb(n-1, k) + comb(n-1, k-1)

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

print(sum(vs[:A]) / A)
v_replaceable = vs[A]

n = vs.count(v_replaceable)
a = A - vs.index(v_replaceable)
b = min(n, B - vs.index(v_replaceable))

if vs[0] == v_replaceable:
    #n個からa~b個を選ぶ選び方が答え。
    print(sum(comb(n, t) for t in range(a, b+1)))
else:
    #n個からa個を選ぶ選び方が答え。
    print(comb(n, a))

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def conv(bb, n):
	ret = 1
	for i in range(bb-n+1, bb+1):
		ret *= i
	for i in range(1, n+1):
		ret //= i
	return ret

def main():
	#a = int(input())
	n, a, b = tin()
	#s = input()
	al = lin()
	al.sort(reverse=True)
	bb = sum(al[:a])/a
	print(bb)
	
	min_use = al[a]
	rrc = al.count(min_use)
	if al[0] == min_use:
		ret = 0
		for n in range(a, min(b, rrc)+1):
			ret += conv(rrc, n)
		print(ret)
		return 
	else:
		rr = [v for v in al if v >= min_use]
		zettai=len(rr)-rrc
		nokori = a- zettai
		n_pattern = conv(rrc, nokori)
		print(n_pattern)
		return
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
v=list(map(int,input().split()))
v.sort()
max_mean=sum(v[-a:])/a
print(max_mean)
from collections import Counter
cva=Counter(v[-a:])
cv=Counter(v)
import math
def ncr(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# 選んだa個が全て同じ値なら
if v[-a]==max_mean:
  ans=0
  for k in range(a,min(b,cv[v[-a]])+1):
    ans+=ncr(cv[v[-a]],k)
  print(ans)
else:
  # aの中で一番小さな数字は何個あるか。
  k0=cva[v[-a]]
  k1=cv[v[-a]]
  ans=ncr(k1,k0)
  print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact

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

c1 = Counter(V)

V.sort(reverse = True)

if all([V[0] == i for i in V[:A]]):
    print(V[0])
    ans = 0
    for i in range(A-1, B):
        if V[i] != V[0]:
            break
        ans += factorial(c1[V[0]])//(factorial(c1[V[0]]-(i+1))*factorial(i+1))
    print(ans)
    sys.exit()

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

c2 = Counter(V[:A])

print(factorial(c1[V[A-1]])//(factorial(c1[V[A-1]]-c2[V[A-1]])*factorial(c2[V[A-1]])))

Submission status: Accepted

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, A, B = LI()
V = LI()

MAX = 51
finv = [None] * MAX


def comb_init():
    finv[0] = 1
    for i in range(1, MAX):
        finv[i] = finv[i - 1] * i


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


def main():
    comb_init()
    V.sort(reverse=True)
    s = sum(V[:A])
    mx = s // A if s % A == 0 else s / A
    print(mx)
    if A == N or V[A - 1] > V[A]:
        print(1)
        return
    
    x = V.count(V[A])
    ans = 0
    if mx == V[A]:
        for i in range(A, B + 1):
            ans += comb(x, i)
    else:
        y = V[:A].count(V[A])
        ans = comb(x, y)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def comb(n, k):
    return factorial(n) // (factorial(k) * factorial(n-k))
  
if __name__ == '__main__':
    from collections import Counter
    from math import factorial

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

    V.sort(reverse = True)
    max_list = [V[0:A]]
    max = sum(V[0:A]) / A

    for i in range(A+1,B+1):
        a = sum(V[0:i]) / i
        if max <= a:
            max_list.append(V[0:i])
            max = a
    print("{:.6f}".format(max))

    ans = 0
    for x in max_list:
        ans_sub = 1
        try:
            x = Counter(x).most_common()
        except TypeError:
            ans += ans_sub
            continue
        for i in range(len(x)):
            ans_sub *= comb(V.count(x[i][0]),x[i][1])
        ans += ans_sub
    print(int(ans))

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


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

# 価値の降順にソート
V.sort(reverse=True)

# 価値の高い方から A 個 選んだ場合が平均価値最大
sumV = 0
for i in range(A):
    sumV += V[i]
ans1 = sumV/A


# 価値最大の個数
cntV0 = 0
for i in range(N):
    if V[i]==V[0]:
        cntV0 += 1
ans2 = 1
# 価値最大の個数が A より大きいなら
if cntV0 > A:
    ans2 = 0
    for i in range(A,min(cntV0,B)+1):
        tmp = 1
        c = cntV0
        r = i
        # cntV0 より j個 選ぶ選び方
        for j in range(r):
            tmp *= c-j
            tmp //= j+1
        ans2 += tmp
else:
    cntV1,cntV2 = 0,0
    # A 番目の価値と同じ個数, それより価値が大きな個数を数える
    for i in range(N):
        if V[i]==V[A-1]:
            cntV1 += 1
        elif V[i]>V[A-1]:
            cntV2 += 1
    # 合わせて A より大きければ, 複数の組み合わせがありうる
    if cntV1+cntV2 > A:
        c = cntV1
        r = A-cntV2
        # A 番目の価値と同じものを, 適切な数選ぶ場合の数を計算する
        for i in range(r):
            ans2 *= c-i
            ans2 //= i+1


print(ans1, ans2)

Submission status: Accepted

Solution code:
import statistics
import math

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

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

result = 0
mean_min = statistics.mean(v[0:a])
for i in range(a,b+1):
  st_mean = statistics.mean(v[0:i])
  if mean_min == st_mean:
    v_n = v.count(v[a])
    v_r = v[0:i].count(v[a])
    result += combinations_count(v_n,v_r)
  else:
    break
print(mean_min)
print(result)

Submission status: Accepted

Solution code:
def ncr(n, r):
  if n < r:
    return 0
  res = 1
  for i in range(1, n + 1):
    res *= i
  for i in range(1, r + 1):
    res //= i
  for i in range(1, n - r + 1):
    res //= i
  return res
n, a, b = map(int, input().split())
v = sorted(list(map(int, input().split())), reverse=True)
print(sum(v[0:a]) / a)
if v[0] == v[a - 1]:
  c = v.count(v[0])
  ans = 0
  for i in range(a, b + 1):
    ans += ncr(c, i)
  print(ans)
else:
  k = v.count(v[a - 1])
  r = v[0:a].count(v[a - 1])
  print(ncr(k, r))

Submission status: Accepted

Solution code:
import math


def check(m, A, V):
    # whether we can get `m` for mean of values
    cnt, x = 0, 0
    for v in V[:A]:
        x += v - m
        cnt += 1
    return x >= 0


def comb(n, k):
    if k > n - k:
        return comb(n, n - k)
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)


def main():
    N, A, B = list(map(int, input().split(' ')))
    V = list(map(int, input().split(' ')))
    V.sort(reverse=True)
    # calculate max average value by binary search
    eps = 10 ** (-15)
    ok, ng = 0, 10 ** 16
    while (ng - ok) / ng > eps:
        mid = (ok + ng) / 2
        if check(mid, A, V):
            ok = mid
        else:
            ng = mid
    ans_v = ok
    # calculate pattern number
    min_target_v = V[A - 1]
    target_v_cnt = sum([1 if v == min_target_v else 0 for v in V])
    selected_target_v_cnt = sum([1 if v == min_target_v else 0 for v in V[:A]])
    ans_pattern = comb(target_v_cnt, selected_target_v_cnt)
    if V[0] == min_target_v:  # V[0] == ... == V[A - 1]
        # the average does not change if we add another item with min_target_v
        for i in range(1, B - A + 1):
            if target_v_cnt < selected_target_v_cnt + i:
                break
            ans_pattern += comb(target_v_cnt, selected_target_v_cnt + i)
    # answer
    print(ans_v)
    print(ans_pattern)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,A,B = LI()
    v = LI()
    d = {}
    for x in v:
        if x in d: d[x] += 1
        else: d[x] = 1

    dx = sorted(d.items(),reverse=True)

    ans = 0.0
    cnt = 0
    for k in range(A,B+1):
        c = 0
        i = 0
        x = 0
        while c < k:
            c += dx[i][1]
            if c >= k:
                x += dx[i][0] * (dx[i][1] - (c-k))
                cnt_i = math.factorial(dx[i][1]) // math.factorial(c-k) // math.factorial(dx[i][1] - (c-k))
                av = round(x/k,7)
                if av > ans:
                    ans = av
                    cnt = cnt_i
                elif av == ans:
                    cnt += cnt_i
            else:
                x += dx[i][0] * dx[i][1]
            i += 1
    print(ans)
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
from math import factorial
def comb(n, k):
    return factorial(n) // (factorial(k) * factorial(n-k))
n, a, b = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse=True)
cnt = Counter(v)
print(sum(v[:a]) / a)

if v[0] == v[a-1]:
    x = cnt[v[0]]
    ans = 0
    for i in range(a, min(x, b)+1):
        ans += comb(x, i)

    print(ans)

else:
    x = cnt[v[a-1]]
    for i in range(a):
        if v[i] == v[a-1]:
            y = i
            break

    print(comb(x, a-y))

Submission status: Accepted

Solution code:
f_memo = {0:1, 1:1}
def f(x):
  global f_memo
  if x in f_memo:
    return f_memo[x]
  else:
    res = x * f(x-1)
    f_memo[x] = res
    return res

comb_memo = {}
def comb(n, r):
  global comb_memo
  if (n, r) in comb_memo:
    return comb_memo[(n, r)]
  else:
    a = f(n)
    b = f(n-r)
    c = f(r)
    res = a // b // c
    comb_memo[(n, r)] = res
    return res


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

mu = sum(v[:A]) / A
R = A-1
for i in range(A, N):
  if v[i] == mu:
    R = i
  else:
    break

R += 1
ans = 0
if R > A:
  for i in range(A, B+1):
    if i > R:
      break
    ans += comb(R, i)
else:
  min_v = v[A-1]
  n = v.count(min_v)
  need = v[:A].count(min_v)
  ans += comb(n, need)

print(mu)
print(ans)

Submission status: Accepted

Solution code:
comb_memo = {}
def comb(n, r):
  global comb_memo
  if (n, r) in comb_memo:
    return comb_memo[(n, r)]
  else:
    r = min(r, n-r)
    res = 1
    for _ in range(r):
      res *= n
      n -= 1
    for i in range(1, r+1):
      res //= i
    comb_memo[(n, r)] = res
    comb_memo[(n, n-r)] = res
    return res

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

mu = sum(v[:A]) / A
ans = 0
if v[0] == mu:
  R = v.count(v[0])
  for i in range(A, B+1):
    if i > R:
      break
    ans += comb(R, i)
else:
  min_v = v[A-1]
  n = v.count(min_v)
  need = v[:A].count(min_v)
  ans += comb(n, need)

print(mu)
print(ans)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    class Pascal:
        def __init__(self, num):
            self.n = num
            self.pascal = [[1] * (i+1) for i in range(num+1)]
            for i in range(2, num+1):    # i 段目 iC0 ... iCi
                for j in range(1, i):
                    self.pascal[i][j] = self.pascal[i-1][j-1] + self.pascal[i-1][j]
        
        def comb(self, a, b):
            return self.pascal[a][b]

    
    n, a, b = mi()
    value = lmi()
    value.sort(reverse=True)

    first_choice = value[:a]
    max_avg = sum(first_choice) / a
    print(max_avg)

    i = a - 1
    while i > 0 and first_choice[i-1] == first_choice[-1]:
        i -= 1
    j = a - 1
    while j < n - 1 and value[j+1] == first_choice[-1]:
        j += 1
    # value[i]...value[j] は first_choice[-1] と一致している

    p = Pascal(51)
    ans = 0
    if i == 0:
        # j+1 C x (x = a to min(b, j+1))
        for k in range(a, min(b + 1, j + 2)):
            ans += p.comb(j + 1, k)
        print(ans)
    else:
        # j-i+1 C a-i
        print(p.comb(j - i + 1, a - i))




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
from fractions  import gcd

input=sys.stdin.readline
n,a,b=map(int,input().split())
v=list(map(int,input().split()))
v.sort(reverse=True)
ans=sum(v[:a])/a
print(ans)
res=0
r1=r2=0
def comb(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

if v[a-1]==v[0]:
    for i in v:
        if i==v[0]:
            r2+=1
    for j in range(a,b+1):
        if j>r2:
            break
        res+=comb(r2,j)
    print(res)
else:   
    f=False
    first=0
    for i in range(n):
        if v[i]==v[a-1]:
            r1+=1
            if not f:
                first=i
            f=True
        elif v[i]<v[a-1]:
            break
    numa=a-first
    res+=comb(r1,numa)
    print(res)

Submission status: Accepted

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

def VI(N, init=0):
  return [init for _ in range(N)]
def VVI(N, M, init=0):
  return [[init for _ in range(M)] for _ in range(N)]

def VD(N, init=0.0):
  return [init for _ in range(N)]
def VVD(N, M, init=0.0):
  return [[init for _ in range(M)] for _ in range(N)]

def Decimal(x):
  print("{0:.10f}".format(x))

class Pair:
  def __init__(self, x, y):
    self.first = x
    self.second = y

  def __repr__(self):
    return '{0} {1}'.format(self.first, self.second)

  def __lt__(self, pi):
    return self.first < pi.second

def POW(x, n):
  ret = 1
  while n:
    if n&1:
      ret *= x
    x *= x
    n >>= 1
  return ret

class EratosthenesSieve:
  def __init__(self, N=1):
    self.f = [0 for _ in range(N+1)]
    self.f[0] = self.f[1] = -1
    self.primes = []
    for i in range(2, N+1):
      if self.f[i]:
        continue
      self.primes.append(i)
      self.f[i] = i
      for j in range(i*i, N+1, i):
        if not self.f[j]:
          self.f[j] = i # jの最小の素因数

  def isPrime(self, x):
    return self.f[x] == x

  # 素因数分解
  def factorList(self, x):
    res = []
    while x != 1:
      res.append(self.f[x])
      x //= self.f[x]
    return res

  # 素因数分解(<素因数, 次数>)
  def factor(self, x):
    fl = self.factorList(x)
    if len(fl) == 0:
      return []

    ret = [Pair(fl[0], 0)]

    for p in fl:
      if ret[len(ret)-1].first == p:
        ret[len(ret)-1].second += 1
      else:
        ret.append(Pair(p, 1))

    return ret

si = EratosthenesSieve(51)

def comb(n, r):
  r = min(r, n-r)
  tmp = [0 for _ in range(51)]
  for i in range(n-r+1, n+1):
    f = si.factor(i)
    for pi in f:
      tmp[pi.first] += pi.second

  for i in range(2, r+1):
    f = si.factor(i)
    for pi in f:
      tmp[pi.first] -= pi.second

  ret = 1
  for i in range(51):
    ret *= POW(i, tmp[i])

  return ret

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

tot = 0
for i in range(A):
  tot += V[i]

avg = float(tot)/float(A)

l = 0
r = 0
for i in range(N):
  if V[i] == V[A-1]:
    l = i
    break

for i in range(N-1, -1, -1):
  if V[i] == V[A-1]:
    r = i
    break

a_num = r-l+1
aa_num = A-1-l+1

ans = 0
if V[0] == V[A-1]:
  for i in range(A, B+1):
    if i > a_num:
      break
    ans += comb(a_num, i)
else:
  ans += comb(a_num, aa_num)

Decimal(avg)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import math

def comb(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()))

d = defaultdict(int)
for i in range(n):
    d[v[i]] += 1

keys = list(d.keys())
keys.sort(reverse=True)
cnt = 0
kind = 0
s = 0
for i in range(len(keys)):
    k = keys[i]
    kind += 1
    if cnt+d[k] < a:
        cnt += d[k]
        s += k*d[k]
    else:
        s += k*(a-cnt)
        break
print(s/a)
if kind > 1:
    print(comb(d[keys[kind-1]], a-cnt))
else:
    ans = 0
    for i in range(a, b+1):
        if d[keys[0]] < i:
            break
        ans += comb(d[keys[0]], i)
    print(ans)

Submission status: Accepted

Solution code:
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)]

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

"""
if len(set(v)) == 1:
    print(1)
    print(1125899906842623)
    exit()
"""

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

if len(set(v[:A]))==1:
    ans = 0
    c = v.count(v[0])
    for i in range(A,B+1):
        if i <= c:
            ans += cmb(c,i)
    print(ans)
    exit()

mi = min(v[:A])
n = v[:A].count(mi)
m = v.count(mi)
print(cmb(m,n))

Submission status: Accepted

Solution code:
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)]

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

if len(set(v)) == 1:
    print(1)
    print(1125899906842623)
    exit()

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

if len(set(v[:A]))==1:
    ans = 0
    c = v.count(v[0])
    for i in range(A,B+1):
        if i <= c:
            ans += cmb(c,i)
    print(ans)
    exit()

mi = min(v[:A])
n = v[:A].count(mi)
m = v.count(mi)
print(cmb(m,n))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**18+3
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,A,B=map(int,input().split())
    v=list(map(int,input().split()))
    v.sort()
    ans=0
    for i in range(A,B+1):
        ans=max(ans,sum(v[-i:])/i)
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
        fac[0]=fac[1]=1
        finv[0]=finv[1]=1
        inv[1]=1
        for i in range(2,(n+1)):
            fac[i]=fac[i-1]*i%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(N,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    ans2=0
    for i in range(A,B+1):
        if sum(v[-i:])/i==ans:
            x=v[-i]
            n=bisect_right(v,x)-bisect_left(v,x)
            m=bisect_right(v,x)-(N-i)
            ans2+=COM(n,m)
    print(ans)
    print(ans2)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
from operator import mul
from functools import reduce

N,A,B = map(int, input().split())
V = list(map(int, input().split()))
VV = sorted(V,reverse = True)
ave = 0
ml = []

for i in range(A,B + 1):
  avet = sum(VV[:i]) / i
  if avet >= ave:
    ml.append(i)
    ave = max(ave,avet)
  else:
    break

dic = collections.Counter(V)
#print(dic,ml)

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

res = 0

for j in ml:
  r = dic[VV[j - 1]]
  rr = VV.index(VV[j - 1])
  res += cmb(r,j - rr)

print(ave)
print(res)

Submission status: Accepted

Solution code:
from collections import Counter
from bisect import bisect_right as br
n,a,b = map(int,input().split())
v = list(map(int,input().split()))
count = Counter(v)
v.sort()
c = 0

ans = sum(v[-a:])

def pascla(low):
    list=[[1],[1,1]]
    if low==0 or low==1:
        return list
    while low-len(list):   
        for i in list[-1:]:
            counter = len(i)-1
            locallist = []
            for j in range(counter):
                locallist.append(i[counter-1] + i[counter])
                counter-=1
            locallist.append(1)
            locallist.insert(0,1)
            list.append(locallist)           

    return list

comb = pascla(51)
for i in range(a,b+1):
    if sum(v[-i:])*a == ans*i:
        m = v[-i]
        if count[m] == 1:
            c += 1
        else:
            index = br(v,m)
            c += comb[count[m]][index-(n-i)]
print(ans/a)
print(int(c))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

N, A, B = map(int, input().split())
V = list(map(int, input().split()))
V.sort(reverse=True)
mi = 10**18
dic = defaultdict(int)
dic2 = defaultdict(int)
tot = 0
for i,a in enumerate(V):
    if i < A:
        tot += a
        dic2[a] += 1
        if a < mi:
            mi = a
    dic[a] += 1
if len(dic2) == 1:
    ans = 0
    for i in range(A, B+1):
        ans += comb(dic[mi], i)
else:
    ans = comb(dic[mi], dic2[mi])
print(tot/A)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

# Combination
MOD = 10**17+3
MAX = 2*10**5
fac = [1,1] + [0]*MAX
finv = [1,1] + [0]*MAX
inv = [0,1] + [0]*MAX
for i in range(2,MAX+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def comb(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

N, A, B = map(int, input().split())
V = list(map(int, input().split()))
V.sort(reverse=True)
arr = V[:A]
se = set()
mi = 10**18
dic2 = defaultdict(int)
tot = 0
for a in arr:
    tot += a
    dic2[a] += 1
    se.add(a)
    if a < mi:
        mi = a
dic = defaultdict(int)
for v in V:
    dic[v] += 1
if len(se) == 1:
    ans = 0
    for i in range(A, B+1):
        ans += comb(dic[mi], i)
else:
    ans = comb(dic[mi], dic2[mi])
print(tot/A)
print(ans)

Submission status: Accepted

Solution code:
n,a,b =map(int, input().split())
al = list(map(int, input().split()))
newal = sorted(al,reverse = True)
ave = 0
ml = []
for i in range(a,b+1):
    avet = sum(newal[:i])/i
    if avet >= ave:
        ml.append(i)
        ave = max(ave,avet)
print(ave)

import collections
c = collections.Counter(al)

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

res = 0
for j in ml:
    r = c[newal[j-1]]
    rr = newal.index(newal[j-1])
    res += cmb(r,j-rr)
print(res)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
v=[int(i) for i in input().split()]
v.sort(reverse=True)
m=v[a-1]
mm=v.count(m)
cnt=0
for i in range(n):
    if v[i]>m:
        cnt+=1
    else:
        break

def fact(n):
    if n==0 or n==-1:
        return 1
    return fact(n-1)*n
def comb(n,k):
    return fact(n)//fact(n-k)//fact(k)

    
ans=0
#print('mm,cnt',mm,cnt)
for i in range(min(mm+cnt-a,b-a+cnt)+1):
    ans+=comb(mm,a-cnt+i)
    #print(i,ans)
if m!=v[0]:
    ans=comb(mm,a-cnt)
print(sum(v[0:a])/a)
print(ans)

Submission status: Accepted

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

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

for i in range(1,N+1):
  dp[i][0]=(0,1)
  for j in range(1,i+1):
    dp[i][j]=dp[i-1][j]
    if dp[i-1][j-1][0]+vlist[i-1]>dp[i][j][0]:
      dp[i][j]=(dp[i-1][j-1][0]+vlist[i-1],dp[i-1][j-1][1])
    elif dp[i-1][j-1][0]+vlist[i-1]==dp[i][j][0]:
      dp[i][j]=(dp[i][j][0],dp[i][j][1]+dp[i-1][j-1][1])
#print(dp)

max_value_avg=0
for j in range(A,B+1):
  #print(j,dp[N][j])
  value_avg=dp[N][j][0]/j
  max_value_avg=max(max_value_avg,value_avg)

answer=0
for j in range(A,B+1):
  value_avg=dp[N][j][0]/j
  if value_avg==max_value_avg:
    answer+=dp[N][j][1]
  
print(max_value_avg)
print(answer)