Problem:


Score : 700 points

Problem Statement

There are N cats.
We number them from 1 through N.

Each of the cats wears a hat.
Cat i says: "there are exactly a_i different colors among the N - 1 hats worn by the cats except me."

Determine whether there exists a sequence of colors of the hats that is consistent with the remarks of the cats.

Constraints

2 ≤ N ≤ 10^5

1 ≤ a_i ≤ N-1

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print Yes if there exists a sequence of colors of the hats that is consistent with the remarks of the cats; print No otherwise.

Sample Input 1

3
1 2 2

Sample Output 1

Yes

For example, if cat 1, 2 and 3 wears red, blue and blue hats, respectively, it is consistent with the remarks of the cats.

Sample Input 2

3
1 1 2

Sample Output 2

No

From the remark of cat 1, we can see that cat 2 and 3 wear hats of the same color.
Also, from the remark of cat 2, we can see that cat 1 and 3 wear hats of the same color.
Therefore, cat 1 and 2 wear hats of the same color, which contradicts the remark of cat 3.

Sample Input 3

5
4 3 4 3 4

Sample Output 3

No

Sample Input 4

3
2 2 2

Sample Output 4

Yes

Sample Input 5

4
2 2 2 2

Sample Output 5

Yes

Sample Input 6

5
3 3 3 3 3

Sample Output 6

No



Sample input:
3
1 2 2


Sample output:
Yes

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    A = list(map(int,input().split()))

    a = max(A)
    if not all(0 <= a - b <= 1 for b in A):
        print('No')
        return
    
    cnt = sum(0 if a == b else 1 for b in A)
    if cnt == 0 and (2*a <= N or a + 1 == N):
        print('Yes')
    elif a == cnt == N:
        print('Yes')
    elif a - cnt > 0 and (a - cnt)*2 <= N - cnt:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
s = set(a)
if len(s)>2:
    ans = "No"
elif len(s)==2:
    if max(s)-min(s)!=1:
        ans = "No"
    else:
        x = max(s)
        n2 = sum(num==x-1 for num in a)
        if x-n2>0 and n2 + 2*(x-n2) <= n:
            ans = "Yes"
        else:
            ans = "No"
else:
    x = max(s)
    if x==n-1 or 2*x<=n:
        ans = "Yes"
    else:
        ans = "No"
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
cnt=Counter(a)
if len(cnt)>2:
    print("No")
    quit()

if len(cnt)==1:
    if n==a[0]+1 or a[0]*2<=n:
        print("Yes")
    else:
        print("No")
    quit()

syo=cnt[min(a)]
dai=cnt[max(a)]
if max(a)-min(a)!=1:
    print("No")
    quit()
maru=max(a)-syo
if maru<=0:
    print("No")
elif maru*2<=dai:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
a=list(map(int,input().split()))
m=min(a)
M=max(a)
if M-m>1:
    print("No")
    exit()
elif M-m==0:
    if a[0]==n-1 or 2*a[0]<=n:
        print("Yes")
    else:
        print("No")
elif M-m==1:
    c=0
    for i in range(n):
        if a[i]==m:
           c+=1
    if 2<=2*(M-c)<=n-c:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
if max(a) - min(a) >= 2:
    print("No")

elif max(a) - min(a) == 0:
    if a[0] == n-1 or 2*a[0] <= n:
        print("Yes")
    else:
        print("No")

else:
    p = a.count(max(a))
    q = a.count(min(a))
    if q+1 <= max(a) <= q+p//2:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
ans=False
aa=a[0]

s1=0
s2=0
check=True
for i in range(n):
    if a[i]==aa:
        s1+=1
    elif a[i]==aa+1:
        s2+=1
    else:
        check=False
        break
if check:
    if s2==0:
        if aa==n-1:
            ans=True
    else:
        if 2<=(aa+1-s1)*2<=s2:
            ans=True
s1=0
s2=0
check=True
for i in range(n):
    if a[i]==aa-1:
        s1+=1
    elif a[i]==aa:
        s2+=1
    else:
        check=False
        break
if check:
    if s2==0:
        pass
    else:
        if 2<=(aa-s1)*2<=s2:
            ans=True

if ans:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))

A.sort()

