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: Wrong Answer

Solution code:
import statistics
import math
N, A, B = map(int, input().split())
v = [int(x) for x in input().split()]
v.sort()

base = v[N-A:]
rem = v[:N-A]
mean_max = statistics.mean(base)
cnb = 0
while mean_max == statistics.mean(base) and len(base) <= B:
    same = base.count(base[0])
    extra = rem.count(base[0])
    cnb += math.factorial(same+extra)/math.factorial(same)/math.factorial(extra)
    if len(rem) == 0: break
    base.append(rem[len(rem)-1])
    rem.pop()
print(mean_max)
print(math.floor(cnb))

Submission status: Wrong Answer

Solution code:
import statistics
import math
N, A, B = map(int, input().split())
v = [int(x) for x in input().split()]
v.sort()

base = v[N-A:]
rem = v[:N-A]
mean_max = statistics.mean(base)
cnb = 0
while mean_max == statistics.mean(base):
    same = base.count(base[0])
    extra = rem.count(base[0])
    cnb += math.factorial(same+extra)/math.factorial(same)/math.factorial(extra)
    if len(rem) == 0: break
    base.append(rem[len(rem)-1])
    rem.pop()
print(mean_max)
print(math.floor(cnb))

Submission status: Wrong Answer

Solution code:
import statistics
import math
N, A, B = map(int, input().split())
v = [int(x) for x in input().split()]
v.sort()

base = v[N-A:]
rem = v[:N-A]
mean_max = statistics.mean(base)
cnb = 0
while mean_max == statistics.mean(base) and len(rem) != 0:
    same = base.count(base[0])
    extra = rem.count(base[0])
    cnb += math.factorial(same+extra)/math.factorial(same)/math.factorial(extra)
    base.append(rem[len(rem)-1])
    rem.pop()
print(mean_max)
print(math.floor(cnb))

Submission status: Wrong Answer

Solution code:
import statistics
import math
N, A, B = map(int, input().split())
v = [int(x) for x in input().split()]
v.sort()

base = v[N-A:]
mean_max = statistics.mean(base)
rem = v[:N-A]
same = 0
while rem[len(rem)-1]*A == sum(base):
    rem.pop()
    same += 1
    if len(rem) == N - B: break
cnb = 0
for i in range(A, min(same+A,B)+1):
    cnb += math.factorial(same+A)/math.factorial(same+A-i)/math.factorial(i)
print(mean_max)
print(1 if same == 0 else cnb)

Submission status: Wrong Answer

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

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

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

print(ans)

Submission status: Wrong Answer

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

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

num = V[a]
m = V.count(num)
k = V[:a].count(num)
#print(m, k, a)
if a != k:
    ans = factorial(m) // (factorial(k) * factorial(m - k))
else:
    #2**n - 1
    ans = 2**m - 1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import prod

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

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

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

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

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

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

ans=prod(res)

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

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

Submission status: Wrong Answer

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def fact(n):
    answer = 1
    for i in range(1, n+1):
        answer *= i
    return answer


def solve():
    N, A, B = read_ints()
    V = read_ints()
    if A > B:
        print(0)
        print(0)
        return
    V.sort(reverse=True)
    S = sum(V[:A])

    choose = 0
    count = 0
    for i, a in enumerate(V):
        if a == V[A-1]:
            if i < A:
                choose += 1
            count += 1
    print(S/A)
    print(fact(count)//fact(choose)//fact(count-choose))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def fact(n):
    answer = 1
    for i in range(1, n+1):
        answer *= i
    return answer


def solve():
    N, A, B = read_ints()
    V = read_ints()
    V.sort(reverse=True)
    S = sum(V[:A])

    choose = 0
    count = 0
    for i, a in enumerate(V):
        if a == V[A-1]:
            if i < A:
                choose += 1
            count += 1
    print(S/A)
    print(fact(count)//fact(choose)//fact(count-choose))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import math

N,A,B = map(int,input().split())
vs = sorted(map(int,input().split()))
print(sum(vs[-A:])/A)
rt = 0
ina = vs.count(vs[-A])
i = A
while i <= B:
  if vs[-1] == vs[-i]:
    inb = vs[-i:].count(vs[-A])
    rt += math.factorial(ina)//(math.factorial(inb) * math.factorial(ina-inb))
    i+=1
  else:
    break
  

print(rt)

Submission status: Wrong Answer

Solution code:
import math

N,A,B = map(int,input().split())
vs = sorted(map(int,input().split()))
print(sum(vs[-A:])/A)
rt = 0
ina = vs.count(vs[-A])
for i in range(A,B+1):
  inb = vs[-i:].count(vs[-A])
  rt += math.factorial(ina)//(math.factorial(inb) * math.factorial(ina-inb))
  if vs[-1] != vs[-i]:
    break
print(rt)

Submission status: Wrong Answer

Solution code:
import math

N,A,B = map(int,input().split())
vs = sorted(map(int,input().split()))
print(sum(vs[-A:])/A)
rt = 0
ina = vs.count(vs[-A])
for i in range(A,B+1):
  if vs[-A] != vs[-i]:
    break
  else:
    inb = vs[-i:].count(vs[-A])
    rt += math.factorial(ina)//(math.factorial(inb) * math.factorial(ina-inb))
print(rt)

Submission status: Wrong Answer

Solution code:
import math

N,A,_ = map(int,input().split())
vs = sorted(map(int,input().split()))
print(sum(vs[-A:])/A)
ina = vs.count(vs[-A])
inb = vs[-A:].count(vs[-A])

print(math.factorial(ina)//(math.factorial(inb) * math.factorial(ina-inb)))

Submission status: Wrong Answer

Solution code:
import math

N,A,_ = map(int,input().split())
vs = sorted(map(int,input().split()))
print(sum(vs[-A:])/A)
print(math.factorial(vs.count(vs[-A]))//math.factorial(vs[-A:].count(vs[-A])))

Submission status: Wrong Answer

Solution code:

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

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

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

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


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

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



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

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

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

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

    if r == 0:
        return 1

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

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

print(ans)

Submission status: Wrong Answer

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

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

print(ans/(10**18))
print(int(count[ans_2]))

Submission status: Wrong Answer

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

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

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

print(ans/(10**18))
print(int(count[ans_2]))

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

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


show_flg=False
show_flg=True

ans=0


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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

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


show_flg=False
show_flg=True

ans=0


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

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

Submission status: Wrong Answer

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

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

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

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


show_flg=False
show_flg=True

ans=0


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

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

Submission status: Wrong Answer

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

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

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

print(ans)
print(int(count[int(ans*2)]))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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