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


def resolve():
    n, a, b = map(int, input().split())
    v = list(map(int, input().split()))
    v.sort(reverse=True)
    max_ave = sum(v[:a]) / a
    ath = v[a - 1]
    num_ath = v.count(ath)
    large = len([vi for vi in v if vi > ath])
    if v[0] == ath:
        ans = 0
        for i in range(a - large, min(b - large, num_ath) + 1):
            ans += combi(num_ath, i)
    else:
        ans = combi(num_ath, a - large)
    print(max_ave)
    print(ans)


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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def comb(n,m):
    ans = 1
    if n==0 or m == 0:
        return 0
    else:
        for i in range(m):
            j = n-i
            ans *= j
        for i in range(1,m+1):
            ans //= i
        return ans
    
def main():
    import sys
    input = sys.stdin.readline
    N,A,B = map(int,input().split())
    V = list(map(int,input().split()))
    #N,A,B = 50,1,50
    #V = [1]*50
    V = sorted(V)[::-1]
    maxAv = sum(V[:A])/A
    maxB = A
    for i in range(A+1,B+1):
        tmp = sum(V[:i])/i
        if maxAv == tmp:
            maxB = i
    count = 0
    
    C = []
    now = V[0]
    c = 0
    for i in V:
        if now == i:
            c += 1
        else:
            C.append([now,c])
            now = i
            c = 1
    if c != 0:
      C.append([now,c])
    C = sorted(C,key=lambda a: a[0])[::-1]
    for i in range(A,maxB+1):
        pretmp = 0
        tmp = 0
        now = 0
        for j in C:
            if tmp >= i:
                break
            now = j[1]
            pretmp = tmp
            tmp += now
        count += comb(now, i-pretmp)
    #print(C)
    print(maxAv)    
    print(count)
            
    
main()

Submission status: Accepted

Solution code:

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

V.sort(reverse=True)

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

D = {}
Da = {}

for i in range(n):
    try:
        D[V[i]] += 1
    except:
        D[V[i]] = 1

for i in range(a):
    try:
        Da[V[i]] += 1
    except:
        Da[V[i]] = 1



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

#print(C(5,3))

if len(set(V[:a])) > 1:
    ans = 1
    for i in set(V[:a]):
        ans *= C(D[i], Da[i])

else:
    ans = 0
    for i in range(a, b+1):
        #print(D[V[0]], i)
        ans += C(D[V[0]], i)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def comb(n, r):
    fact = 1
    for i in range(n - r + 1, n + 1):
        fact = fact * i
    divisor = 1
    for j in range(1, r + 1):
        divisor = divisor * j


    return fact // divisor



n, a, b = LI()
value = sorted(LI(), reverse=True)
m = value[a-1]
ans = 0
print(sum(value[:a]) / a)
left_cnt = value[:a].count(m)
total_cnt = value.count(m)
if left_cnt != a:
    print(comb(total_cnt, left_cnt))
else:
    for k in range(a, min(total_cnt, b) + 1):
        ans += comb(total_cnt, k)
    print(ans)

Submission status: Accepted

Solution code:
from scipy.misc import comb
N,A,B,*V=map(int,open(0).read().split());d={}
for v in V:d[v]=d.get(v,0)+1
l=sorted(d.items(),key=lambda x:x[0])[::-1]
if l[0][1]>A:
 print(l[0][0])
 print(int(sum(comb(l[0][1],i,exact=1)for i in range(A,B+1))))
else:
 s=0;c=A
 for k,v in l:
  if v<c:s+=k*v;c-=v
  else:print((s+k*c)/A);print(int(comb(v,c,exact=1)));break

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
vs = list(map(int, input().split()))
vs.sort(reverse=True)
#print(vs)
r = sum(vs[:A])/A
print(r)
vA = vs[A-1]
I = vs.index(vA)
C = vs.count(vA)
#print(I, C)
if I != 0:
  # C_{C}_{A-I}
  r = 1
  for i in range(1, A-I+1):
    r = r*(C-i+1)//i
  print(r)
else:
  rs = []
  for n in range(A, B+1):
    # C_{C}_{N-I}
    if n-I < 0 or n-I > C:
      continue
    r = 1
    for i in range(1, n-I+1):
      r = r*(C-i+1)//i
    #print(C, n-I, r)
    rs.append(r)
  #print(rs)
  r = sum(rs)
  print(r)

Submission status: Accepted

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

c = Counter(v)
ans_num = sum(v[:A]) / A
ans_cnt = 0

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

num = v[A-1]
num_all = c[num]
cc = Counter(v[:A])
tmp = cc[num]

for i in range(A-1, B):
    last = v[i]
    if i != A-1:
        if last != v[0]:
            break
    ans_cnt += cmb(num_all, (i+1)-(A-tmp))