mn = min(A)
mx = max(A)
if mx - mn > 1:
    print('No')
    exit()

if mn == mx:
    if N == mn + 1 or N >= 2*mn:
        print('Yes')
    else:
        print('No')
    exit()

nsolo = A.count(mn)
ndup = N - nsolo

if nsolo  > mn:
    print('No')
    exit()

if ndup < 2*(mn - nsolo+1):
    print('No')
    exit()

print('Yes')

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = sorted(map(int, readline().split()))

def main(A):
    N = len(A)
    if A[0] == A[-1]:
        x = A[0]
        return x == N - 1 or 2 * x <= N
    if A[0] + 1 != A[-1]:
        return False
    a, b = A[0], A[-1]
    full = b
    unique = A.count(a)
    people, color = N - unique, A[-1] - unique
    return color > 0 and 2 * color <= people

print('Yes' if main(A) else 'No')

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
s=max(a)-min(a)
if s>=2:
    print("No")
elif s==0:
    if a[0]==n-1 or n//a[0]>=2:
        print("Yes")
    else:
        print("No")
else:
    a.sort()
    x=bisect.bisect_right(a,a[0])
    if x+1<=a[-1]<=x+(n-x)//2 and n-x>=2:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ma, mi = max(a), min(a)
if ma - mi > 1:
    print("No")
elif ma - mi == 1:
    z, o = 0, 0
    for i in range(n):
        if a[i] == ma - 1:
            z += 1
        else:
            o += 1
    if z < ma and ma - z <= o / 2:
        print("Yes")
    else:
        print("No")
else:
    if ma == n - 1 or ma <= n / 2:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
m = min(A)
M = max(A)
if M - m > 1:
  print("No")
elif M - m == 0:
  if 1 <= M <= n//2 or m == n-1:
    print("Yes")
  else:
    print("No")
else:
  k = A.count(m)
  if 1 <= M-k <= (n-k)//2:
    print("Yes")
  else:
    print("No")

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = max(A); m = min(A)
if M - m > 1:
  print('No')
elif M - m == 1:
  c = A.count(m)
  if 2*M - N <= c < M:
    print('Yes')
  else:
    print('No')
else:
  if m == N-1:
    print('Yes')
  elif N >= 2*m:
    print('Yes')
  else:
    print('No')

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
if max(a)-min(a)>=2:exit(print("No"))
if len(set(a))==1:
  m=a[0]
  if m==n-1 or 2*m<=n:print("Yes")
  else:print("No")
else:
  x=a.count(min(a))
  y=n-x
  if x<max(a) and 2*(max(a)-x)<=y:print("Yes")
  else:print("No")

Submission status: Accepted

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

cat = {}
for c in a:
  if c in cat:
    cat[c] += 1
  else:
    cat[c] = 1

min_cat = N
min_cat_cnt = 0
max_cat = 0
max_cat_cnt = 0
for c in cat:
  if c < min_cat:
    min_cat = c
    min_cat_cnt = cat[c]
  if c > max_cat:
    max_cat = c
    max_cat_cnt = cat[c]
    
if max_cat - min_cat == 1 and min_cat_cnt <= min_cat and 2 * min_cat - min_cat_cnt + 2 <= N:
  print("Yes")
elif max_cat == min_cat and 2 * (max_cat) <= N:
  print("Yes")
elif max_cat == min_cat and min_cat_cnt - 1 == min_cat:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
*a, = map(int, input().split())
v = sum(a)
c = Counter(a)

for n in range(N+1)[::-1]:
    if v-(N-1)*n>=0 and (v-(N-1)*n)%N==0:
        k = (v-(N-1)*n)//N
        if (k==0 and n==N) or (k and (N-n)%k==0):
            if c[n+k]==N-n and c[n+k-1]==n:
                print("Yes")
                break
else:
    print("No")

Submission status: Accepted

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

x = min(a)
y = max(a)
if y - x > 1:
    print('No')

elif y == x:
    if n == x + 1 or 2 * x <= n:
        print('Yes')
    else:
        print('No')

else:
    x_cnt = a.count(x)
    y_cnt = a.count(y)

    if y > x_cnt and 2 * (y - x_cnt) <= y_cnt:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

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

