Problem:


Score : 500 points

Problem Statement

We have a sequence of N integers: A_1, A_2, \cdots, A_N.

You can perform the following operation between 0 and K times (inclusive):

Choose two integers i and j such that i \neq j, each between 1 and N (inclusive). Add 1 to A_i and -1 to A_j, possibly producing a negative element.

Compute the maximum possible positive integer that divides every element of A after the operations. Here a positive integer x divides an integer y if and only if there exists an integer z such that y = xz.

Constraints

2 \leq N \leq 500

1 \leq A_i \leq 10^6

0 \leq K \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_{N-1} A_{N}

Output

Print the maximum possible positive integer that divides every element of A after the operations.

Sample Input 1

2 3
8 20

Sample Output 1

7

7 will divide every element of A if, for example, we perform the following operation:

Choose i = 2, j = 1. A becomes (7, 21).

We cannot reach the situation where 8 or greater integer divides every element of A.

Sample Input 2

2 10
3 5

Sample Output 2

8

Consider performing the following five operations:

Choose i = 2, j = 1. A becomes (2, 6).

Choose i = 2, j = 1. A becomes (1, 7).

Choose i = 2, j = 1. A becomes (0, 8).

Choose i = 2, j = 1. A becomes (-1, 9).

Choose i = 1, j = 2. A becomes (0, 8).

Then, 0 = 8 \times 0 and 8 = 8 \times 1, so 8 divides every element of A. We cannot reach the situation where 9 or greater integer divides every element of A.

Sample Input 3

4 5
10 1 2 22

Sample Output 3

7

Sample Input 4

8 7
1 7 5 6 8 2 6 5

Sample Output 4

5



Sample input:
2 3
8 20


Sample output:
7

Submission status: Wrong Answer

Solution code:
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()
    divisors.reverse()
    return divisors

n, k = map(int, input().split())
dat = list(map(int, input().split()))
dat = list(map(abs, dat))
total = sum(dat)
divs = make_divisors(total)
for ds in divs:
    t = 0
    for i in range(n):
        #t += (dat[i] % ds)
        t += min( (dat[i] % ds) , abs((dat[i] % ds) - ds))
        #print(" = {0} ... {1}".format(dat[i], min( (dat[i] % ds) , abs((dat[i] % ds) - ds))))
    #print("end: {0} {1}".format(ds, t))
    if t < (k * 2):
        res = ds
        break
print(ds)

Submission status: Wrong Answer

Solution code:
import math
import sys

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

s=sum(a)
s_factors=[]

l=int(math.sqrt(s))