print(ans_num)
print(ans_cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict,Counter

def nck(n, k):
    ret = 1
    for i in range(min(n - k, k)):
        ret *= (n - i)
        ret /= (i + 1)
    return ret


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

    v = sorted(v, reverse=True)
    d = Counter(v)
    value = 0
    t = 0
    for i in range(a):
        value += v[i]
        if i == a - 1:
            t = v[i]
    print(value / a)

    c = 0
    for i in range(n):
        if v[i] == t:
            break
        c += d[v[i]]

    ans = 0
    if d[v[0]] > a:
        for i in range(a, min(b,d[v[0]])+1):
            ans += nck(d[v[0]], i)
        print(int(ans))
    else:
        print(int(nck(d[t], a - c)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import functools
from heapq import*
from collections import deque
import collections
import math
from collections import defaultdict,Counter
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


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)

    # divisors.sort()
    return divisors


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


def modinv(a, mod):
    return modpow(a, mod - 2, mod)


def cnk(a, b):
    MOD = 10**9+7
    ret = 1
    for i in range(b):
        ret *= (a-i)
        ret %= MOD
        ret = ret * modinv(i+1, MOD) % MOD
    return ret


def Dijkstra(n, start, e):
    # input parm e
    # e = [[]for i in range(n)]
    # e[x].append([y, 1])
    # e[y].append([x, 1])
    n += 10

    d = [float("inf") for i in range(n)]
    d[start] = 0

    pathnum = [0 for i in range(n)]
    pathnum[start] = 1

    visited = [False for i in range(n)]
    q = []
    heappush(q, (0, start))
    while len(q):
        now_distance, v = heappop(q)
        if visited[v]:
            continue
        visited[v] = True
        for next_v, next_distance in e[v]:
            if visited[next_v]:
                continue
            dd = now_distance + next_distance
            if d[next_v] > dd:
                d[next_v] = dd
                heappush(q, (dd, next_v))
            if d[next_v] == dd:
                pathnum[next_v] += pathnum[v]
                pathnum[next_v] %= MOD

    return d, pathnum


def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


class UnionFind:
    def __init__(self, n):
        self.sz = [-1 for i in range(n)]

    # 検索
    def find(self, x):
        if self.sz[x] < 0:
            return x
        else:
            self.sz[x] = self.find(self.sz[x])
            return self.sz[x]

    # 併合

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.sz[x] > self.sz[y]:
            x, y = y, x
        self.sz[x] += self.sz[y]
        self.sz[y] = x

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xが含まれている集合のサイズを求める
    def size(self, x):
        return -self.sz[self.find(x)]


class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

#
# kruskal
#


@functools.lru_cache(maxsize=None)
class UNION_FIND(object):
    def __init__(self, n):
        self.parent = [-1 for i in range(n)]

    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def size(self, x):
        return -self.parent[self.root(x)]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.size(x) < self.size(y):
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True


def compute_mst_kruskal(max_v, edges):
    edges.sort(key=lambda x: x[2], reverse=1)
    uf = UNION_FIND(max_v)
    mst = []
    for (a, b, c, d) in edges:
        if uf.root(a-1) != uf.root(b-1):
            uf.union(a-1, b-1)
            mst += [d+1]
    return mst


# max_v, max_e = map(int, input().split())
# edges = []
# for i in range(max_e):
#     a, b, c = map(int, input().split())
#     heappush(edges, (a, b, c, i))

# mst = compute_mst_kruskal(max_v, edges)
# mst.sort()
# for i in mst:
#   print(i)

#
# Dinic
#

class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

# V, E, r = map(int, input().split())
# edges = []
# for i in range(E):
#     s, t, d = map(int, input().split())
#     edges.append([s, t, d])

# d = BellmanFord(edges, V, r)
# if d == -1:
#     print("NEGATIVE CYCLE")
#     exit()

# for i in range(V):
#     if d[i] == float("inf"):
#         print("INF")
#     else:
#         print(d[i])


ok = [False for i in range(2505)]


def Bellmanford(edges, n, s):
    d = [float("inf") for i in range(n)]
    d[s] = 0

    for i in range(n):
        for x, y, z in edges:
            if not ok[x] or not ok[y]:  # 0からn-1へ到達できない点は無視
                continue
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                if i == n - 1:
                    print(-1)
                    exit()
    print(max(0, -d[n - 1]))


def nck(n, k):
    ret = 1
    for i in range(min(n - k, k)):
        ret *= (n - i)
        ret /= (i + 1)
    return ret


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

    v = sorted(v, reverse=True)
    # d = defaultdict(int)
    # for i in range(n):
    #     d[v[i]] += 1
    d = Counter(v)
    value = 0
    t = 0
    for i in range(a):
        value += v[i]
        if i == a - 1:
            t = v[i]
    print(value / a)

    c = 0
    for i in range(n):
        if v[i] == t:
            break
        c += d[v[i]]

    ans = 0
    if d[v[0]] > a:
        for i in range(a, min(b,d[v[0]])+1):
            ans += nck(d[v[0]], i)
        print(int(ans))
    else:
        print(int(nck(d[t], a - c)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import functools
from heapq import*
from collections import deque
import collections
import math
from collections import defaultdict
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


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)

    # divisors.sort()
    return divisors


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


def modinv(a, mod):
    return modpow(a, mod - 2, mod)


def cnk(a, b):
    MOD = 10**9+7
    ret = 1
    for i in range(b):
        ret *= (a-i)
        ret %= MOD
        ret = ret * modinv(i+1, MOD) % MOD
    return ret


def Dijkstra(n, start, e):
    # input parm e
    # e = [[]for i in range(n)]
    # e[x].append([y, 1])
    # e[y].append([x, 1])
    n += 10

    d = [float("inf") for i in range(n)]
    d[start] = 0

    pathnum = [0 for i in range(n)]
    pathnum[start] = 1

    visited = [False for i in range(n)]
    q = []
    heappush(q, (0, start))
    while len(q):
        now_distance, v = heappop(q)
        if visited[v]:
            continue
        visited[v] = True
        for next_v, next_distance in e[v]:
            if visited[next_v]:
                continue
            dd = now_distance + next_distance
            if d[next_v] > dd:
                d[next_v] = dd
                heappush(q, (dd, next_v))
            if d[next_v] == dd:
                pathnum[next_v] += pathnum[v]
                pathnum[next_v] %= MOD

    return d, pathnum


def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


class UnionFind:
    def __init__(self, n):
        self.sz = [-1 for i in range(n)]

    # 検索
    def find(self, x):
        if self.sz[x] < 0:
            return x
        else:
            self.sz[x] = self.find(self.sz[x])
            return self.sz[x]

    # 併合

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.sz[x] > self.sz[y]:
            x, y = y, x
        self.sz[x] += self.sz[y]
        self.sz[y] = x

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xが含まれている集合のサイズを求める
    def size(self, x):
        return -self.sz[self.find(x)]


class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

#
# kruskal
#


@functools.lru_cache(maxsize=None)
class UNION_FIND(object):
    def __init__(self, n):
        self.parent = [-1 for i in range(n)]

    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def size(self, x):
        return -self.parent[self.root(x)]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.size(x) < self.size(y):
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True


def compute_mst_kruskal(max_v, edges):
    edges.sort(key=lambda x: x[2], reverse=1)
    uf = UNION_FIND(max_v)
    mst = []
    for (a, b, c, d) in edges:
        if uf.root(a-1) != uf.root(b-1):
            uf.union(a-1, b-1)
            mst += [d+1]
    return mst


# max_v, max_e = map(int, input().split())
# edges = []
# for i in range(max_e):
#     a, b, c = map(int, input().split())
#     heappush(edges, (a, b, c, i))

# mst = compute_mst_kruskal(max_v, edges)
# mst.sort()
# for i in mst:
#   print(i)

#
# Dinic
#

class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

# V, E, r = map(int, input().split())
# edges = []
# for i in range(E):
#     s, t, d = map(int, input().split())
#     edges.append([s, t, d])

# d = BellmanFord(edges, V, r)
# if d == -1:
#     print("NEGATIVE CYCLE")
#     exit()

# for i in range(V):
#     if d[i] == float("inf"):
#         print("INF")
#     else:
#         print(d[i])


ok = [False for i in range(2505)]


def Bellmanford(edges, n, s):
    d = [float("inf") for i in range(n)]
    d[s] = 0

    for i in range(n):
        for x, y, z in edges:
            if not ok[x] or not ok[y]:  # 0からn-1へ到達できない点は無視
                continue
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                if i == n - 1:
                    print(-1)
                    exit()
    print(max(0, -d[n - 1]))


def nck(n, k):
    ret = 1
    for i in range(min(n - k, k)):
        ret *= (n - i)
        ret /= (i + 1)
    return ret


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

    v = sorted(v, reverse=True)
    d = defaultdict(int)
    for i in range(n):
        d[v[i]] += 1
    value = 0
    t = 0
    for i in range(a):
        value += v[i]
        if i == a - 1:
            t = v[i]
    print(value / a)

    c = 0
    for i in range(n):
        if v[i] == t:
            break
        c += d[v[i]]

    ans = 0
    if d[v[0]] > a:
        for i in range(a, min(b,d[v[0]])+1):
            ans += nck(d[v[0]], i)
        print(int(ans))
    else:
        print(int(nck(d[t], a - c)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def cmb(n, r):
    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])

    return result

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

data = []
cnt = 0
ans = 0
for i in v:
  data.append(i)
  cnt += 1
  if cnt == A:
    vnum = v.count(i)
    datanum = data.count(i)
    if cnt == datanum:
      for j in range(A,min(B, vnum)+1):
        #print(vnum, j)
        ans += cmb(vnum, j)
      break
    else:
      ans = cmb(vnum, datanum)
      #print(vnum,datanum)
      break
print(sum(data)/len(data))
print(ans)

Submission status: Accepted

Solution code:
def comb(N):
    for i in range(N+1):
        for j in range(i+1):
            if j == 0 or j == i :
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

def main():
    global dp,N
    N, A, B = map(int, input().split())
    v = [int(i) for i in input().split()]
    v.sort(reverse=True)
    dp = [[0 for i in range(N+1)] for j in range(N+1)]
    ans = 0
    for i in range(A):
        ans += v[i]
    ans /= A
    a = 0
    b = 0
    for i in range(N):
        if v[A-1] == v[i]:
            a += 1
            if i < A :
                b += 1
    ans_2 = 0
    comb(N)
    if v[A-1] == v[0]:
        for i in range(A,B+1):
            ans_2 += dp[a][i]
    else:
        ans_2 += dp[a][b]
    print(ans,ans_2)


if __name__ == '__main__':
    main()

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

def main():
    N, A, B = map(int, input().split())
    v = list(map(int, input().split()))
    sort_v = sorted(v, reverse=True)
    sum_A = 0
    for i in range(A):
        sum_A += sort_v[i]
    max_ave_v = sum_A / A

    print(max_ave_v)

    num = sort_v.count(sort_v[0])
    num2 = sort_v.count(sort_v[A-1])
    if sort_v[0] == sort_v[A-1]:
        ans = 0
        for i in range(A,B+1):
            if num >= i:
                ans += cmb(num,i)
    else:
        cnt = 0
        for i in range(A):
            if sort_v[i] == v[A-1]:
                cnt += 1
        ans = cmb(num2, cnt)

    print(ans)
        


main()

Submission status: Accepted

Solution code:
import math
n,a,b=map(int,input().split())
v=list(map(int,input().split()))
v.sort()
v.reverse()
if a==n:
  print(sum(v)/n)
  print(1)
elif v[a-1]!=v[a]:
  print(sum(v[0:a])/a)
  print(1)
elif v[0]!=v[a-1]:
  print(sum(v[0:a])/a)
  ct1=0;ct2=0
  for i in range(n):
    if v[i]==v[a-1]:
      ct1+=1
      if i<a:
        ct2+=1
  print(math.factorial(ct1)//(math.factorial(ct1-ct2)*math.factorial(ct2)))
else:
  print(sum(v[0:a])/a)
  ct1=0;ans=0
  for i in range(n):
    if v[i]==v[a-1]:
      ct1+=1
  for i in range(a,min(ct1+1,b+1)):
    ans+=math.factorial(ct1)//(math.factorial(ct1-i)*math.factorial(i))
  print(ans)

Submission status: Accepted

Solution code:
def main():

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

    if all(v[i] == v[0] for i in range(A)):
        ct = 0
        for i in range(N):
            if v[i] == v[0]:
                ct += 1
        cases = [1]
        for i in range(1, ct+1):
            cases.append(cases[-1]*(ct-i+1)//i)
        return v[0], sum(cases[A:(min(ct, B)+1)])
    else:
        i = 0
        tot = 0
        while i < A:
            tot += v[i]
            i += 1
        max_i = i
        ref = v[i-1]
        ct_used = 0
        for j in range(A):
            if v[j] == ref:
                ct_used += 1

        ct = 0
        for j in range(N):
            if v[j] == ref:
                ct += 1
        cases = 1
        for j in range(1, ct_used+1):
            cases = cases * (ct-j+1)//j
        return tot/max_i, cases

if __name__ == '__main__':
    output = main()
    for v in output:
        print(v)

Submission status: Accepted

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

f = [1]
for i in range(1, 51):
    f.append(f[-1] * i)

def comb(n, k):
    a = f[n]
    b = f[n-k]
    c = f[k]
    bc = b * c
    return a // bc

def solve(N: int, A: int, B: int, v: "List[int]"):
    v = sorted(v, reverse=True)
    print("%.6f" % (sum(v[:A])/A))

    if v[0] != v[A]:
        ret = comb(v.count(v[A-1]), v[:A].count(v[A-1]))
        print(ret)
    else:
        s = 0
        X = v.count(v[0])
        for i in range(A, B+1):
            s += comb(X, i)
        print(s)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    v = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B, v)

if __name__ == '__main__':
    main()