N = int(input())
a = list(map(int, input().split()))
m, n = max(a), min(a)
if m - n > 1 or m >= N:
    print('No')
elif m - n == 0:
    print('Yes' if n == N - 1 or n * 2 <= N else 'No')
else:
    print('Yes' if 1 <= m - a.count(n) <= a.count(m) // 2 else 'No')

Submission status: Accepted

Solution code:
from collections import Counter


def cat():
    N = int(input())
    A = list(map(int, input().split()))

    # こいつらは絶対いける
    if A == [1] * N:
        return True
    if A == [N - 1] * N:
        return True

    # 数字は高々隣り合う数2種になるはず
    Aset = set(A)
    if len(Aset) == 1:
        Amax = A[0]
        cnt = N - Amax + 1
        if N <= 2 * cnt - 2:
            return True
        else:
            return False
    elif len(Aset) == 2:
        A.sort()
        Amax = A[-1]
        Amin = A[0]
        if Amin + 1 != Amax:
            return False
        lower = N - Amax + 1
        upper = 2 * lower - 2
        c = Counter(A)
        if lower <= c[Amax] <= upper:
            return True
        else:
            return False
    else:
        return False


if __name__ == "__main__":
    if cat():
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
from collections import Counter

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

if len(A.keys()) >= 3:
    print('No')
    exit()

if len(A.keys()) == 1:
    p = list(A.keys())[0]
    print('Yes' if 2 * p <= N or p == N - 1 else 'No')
    exit()

p1, p2 = sorted(A.keys())
print('Yes' if p2 - p1 == 1 and (A[p1] + 1) <= p2 <= (A[p1] + A[p2] // 2) else 'No')

Submission status: Accepted

Solution code:
n=int(input())

a=list(map(int,input().split()))
if len(set(a))==1:
    if n>=2*a[0] or n-1==a[0]:print("Yes")
    else:print("No")
elif len(set(a))>=3:print("No")
else:
    s,S=sorted(list(set(a)))
    k=a.count(s)
    if S==s+1 and 2*S-n<=k and S>k:print("Yes")
    else:print("No")

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()

mx,mxc = 0,0
mn,mnc = 1000000,0
for i in a:
    if mx == i:
        mxc += 1
    if mn == i:
        mnc += 1
    if mx < i:
        mx = i
        mxc = 1
    if mn > i:
        mn = i
        mnc = 1

d = mx-mn


if d > 1:
    print('No')
elif d == 1:
    if mx > mnc and 2*(mx-mnc) <= mxc:
        print('Yes')
    else:
        print('No')
elif d == 0:
    if a[0] == n-1 or 2*a[0] <= n:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

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

A.sort()
v = A[-1] - A[0]
if v >= 2:
    print('No')
elif v == 0:
    if A[0]*2 <= n or A[0] == n-1:
        print('Yes')
    else:
        print('No')
else:
    x = A.index(A[-1])
    y = A[0] - x + 1
    if y > 0 and y*2 <= n-x:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

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

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, a: "List[int]"):
    from collections import Counter
    ma, mi = max(a), min(a)
    if ma >= N or mi < 1:
        raise
    if ma - mi > 1:
        return False
    # 全員aloneか、全員pair以上（pairもしくはcrowd）
    if ma == mi:
        return ma == N - 1 or  2 * ma <= N
    c = Counter(a)
    # pairがpairでない
    if c[ma] % 2 != 0:
        return False
    x = ma - c[ma] // 2
    # pair以外、すべてalone(crowdが0個)
    if x == c[mi]:
        return True
    # crowdを1つ以上作れるなら1以上c[mi]-2以下の好きな數を作れる
    return 1 <= x <= c[mi] - 2

# Generated by 1.1.6 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)) for _ in range(N)]  # type: "List[int]"
    print(YES if solve(N, a) else NO)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, a: "List[int]"):
    from collections import Counter
    ma, mi = max(a), min(a)
    if ma >= N or mi < 1:
        raise
    if ma - mi > 1:
        return False
    # 全員aloneか、全員crowd
    if ma == mi:
        return ma == N - 1 or  2 * ma <= N
    c = Counter(a)
    # pairがpairでない
    if c[ma] % 2 != 0:
        return False
    x = ma - c[ma] // 2
    # pair以外、すべてalone(crowdが0個)
    if x == c[mi]:
        return True
    # crowdを1つ以上作れるなら1以上c[mi]-2以下の好きな數を作れる
    return 1 <= x <= c[mi] - 2

# Generated by 1.1.6 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)) for _ in range(N)]  # type: "List[int]"
    print(YES if solve(N, a) else NO)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, a: "List[int]"):
    from collections import Counter
    ma, mi = max(a), min(a)
    if ma >= N or mi < 1:
        raise
    if ma - mi > 1:
        return False
    if ma == mi:
        return ma == N - 1 or  2 * ma <= N
    c = Counter(a)
    # pairがpairでない
    if c[ma] % 2 != 0:
        return False
    x = ma - c[ma] // 2
    if x < 0:
        return False
    # pair以外、すべてalone(crowdが0個)
    if x == c[mi]:
        return True
    # crowdを1つ以上作れるなら0以上c[mi]-2以下の好きな數を作れる
    return x <= c[mi] - 2