for i in range(1,l+1):
    if s%i==0:
        s_factors.append(i)
        s_factors.append(s//i)

s_factors.sort()

for f in s_factors[::-1]:
    b=[a[i]%f for i in range(n)]
    c=[f-a[i]%f for i in range(n)]
    
    b.sort()
    c.sort()
    c=c[::-1]

    sb=[0 for i in range(n)]
    sc=[0 for i in range(n)]
    
    sb[0]=b[0]
    sc[0]=c[0]

    for i in range(1,n):
        sb[i]=sb[i-1]+b[i]

    for i in range(1,n):
        sc[i]=sc[i-1]+c[i]

    for i in range(n-1):
        if sb[i]==sc[n-1]-sc[i]:
            if sb[i]<=k:
                print(f)
                sys.exit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
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 solve(N: int, K: int, A: "List[int]"):
    tot = sum(A)
    divs = make_divisors(sum(A))

    m = 1
    for cand in divs[1:]:
        modA = sorted([a % cand for a in A])
        counter = 0
        left = 0
        while left < N and modA[left] == 0:
            left += 1
        right = N-1
        while left < right and counter < K:
            smaller = min(modA[left], cand - modA[right])
            modA[left] -= smaller
            modA[right] += smaller
            counter += smaller
            if modA[left] == 0:
                left += 1
            if modA[right] == cand:
                right -= 1
        if counter < K:
            m = cand

    print(m)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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(reverse=True)
  return divisors

def is_search(div, A, K, N):
  tmp = A.copy()
  for i in range(N):
    tmp[i] = tmp[i] % div
  if sum(tmp) % div > 0:
    #print(div, ': amari')
    return False
  tmp.sort()
  #print(d, tmp)
  
  
  l,r = 0, N-1

  cnt = 0
  while l<r:
    if tmp[l] == 0:
      l += 1
      continue
    if tmp[r] == div:
      r -= 1
      continue
      
    if tmp[l] > div - tmp[r]:
      cnt += div - tmp[r]
      tmp[r] += div - tmp[r]
      tmp[l] -= div - tmp[r]
      r -= 1
    else:
      cnt += tmp[l]
      tmp[r] += tmp[l]
      tmp[l] -= tmp[l]
      l += 1
  #print(cnt,tmp)
  return True if cnt <= K else False
    
    
D = make_divisors(sum(A))

for d in D:
  if is_search(d,A,K,N):
    print(d)
    exit(0)

Submission status: Wrong Answer

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

mint = sum(a)
divs = []
for i in range(1, int(mint ** 0.5) +1):
    if mint % i == 0:
        divs.append(i)
        if i != mint // i:
            divs.append(mint // i)
divs.sort()
divs = divs[::-1]
result = 1
for i in range(len(divs)-1):
    cur = divs[i]
    sums = 0
    divList = []
    for j in range(n):
        numi = a[j] % cur
        sums += numi
        divList.append(numi)
    divList.sort()
    divList = divList[::-1]
    count = sums
    for j in range(n):
        count -= divList[j]
        if count <= sums // 2:
            break
    if count <= k:
        result = cur
        break

print(result)

Submission status: Wrong Answer

Solution code:
from math import sqrt as sq


def divisors(n: int):
    l = int(sq(n) + 1)

    for d in range(1, l):
        if n % d == 0:
            yield d
            yield n // d


def max_gcd(N: int, K: int, A: list)->int:
    S = sum(A)

    ans = 1

    for d in divisors(S):
        ok = sum(min(a % d, d - a % d) for a in A) <= 2*K

        if ok:
            ans = max(ans, d)
    return ans


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    ans = max_gcd(N, K, A)
    print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
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

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

a_sum = sum(a)

if a_sum - max(a) <= k:
    print(a_sum)

else:
    l = make_divisors(sum(a))
    m = len(l)
    ans = 1

    for gcd in l:
        mod = 0
        k_s = 0
        for a_ in a:
            mod_ = a_ % gcd
            k_s += min(mod_, gcd - mod_)
            mod += mod_
        if int(k_s/2) + 1 < k and mod % gcd == 0:
            ans = max(ans, gcd)

    print(ans)

Submission status: Wrong Answer

Solution code:
import math
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :rtype: list of int
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


def can_make(div):
    mods = []
    for a in A:
        mods.append(a % div)
    mods.sort()

    max_k = defaultdict(int)
    max_k[0] = K
    for i in range(len(mods)):
        if mods[i] == 0:
            continue
        next_k = defaultdict(int)
        for c, k in max_k.items():
            if mods[i] <= k:
                nc = (c - mods[i]) % div
                nk = k - mods[i]
                next_k[nc] = max(next_k[nc], nk)
            if div % mods[i] <= k:
                nc = (c + div % mods[i]) % div
                nk = k - div % mods[i]
                next_k[nc] = max(next_k[nc], nk)
        max_k = next_k
    return 0 in max_k.keys()


N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))

# 答えは絶対 A の合計の約数になる
divs = get_divisors(sum(A))
for div in sorted(divs, reverse=True):
    if can_make(div):
        print(div)
        exit()
assert False

Submission status: Wrong Answer

Solution code:
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(reverse = True)
    return divisors