# Generated by 1.1.6 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)) for _ in range(N)]  # type: "List[int]"
    print(YES if solve(N, a) else NO)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

A.sort()
if A[-1]-A[0]>1:
    print('No')
else:
    if A[-1]-A[0]==1:
        n=A.count(A[0])
        m=A.count(A[-1])
        kind=A[-1]-n
        if m>=2*kind and kind>0:
            print('Yes')
        else:
            print('No')
    else:
        if A[0]==N-1:
            print('Yes')
        else:
            if N>=2*A[0]:
                print('Yes')
            else:
                print('No')

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
M=max(a)
m=min(a)
if M>m+1:
  print("No")
elif M==m+1:
  cntm=a.count(m)
  cntM=n-cntm
  if cntm>m:
    print("No")
  elif cntm+cntM//2<M:
    print("No")
  else:
    print("Yes")
elif M==m:
  if m<=n//2:
    print("Yes")
  elif m==n-1:
    print("Yes")
  else:
    print("No")

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline

N, *a = map(int, read().split())
a.sort()
if a[0] + 1 < a[-1]:
    print('No')
elif a[0] == a[-1]:
    if a[-1] == N - 1 or 2 * a[-1] <= N:
        print('Yes')
    else:
        print('No')
else:
    b = a.count(a[0])
    c = N - b
    if b < a[-1] and 2 * (a[-1] - b) <= c:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

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

res = True
maxvar = max(A)

x = 0
y = 0

for i in range(N):
    if A[i] == maxvar:
        x += 1
    elif A[i] == maxvar - 1:
        y += 1
    else:
        res = False
        break
else:
    if (maxvar - y) * 2 + y > N or y >= maxvar:
        res = False

    if maxvar == N - 1 and y == 0:
        res = True

print('Yes' if res else 'No')

Submission status: Accepted

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

res = True
maxvar = max(A)

x = 0
y = 0

for i in range(N):
    if A[i] == maxvar:
        x += 1
    elif A[i] == maxvar - 1:
        y += 1
    else:
        res = False
        break
else:
    if (maxvar - y) * 2 + y > N or (maxvar - y) * 2 <= 0 or y >= maxvar:
        res = False

    if maxvar == N - 1 and y == 0:
        res = True

print('Yes' if res else 'No')

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
k=len(set(A))
if k==1:
  if A[0]==n-1 or 2*A[0]<=n:
    print("Yes")
  else:
    print("No")
elif k>2:
  print("No")
else:
  ma=min(A)
  Ma=max(A)
  if Ma-ma>1:
    print("No")
  else:
    ct=0
    for a in A:
      if a==ma:
        ct+=1
    if ma+1>ct and (ma+1-ct)*2<=n-ct:
      print("Yes")
    else:
      print("No")

Submission status: Accepted

Solution code:
# 解説AC
N = int(input())
A = [int(i) for i in input().split()]

MAXA = max(A)
MINA = min(A)

if MAXA - MINA >= 2:
    flag = False
elif MAXA - MINA == 0:
    # 全てalone -> 種類数はN
    flag = True if (A[0] == N - 1) else False
    # 全てaloneではない -> 種類数はN/2以下
    flag |= True if (2 * A[0] <= N) else False
else:
    x = A.count(MINA) # alonaな猫の匹数
    y = A.count(MAXA) # aloneではない猫の匹数
    # MAXA - x: aloneではない猫の種類数
    flag = True if (x < MAXA and 2 * (MAXA - x) <= y) else False

if flag:
    print('Yes')
else:
    print('No')

Submission status: Accepted

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

if(max(a) - min(a) > 1):
    print('No')
    exit()
elif(max(a) - min(a) == 0):
    var = max(a)
    if((var==n-1)|(var <= n//2)):
        print('Yes')
    else:
        print('No')
    exit()

max_n = a.count(max(a))
min_n = a.count(min(a))

max_var = min_n + max_n//2
min_var = min_n + 1

if((min(a) >= min_var - 1) & (max(a) <= max_var)):
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
a.sort()
if a[-1] - a[0] > 1:
  print("No")
  exit(0)

if a[0] == a[-1]:
  if a[0] == N - 1:
    print("Yes")
    exit(0)
  if N // a[0] >= 2:
    print("Yes")
  else: print("No")
  exit(0)

table = [0] * N
for i in range(N):
  if a[i] == a[0]: table[i] = i + 1
l = max(table) + 1
r = l + table.count(0) // 2

if a[-1] in range(l, r): print("Yes")
else: print("No")

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
a,b=max(l),min(l)
if a-b>1:
    ans="No"
elif a==b:
    if a<=n//2 or a==n-1:
        ans="Yes"
    else:
        ans="No"
else:
    if 2*a-n<=l.count(b)<=b:
        ans="Yes"
    else:
        ans="No"
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
data = [[-1, 0]]
for x in a:
    if data[-1][0] == x:
        data[-1][1] += 1
    else:
        data.append([x, 1])
data = data[1:]

if len(data) == 1:
    print("Yes" if data[0][0] * 2 <= n or data[0][0] + 1 == n else "No")
elif len(data) == 2:
    if data[0][0] + 1 == data[1][0] and data[0][0] >= data[0][1] and data[1][1] >= 2 * (data[1][0] - data[0][1]):
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Accepted

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

a.sort()
if a[-1] - a[0] >= 2:
    print("No")
elif a[-1] - a[0] == 1:
    m = 0
    for x in a:
        if x == a[0]:
            m += 1
        else:
            break
    if  a[-1]-m <= (n-m)//2 and a[-1]-m > 0:
        print("Yes")
    else:
        print("No")
else:
    if a[0] == n-1 or a[0] <= n//2:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

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

d = {}

for ai in a:
    if ai not in d:
        d[ai] = 0
    d[ai] += 1

f = 1

k = list(d.keys())
k.sort()

# ボッチ猫の数
b = 0

if len(k) > 2:
    f = 0
elif len(k) == 2:
    if k[1] - k[0] != 1:
        f = 0
    b = d[k[0]]

# グループ数
g = k[-1] - b

if g <= 0 or g > d[k[-1]] // 2:
    f = 0

if len(k) == 1 and k[-1] == n - 1:
    f = 1

if f:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
if max(a)>=min(a)+2:
    print('No')
elif max(a)==min(a):
    if max(a)==n-1 or 2*max(a)<=n:
        print('Yes')
    else:
        print('No')
else:
    mi=0
    ami=min(a)
    for i in a:
        if i==ami:
            mi+=1
    ma=n-mi
    if mi<ami+1 and 2*(ami+1-mi)<=ma:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
n=int(input())
lists=list(map(int,input().split()))
from collections import Counter
a=dict(Counter(lists))
if len(a)==1:
    if n>=lists[0]*2 or lists[0]==n-1:
        print("Yes")
    else:
        print("No")
    
elif len(a)==2:
    P=list(a.keys())
    Q=list(a.values())
    x,y=min(P),max(P) #x=k+l-1,y=k+l
    c,d=a[x],a[y]#c=k,d=?
    if 2*y-c<=n and c>0 and y>c and y-x==1:
        print("Yes")
    else:
        print("No")

    
else:
    print("No")

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())
s = set(A)
if max(s)-min(s)>1:
  print('No')
else:
  if len(s)==1:
    if A[0]==N-1:
      print('Yes')
    elif 2*A[0]<=N:
      print('Yes')
    else:
      print('No')
  elif len(s)==2:
    N -= A.count(min(s))
    u = max(s)-A.count(min(s))
    if u<=0:
      print('No')
    elif 2*u<=N:
      print('Yes')
    else:
      print('No')
  else:
    print('No')

Submission status: Accepted

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    
    if (max(a)-min(a) >= 2):
        print("No")
    else:
        count = [0,0]
        t = min(a)
        for num in a:
            if num == t:
                count[0] += 1
            else:
                count[1] += 1
        if (count[0]*count[1] == 0):
            if (2*a[0] <= N or a[0] == N-1):
                print("Yes")
            else:
                print("No")
        else:
            if (count[0] < t+1 and 2*(t+1-count[0]) <= count[1]):
                print("Yes")
            else:
                print("No")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
B = []
C = []
for num in A:
    if len(B) >= 3:
        print("No")
        break
    elif num in B: 
        C[B.index(num)] += 1
    else:
        B.append(num)
        C.append(1)


if len(B) >= 3:
    pass
elif len(B) == 1:
    if n == B[0] +1:
        print('Yes')
    elif n//B[0] >= 2:
        print('Yes')
    else:
        print('No')
elif B[0]  == (B[1]+1):
    k = C[1]
    m = B[1]
    if m-k+1 <= 0:
        print('No')
    elif (n-k) % (m-k+1) == 0:
        print('Yes')
    else:
        print('No')
elif B[1] == (B[0]+1):
    k = C[0]
    m = B[0]
    if m-k+1 <= 0:
        print('No')
    elif (n-k) % (m-k+1) == 0:
        print('Yes')
    else:
        print('No')
else:
    print('No')

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

A.sort()
flag = True
for a in A:
    if a > A[0]+1:
        flag = False

ans = "No"
if flag:
    cnt = A.count(A[0])
    if cnt == N and (A[0] == N-1 or A[0]*2 <= N):
        ans = "Yes"
    elif cnt == A[0] and cnt < N-1:
        ans = "Yes"
    elif cnt < A[0] and N-cnt >= 2*(A[0]-cnt+1):
        ans = "Yes"
        
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
Ma,ma=max(A),min(A)
b=Ma-ma<=1
if b:
    if Ma==ma:
        b=N==Ma+1 or N//2>=Ma
    else:
        Mc=len(list(a for a in A if a==Ma))
        mc=N-Mc
        b=mc+1<=Ma<=mc+Mc//2
print("YNeos"[not b::2])

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
mx = max(a)
mn = min(a)
if mx>mn+1:
    print('No')
elif mx==mn:
    if mx==n-1 or n>=2*mn:
        print('Yes')
    else:
        print('No')
else:
    k = len([x for x in a if x==mn])
    if k<mx and n-k>=2*(mx-k):
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array(lr())
diff = A.max() - A.min()
if diff > 1:
    print('No')
    exit()
if diff == 0:
    if A[0] == N-1:
        print('Yes')
    else:
        group = A[0]
        if 2 * group > N:
            print('No')
        else:
            print('Yes')
    exit()
else:
    # 差が１
    x = np.count_nonzero(A==A.min()) #自分自身はalone
    group = A.max()
    if x < group and 2 * (group-x) <= N - x:
        print('Yes')
    else:
        print('No')
#13

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
if a[n-1]-a[0]>=2:
  print('No')
  exit()
if a[n-1]==a[0]:
  if a[0]==n-1 or 2*a[0]<=n:
    print('Yes')
  else:
    print('No')
else:
  x=a[0]
  cnt=0
  for i in range(n):
    if a[i]==x:
      cnt+=1
    else:
      break
  if cnt<a[n-1] and 2*(a[n-1]-cnt)<=n-cnt:
    print('Yes')
  else:
    print('No')

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
s = set(a)
if len(s)>=3:
    print('No')
elif len(s)==2:
    #頑張る
    mx = max(a)
    mn = min(a)
    y = a.count(mx)
    x = a.count(mn)
    if mx-mn>1:
        print('No')
    elif x < mx and 2*(mx-x)<=y:
        print('Yes')
    else:
        print('No')
else:
    if a[0]==n-1:
        print('Yes')
    elif a[0]*2<=n:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
import sys
N = int(input())
a = list(map(int, input().split()))
m = max(a)
cnt0 = a.count(m)
cnt1 = a.count(m-1)
if cnt0+cnt1 != N:
    print('No')
    sys.exit()
if cnt1+1<=m<=cnt1+cnt0//2:
    print('Yes')
elif cnt1 == 0 and m+1 == cnt0:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
N = input()
a = map(int, raw_input().split())

if max(a)-min(a)>=2:
  print "No"
elif max(a)-min(a)==0:
  if N>=2*a[0] or N==a[0]+1:
    print "Yes"
  else:
    print "No"
else:
  cn = max(a)-a.count(min(a))
  if a.count(max(a))>=2 and cn>0 and N>=a.count(min(a))+2*cn:
    print "Yes"
  else:
    print "No"

Submission status: Accepted

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

ls_A = len(set(A))

if ls_A >= 3:
  print("No")
  exit()
  
if max(A) - min(A) >= 2:
  print("No")
  exit()

if len(set(A)) == 1:
  if A[0] == N - 1:
    print("Yes")
    exit()
  if N // A[0] >= 2:
    print("Yes")
  else:
    print("No")
else:
  min_A = min(A)
  cnt_min = 0
  for a in A:
    if a == min_A:
      cnt_min += 1
  N -= cnt_min  
  if max(A) - cnt_min <= 0:
    print("No")
    exit()
  if N // (max(A) - cnt_min) >= 2:
    print("Yes")
  else:
    print("No")

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())),reverse=True)
if A[0]==A[-1] and (A[0]==1 or A[0]==N-1):
    print("Yes")