if __name__ == "__main__":
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    max = A[N-1]
    S = sum(A)
    divs = make_divisors(S)
    ans = 1
    D = len(divs)
    for i in range(D):
        d = divs[i]
        B = [a%d for a in A]
        C = [a//d for a in A]
        b = sum(B)
        if K < b//2:
            continue
        else:
            ans = d
            break
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy as dee
n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
b=sum(a)

def d(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()
  divisors.reverse()
  return divisors
def g(a,j,k):
  b=[i%j for i in a]
  c=[abs(j-i%j) for i in a]
  f=set([(0,0)])
  for d,e in zip(b,c):
    h=set()
    for g in f:
      if g[0]+d<=k:
        h.add((g[0]+d,g[1]))
      if g[0]+e<=k:
        h.add((g[0],g[1]+e))
    f=dee(h)
  y={(x,x) for x in range(k,-1,-2)} & f
  return y

c=d(b)
for i in c:
  e=[min(j%i,abs(i-j%i)) for j in a]
  f=sum(e)
  if f<=2*k:
    if g(a,i,k):
      print(i)
      exit()
print(1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
sumA = sum(A)

# 約数の全列挙
def 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(reverse = True)  # ソート
    return divisors

ansList = divisors(sumA)
ans = 1

for div in ansList :
    count = 0
    for a in A :
        b = a % div
        count += min(b, div - b)

    if count <= 2 * K :
        ans = div
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

def factorize(n):
    d = 2
    ans = []
    while d * d <= n:
        e = 0
        while n % d == 0:
            n /= d
            e += 1
        if e:
            ans.append((d,e))
        d += 1 + d%2
    if n > 1:
        ans.append((n, 1))
    return ans

from itertools import product
def divisors(N):
    facs = factorize(N)
    bases, expos = zip(*facs)
    for es in product(*[range(e+1) for e in expos]):
        ans = 1
        for i, e in enumerate(es):
            ans *= bases[i] ** e
        yield ans

def memo(f):
    class memodict(dict):
        def __init__(self, f):
            self.f = f
        def __call__(self, *args):
            return self[args]
        def __missing__(self, key):
            ret = self[key] = self.f(*key)
            return ret
    return memodict(f)

def solve(N, K, A):
    S = sum(A)
    def check(g):
        items = []
        for x in A:
            positive = (-x)%g
            negative = g + x if x < g else x % g
            items.append((positive, negative))
        # does there exist a coloring so that sumpos and sumneg <= K
        @memo
        def dp(i, sumpos, sumneg):
            if sumpos > K or sumneg > K: return False
            if i == len(items): return True
            p, n = items[i]
            return dp(i+1, sumpos + p, sumneg) or dp(i+1, sumpos, sumneg + n)
        return dp(0,0,0)
    
    for g in sorted(divisors(S), reverse = True):
        if check(g): return g
    return 1
        


N, K = map(int, raw_input().split())
A = map(int, raw_input().split())
print solve(N, K, A)

Submission status: Wrong Answer

Solution code:
from math import sqrt
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
div = []
for i in range(1, int(sqrt(s)+1)):
	if s%i == 0:
		if i*i != s:
			div.append(s//i)
		div.append(i)
div.sort(reverse=True)
#print(div)

for d in div:
	b = [x for x in a if x%d != 0]
	if not b:
		print(d)
		break
	plus, minus = 0, 0
	for x in b[:len(b)-1]:
		if x%d == 0:
			continue
		y, z = d-(x%d), x%d
		if plus+y <= minus+z:
			plus += y
		else:
			minus += z
	if max(plus, minus) <= k:
		print(d)
		break

Submission status: Wrong Answer

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

S = sum(A)
M = max(A)

def divisor(n):
    res = []
    rn = int(n**0.5) + 1 
    for i in range(1, rn):
        if n % i == 0:
            res.append(i)
            if i != n / i:
                res.append(int(n / i))
    return sorted(res)

Y = divisor(S)

ans = 1
for i in range(1, len(Y)):
    cnt = 0
    for j in range(N):
        cnt += A[j] % Y[i]
    if cnt <= K*2:
        ans = Y[i]

print(ans)

Submission status: Wrong Answer

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

A_sum = sum(A)

print(A_sum)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
sumA = sum(A)

# 約数の全列挙
def 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(reverse = True)  # ソート
    return divisors

ansList = divisors(sumA)
ans = 1

for div in ansList :
    count = 0
    for a in A :
        count += (a % div)

    if count <= 2 * K :
        ans = div
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = [int(x) for x in input().split()]
A_list = [int(x) for x in input().split()]
ans = 0
for i in range(1, max(A_list)+K):
    mod_A = [A % i for A in A_list]
    if (sum(mod_A) % i == 0):
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
A = sum(a)
fact = []

for i in range(1, int(A**(1/2))+2):
  if A % i == 0:
    fact.append(i)
    fact.append(A//i)
fact.sort(reverse=True)

#print(fact)

for i in fact:
  s = 0
  L = [a[_]%i for _ in range(n)] 
  L.sort(reverse=True)
  #print(L)
  if sum(L[1::]) <= k:
    print(i)
    break

Submission status: Wrong Answer

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

S = sum(A)
M = max(A)

def divisor(n):
    res = []
    rn = int(n**0.5) + 1 
    for i in range(1, rn):
        if n % i == 0:
            res.append(i)
            if i != n / i:
                res.append(int(n / i))
    return sorted(res)

Y = divisor(S)
print(Y)

ans = 1
for i in range(1, len(Y)):
    cnt = 0
    for j in range(N):
        cnt += A[j] % Y[i]
    if cnt <= K*2:
        ans = Y[i]

print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy as dee
n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
b=sum(a)

def d(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()
  divisors.reverse()
  return divisors
def g(a,j,k):
  b=[i%j for i in a]
  c=[abs(j-i%j) for i in a]
  f=set([(0,0)])
  for d,e in zip(b,c):
    h=set()
    for g in f:
      if g[0]+d<=k:
        h.add((g[0]+d,g[1]))
      if g[0]+e<=k:
        h.add((g[0],g[1]+e))
    f=dee(h)
  y={(x,x) for x in range(k,-1,2)} & f
  return y

c=d(b)
for i in c:
  e=[min(j%i,abs(i-j%i)) for j in a]
  f=sum(e)
  if f<=2*k:
    if g(a,i,k):
      print(i)
      exit()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
s=sum(a)

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

l=make_divisors(s)
if n==2:
    f=1
    for i in range(n):
        if a[i]>k:
            f=0
    if f:
        print(l[-1])
    else:
        print(l[-2])
else:
    print(l[-2])

Submission status: Wrong Answer

Solution code:
from math import ceil
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

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

a_sum = sum(a)

if a_sum - max(a) <= k:
    print(a_sum)

else:
    l = make_divisors(sum(a))
    m = len(l)
    ans = 1

    for gcd in l:
        mod = 0
        k_s = 0
        for a_ in a:
            mod_ = a_ % gcd
            k_s += min(mod_, gcd - mod_)
            mod += mod_
        if ceil((k_s+1)/2) < k and mod % gcd == 0:
            ans = max(ans, gcd)

    print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy as dee
n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
b=sum(a)

def d(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()
  divisors.reverse()
  return divisors
def g(a,j,k):
  b=[i%j for i in a]
  c=[abs(j-i%j) for i in a]
  f=set([(0,0)])
  for d,e in zip(b,c):
    h=set()
    for g in f:
      if g[0]+d<=k:
        h.add((g[0]+d,g[1]))
      if g[0]+e<=k:
        h.add((g[0],g[1]+e))
    f=dee(h)
  y={(x,x) for x in range(k,-1 -2)} & f
  return y

c=d(b)
for i in c:
  e=[min(j%i,abs(i-j%i)) for j in a]
  f=sum(e)
  if f<=2*k:
    if g(a,i,k):
      print(i)
      exit()

Submission status: Wrong Answer

Solution code:

N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
# N,K = 500,10**9
# A = [10**6-1 for i in range(N)]
# A = [10**6 for i in range(N)]

# N,K = 8,7
# A = [1,7,5,6,8,2,6,5]

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

dvs = make_divisors(sum(A))

AA = [None for i in range(N)]
ok = 1
for dv in dvs:
    for i in range(N):
        AA[i] = A[i]%dv
    AA = sorted(AA)
    # print(dv, AA)
    l,r = 0,N-1
    while l < N-1 and AA[l] == 0:
        l+=1
    while r > 0 and AA[r] == 0:
        r-=1
    kcnt = 0
    while l<r and r>0 and l<N-1:
        # print(dv, l,r,AA[l],AA[r], kcnt)
        if AA[l] == 0:
            l+=1
        if AA[r]%dv == 0:
            r-=1
        else:
            mv = max(min([AA[l],dv-AA[r],K-kcnt]),0)
            kcnt += mv
            AA[l]-=mv
            AA[r]-=mv
        if mv == 0:
            # print("dame")
            break
    if l>=r:
        ok = max(ok, dv)

# print(len(dvs))

# print("ok")
print(ok)

Submission status: Wrong Answer

Solution code:
import math
a,b=map(int,input().split())
c=list(map(int,input().split()))

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
d=make_divisors(sum(c))

k=0
m=1
for i in d:
  k=0
  for j in c:
    k+=j%i
  if k<=b*2 and k%i==0:
    m=i
print(m)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
# print(N, K, A)

s = sum(A)
factors = []
for i in range(1, s):
    if s % i == 0:
        factors.append(s // i)

def solve(mod, R, K):
    R.sort()
    half = sum(R) // 2
    # print(mod, R, K, half)
    return half <= K
    # s = 0
    # for i in range(len(R)):
    #     r = R[i]
    #     if s + r > half:
    #         R[i] = r - mod
    #     else:
    #         s += r
    # s = sum(R)
    # print(mod, R, K)
    # return s == 0

# print(factors)
for f in factors:
    R = []
    for a in A:
        R.append(a % f)
    # print(f, R)
    found = solve(f, R, K)
    if found:
        print(f)
        exit()

Submission status: Wrong Answer

Solution code:
def getDivisor(x):
    ans = []
    for d in range(1, int(x**0.5)+1):
        if x%d == 0:
            ans.append(d)
            if x//d != d:
                ans.append(x//d)
    return sorted(ans)


N, K = map(int, input().split())
As = list(map(int, input().split()))

sumA = sum(As)
divisors = getDivisor(sumA)
#print(divisors)

def f(d):
    Bs = As[:]
    diffs = [0]*N
    sumAdd = sumSub = 0
    maxAdd = maxSub = 0
    nAdd = nSub = 0
    d2 = d//2
    for i, B in enumerate(Bs):
        BmodD = B%d
        if BmodD == 0:
            pass
        elif BmodD <= d2:
            # 減らす
            diffs[i] = BmodD
            sumSub += BmodD
            if BmodD > maxSub:
                maxSub = BmodD
            nSub += 1
        else:
            # 増やす
            diffs[i] = d-BmodD
            sumAdd += d-BmodD
            if d-BmodD > maxAdd:
                maxAdd = d-BmodD
            nAdd += 1

    if sumSub == sumAdd:
        return sumSub <= K
    elif sumSub > sumAdd:
        # 減らし過ぎ
        if nSub < N:
            return sumSub <= K and sumAdd <= K
        else:
            sumSub -= d-maxSub
            return sumSub <= K and sumAdd <= K
    else:
        # 増やし過ぎ
        if nAdd < N:
            return sumSub <= K and sumAdd <= K
        else:
            sumAdd -= maxAdd
            return sumSub <= K and sumAdd <= K


for d in reversed(divisors):
    ret = f(d)
    if ret:
        print(d)
        break
else:
    print(1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
nums = A[:]

sum_n = sum(nums)

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

    return divisors

divisors = sorted(list(make_divisors(sum_n)), reverse=True)
#print('DIV', divisors)

import math
for d in divisors:
    mod_nums = list(map(lambda x: x%d, nums[:]))
    #print(mod_nums)
    sum_m = sum(mod_nums)
    #print(sum_m)
    if math.ceil(sum_m/2) <= K:
        ans = d
        break



print(ans)

Submission status: Wrong Answer

Solution code:
import math
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

sA = sum(A)


def trial_division(n):
    # 素因数を格納するリスト
    factor = []
    # 2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    # リストが空ならそれは素数
    if not factor:
        return [n]
    else:
        factor.append(n)
        return factor


lst = sorted(trial_division(sum(A)))

n = len(lst)
for i in range((2 ** n)-1, 0, -1):
    c = 1
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            c *= lst[j]  # フラグが立っていたら bag に果物を詰める

    cnt = 0
    for a in A:
        cnt += min(a % c, c-(a % c))
    if cnt//2 <= K:
        print(c)
        exit()

print(1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
S = sum(A)
k = K
m = 0
for i in range(N):
    if k > A[i]:
        k -= A[i]
        m += 1
    else:
        break

for i in range(S, int(S ** (1 / 2)) - 1, -1):
    if S % i == 0:
        t = S // i
        if t > N - m:
            print(i)
            break

Submission status: Wrong Answer

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

sum1 = sum(a)

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

    return divisors

li = make_divisors(sum1)

ans = 0

for i in li:
    a.sort(key = lambda x: min(x%i,i-x%i))
    count = sum1 // i
    count2 = 0
    for j in range(len(a)):
        if j != len(a) - 1:
            if a[j] % i == 0:
                count -= a[j] // i
            else:
                t = a[j] // i
                if abs(a[j] - i * t) < abs(a[j] - i * (t+1)):
                    count2 += abs(a[j] - i*t)
                    count -= t
                else:
                    count2 += abs(a[j] - i * (t+1))
                    count -= t+1
        else:
            count2 += abs(a[j] - count * i)
    if count2 // 2 <= k:
        ans = max(ans,i)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
sun = sum(a)
cd = []
rcd = []
for i in range(1,int(sun**0.5)+1):
  if sun % i == 0:
    cd.append(i)
    rcd.append(sun//i)
rcd.reverse()
if cd[-1] == rcd[0]:
  del cd[-1]
gcd = cd + rcd
gcd.reverse()
#print(gcd)
count = -1
while True:
  count += 1
  g = gcd[count]
  b = list(map(lambda x: x % g,a))
  moon = sum(b)
  if moon // 2 <= k:
    print(g)
    break

Submission status: Wrong Answer

Solution code:
from copy import deepcopy as dee
n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
b=sum(a)

def d(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()
  divisors.reverse()
  return divisors
def g(a,j,k):
  b=[i%j for i in a]
  c=[abs(j-i%j) for i in a]
  f=set([(0,0)])
  for d,e in zip(b,c):
    h=set()
    for g in f:
      if g[0]+d<=k:
        h.add((g[0]+d,g[1]))
      if g[0]+e<=k:
        h.add((g[0],g[1]+e))
    f=dee(h)
  y={(x,x) for x in range(0,k+1)} & f
  return y

c=d(b)
for i in c:
  e=[min(j%i,abs(i-j%i)) for j in a]
  f=sum(e)
  if f<=2*k:
    if g(a,i,k):
      print(i)
      exit()

Submission status: Wrong Answer

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

s = sum(a)
d = []
for i in range(1, s):
    if s % i == 0:
        d.append(i)
    if s <= i * i:
        break
    if s % i == 0:
        d.append(s // i)
d = list(reversed(sorted(d)))

for di in d:
    b = []
    for ai in a:
        b.append(ai % di)
    b = list(sorted(b))
    cnt = 0
    il = 0
    ir = n - 1
    while il < ir:
        if b[il] + b[ir] == di:
            cnt += b[il]
            b[il] = 0
            b[ir] = di
            il += 1
            ir -= 1
        elif b[il] < di - b[ir]:
            cnt += b[il]
            b[il] = 0
            b[ir] += b[il]
            il += 1
        else:
            cnt += di - b[ir]
            b[ir] = di
            b[il] -= di - b[ir]
            ir -= 1
    if cnt <= k:
        print(di)
        break

Submission status: Wrong Answer

Solution code:
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(reverse=True)
    return divisors


n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
d = make_divisors(s)
for x in d:
    b = a[:]
    idx, idx2 = 0, 0
    for i in range(n):
        b[i] %= x
        if b[i] > x // 2:
            b[i] -= x
    su = sum(b)
    mindex = b.index(min(b))
    maxdex = b.index(max(b))
    if su > 0:
        b[maxdex] -= su
    else:
        b[mindex] -= su
    abs_sum = 0
    for i in range(n):
        abs_sum += abs(b[i])
    if abs_sum // 2 <= k:
        print(x)
        break

Submission status: Wrong Answer

Solution code:
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))

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(reverse=True)
    return divisors
d=make_divisors(sum(a))
l=len(d)

x=0
for i in range(l):
    b=0
    c=0
    x=d[i]
    for j in range(n):
        if x-a[j]%x>a[j]%x:
            b+=a[j]%x
        else:
            c+=x-a[j]%x
    if max(b//x*x,c//x*x)<=k:
        print(x)
        sys.exit()

Submission status: Wrong Answer

Solution code:
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(reverse =True)
    return divisors

n,k = map(int,input().split())

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

sumli = sum(li)

div =make_divisors(sumli)
for i in range(len(div)):
    ans = div[i]
    diff = map(lambda x: min(x % ans, ans-x%ans), li)
    a = sum(diff)
    if (a/2 < k):
        print(ans)
        break

Submission status: Wrong Answer

Solution code:
from math import ceil
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

n, k = map(int, input().split())
a = list(map(int, input().split()))
l = make_divisors(sum(a))
m = len(l)
ans = 1

for gcd in l:
    mod = 0
    k_s = 0
    for a_ in a:
        mod_ = a_ % gcd
        k_s += min(mod_, gcd - mod_)
        mod += mod_
    if ceil((k_s+1)/2) < k and mod % gcd == 0:
        ans = max(ans, gcd)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
sumA = sum(A)

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(reverse=True)
    return divisors

divs = make_divisors(sumA)

for i in divs:
    mod = 0
    for j in range(N):
        mod += A[j] % i
    if mod // 2 <= K:
        ans = i
        break

print(ans)