else:
    k = A[0]
    cnt = A.count(k-1)
    n = N-cnt
    k -= cnt
    if k<=0:
        print("No")
    else:
        n -= 2*k
        if n>=0:
            print("Yes")
        else:
            print("No")

Submission status: Accepted

Solution code:

N=int(input())
A=list(map(int,input().split()))
D={}
for a in A:
  if(a in D):
    D[a]+=1
  else:
    D[a]=1
    
if(max(D)-min(D)>1):
  print("No")
  exit()
  
if(len(D)==2):
  B=max(D)
  if(B-D[B-1]>0 and D[B]>=2*(B-D[B-1])):
    print("Yes")
  else:
    print("No")
  
else:
  B=max(D) # 常に同じ色の人がいる
  if(N>=2*B):
    print("Yes")
    exit()
  
  B=max(D)+1 # 全員違う色
  if(B==N):
    print("Yes")
    exit()
  print("No")

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
X = min(A)
Y = max(A)
if Y - X > 1:
    print("No")
elif X == Y:
    print("Yes" if X <= N//2 or X == N-1 else "No")
else:
    K = A.count(X)
    print("Yes" if N-K > 1 and K+1 <= X+1 <= K + (N-K)//2 else "No")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = min(a)
M = max(a)
num_m = 0
num_M = 0
if M - m >= 2:
  print("No")
else:
  if m == M:
    if m == n-1:
      print("Yes")
    else:
      if m <= n/2:
        print("Yes")
      else:
        print("No")
  else:
    for i in range(n):
      if a[i] == m:
        num_m += 1
    more = n - num_m
    num_remain = M - num_m
    if 0 < num_remain <= more/2:
      print("Yes")
    else:
      print("No")

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
if len(set(l)) == 1:
  if l[0] <= n//2 or l[0] == n-1:
    print('Yes')
  else:
    print('No')
elif len(set(l)) > 2 or max(l)-min(l) > 1:
  print('No')
else:
  ma = max(l)
  mi = ma - 1
  mac = l.count(ma)
  mic = n - mac
  if mic <= mi <= mic-1+mac//2:
    print('Yes')
  else:
    print('No')

Submission status: Accepted

Solution code:
n=int(input())
L=sorted(list(map(int,input().split())))
if L[-1]-L[0]>1:
  s='No'
elif L[-1]-L[0]==1:
  c=L.count(L[0])
  s = ('Yes'if c<L[-1] and 2*(L[-1]-c)<=n-c else 'No')
else:
  s = ('Yes'if L[0]==n-1 or 2*L[-1]<=n else 'No')
print(s)