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:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

n=I()
a=LI()
m,M=min(a),max(a)
n_m=a.count(m)
n_M=a.count(M)

if m+1<M:
    ans=1
elif m+1==M:
    if n_M//2+n_m>=m+1>=n_m+1:
        ans=0
    else:
        ans=1
else:
    if m==n-1 or m<=n//2:
        ans=0
    else:
        ans=1

print(YN[ans])

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

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

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

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


def solve(N, A):
    ma = max(A)
    mi = min(A)
    if ma == mi:
        # 全部違う色
        if ma == N - 1:
            return True
        # 全部誰かと被ってる
        return ma * 2 <= N
    if ma - mi == 1:
        A.sort()
        mi_count = bisect.bisect_left(A, ma)
        # mi_count の数だけ、誰とも被ってない人がいる
        return 0 < (ma - mi_count) * 2 <= N - mi_count
    return False


ok = solve(N, A)
if ok:
    print('Yes')
else:
    print('No')

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
a.sort()
low,high = a[0],a[-1]
if high - low >= 2:
    print('No')
    quit()
if high - low == 1:
    x,y = 0,0
    for i in range(n):
        if a[i] == high:
            y += 1
        else:
            x += 1
    if x < high and 2*(high-x) <= y:
        print('Yes')
    else:
        print('No')
else:
    for i in range(n):
        if a[i] != n-1:
            break
    else:
        print('Yes')
        quit()
    for i in range(n):
        if 2*a[i] > n:
            print('No')
            break
    else:
        print('Yes')

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(map(int, input().split())) for _ in range(N)]
        return map(list,zip(*read_all))

#################

N = I()
a = III()

small = a[0]
large = a[0]

for i in range(1,N):
    if a[i]>small:
        large = a[i]
        break
    if a[i]<small:
        large = small
        small = a[i]
        break

if small != large:
    if large!=small+1:
        print('No')
        exit()
    small_num = 0
    large_num = 0
    for i in range(N):
        if a[i]==small:
            small_num += 1
        else:
            large_num += 1
    num = large_num
    val = large-small_num
    if 2*val<=num and val>=1:
        print('Yes')
    else:
        print('No')
else:
    num = N
    val = large
    if val+1==num:
        print('Yes')
    elif 2*val<=num:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

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

minColor = min(A)
maxColor = max(A)

if minColor == maxColor:
    if minColor == N - 1:  # 各色の猫が1匹ずつ
        print('Yes')
    elif minColor * 2 <= N:  # 各色の猫が2匹以上
        print('Yes')
    else:
        print('No')
    exit()

if minColor + 1 != maxColor:
    print('No')
    exit()

minCnt = 0
maxCnt = 0

for a in A:
    if a == minColor:
        minCnt += 1
    elif a == maxColor:
        maxCnt += 1
    else:
        print('No')
        exit()

# minCnt : 1匹だけの色
# maxCnt : 2匹以上の色
# 全体でmaxColor個の色

if (maxColor - minCnt) * 2 <= maxCnt and maxColor >= minCnt + 1:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    n = int(input())
    a = list(sorted(map(int, input().split())))
    
    if a[0] == a[-1]:
        if (a[0] == n-1 or a[0]*2 <= n):
            print("Yes")
        else:
            print("No")
    elif a[-1] - a[0] > 1:
        print("No")
    else:
        minc = 0
        for _a in a:
            if _a == a[0]:
                minc += 1
            else:
                break
        if minc <= a[0] and n-minc>=2*(a[-1]-minc):
            print("Yes")
        else:
            print("No")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
Amax, Amin = max(A), min(A)
if Amax - Amin > 1:
  print('No')
elif Amax - Amin == 1:
  solo = A.count(Amin)
  print('Yes' if 0 < Amax - solo <= (N - solo) // 2 else 'No')
else:
  print('Yes' if (Amax == N - 1) or (Amax <= N // 2) else 'No')

Submission status: Accepted

Solution code:
N=int(input())
arr=list(map(int,input().split()))
min_,max_=min(arr),max(arr)
ans=None

if max_-min_ > 1:
    ans=False
elif max_-min_ == 1:
    """
    A=max_
    y=len([a for a in arr if a==max_])
    x=N-y
    nc=A-x
    ans=(A-x)>0 and y >=2*(A-x)
    """
    
    y=len([a for a in arr if a==max_])
    x=N-y
    nc=max_-x
    ans=nc>0 and y>=2*nc

else:
    ans=N>=2*min_ or min_+1==N

print("Yes" if ans else "No")

Submission status: Accepted

Solution code:
N=int(input())
arr=list(map(int,input().split()))
min_,max_=min(arr),max(arr)
ans=None

if max_-min_ > 1:
    ans=False
elif max_-min_ == 1:
    A=max_
    y=len([a for a in arr if a==max_])
    x=N-y
    nc=A-x
    ans=(A-x)>0 and y >=2*(A-x)
else:
    ans=N>=2*min_ or min_+1==N

print("Yes" if ans else "No")

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
min_,max_=min(A),max(A)

def f(n,k):
    return n%k==0 if k>0 else False

ans=None
if max_-min_ > 1:
    ans=False
elif max_-min_ == 1:
    k=max_
    nk=len([a for a in A if a==max_])
    nk1=N-nk
    ans=f(nk,k-nk1)
else:
    ans=f(N,min_) or f(N,min_+1)

if ans is True:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
N=int(input())
*A, = map(int,input().split())
B = {}
for a in A: B[a] = B.get(a,0)+1
m = min(B)
M = max(B)
if m+1<M:
    print("No")
    exit()
def check(n):
    b0 = B.setdefault(n-1,0)
    b1 = B.setdefault(n,0)
    if b1==0:
        return b0==n
    else:
        return 1<= n-b0 <= b1//2
if m+1==M:
    ans = check(M)
else:
    ans = check(m) or check(m+1)
print("Yes" if ans else "No")

Submission status: Accepted

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

from collections import Counter

N = int(input())
A = [int(x) for x in input().split()]

x = min(A)
y = max(A)

if x == y:
    # 全員がnon-uniqueな色 or 全員がuniqueな色
    bl = (x <= N//2) or (x == N-1)
elif y != x + 1:
    bl = False
else:
    a = A.count(x)
    b = A.count(y)
    # a人：unique color
    # b人：non-unique color
    # b人でc種類あるとする
    c = y - a
    bl = (1 <= c <= b//2)

answer = 'Yes' if bl else 'No'
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
ma = max(a)
mi = min(a)
if ma - mi >= 2:
    print('No')
elif ma == mi:
    if a[0] == N - 1:
        print('Yes')
    elif 2 * a[0] <= N:
        print('Yes')
    else:
        print('No')
else:
    al = 0
    na = 0
    for i in range(N):
        if a[i] == ma - 1:
            al += 1
        else:
            na += 1

    if al < ma and 2 * (ma - al) <= na:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
n=int(input())
arr=list(map(int,input().split()))
amax=max(arr)
amin=min(arr)
if amax-amin>=2:
  print('No')
elif amax-amin==0:
  flag=False
  for i in range(n):
    if arr[i]!=n-1:
      break
  else:
    flag=True
  for i in range(n):
    if 2*arr[i]>n:
      break
  else:
    flag=True
  if flag==True:
    print('Yes')
  else:
    print('No')
elif amax-amin==1:
  cnt1=0
  cnt2=0
  for i in range(n):
    if arr[i]==amax-1:
      cnt1+=1
    else:
      cnt2+=1
  if cnt1<amax and 2*(amax-cnt1)<=cnt2:
    print('Yes')
  else:
    print('No')

Submission status: Accepted

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

# Yesならば aの任意の2要素の差は高々1である
# 小さい方の値を発言している猫はそれぞれ異なる帽子を被る必要がある
# 大きい方の値を発言している猫は同じ帽子を被る猫が少なくとも他に一匹存在する必要がある
L = min(a)
R = max(a)
ans = (
    'Yes' if R - L == 0 and (N >= 2 * L or N == L + 1) or
    R - L == 1 and 2 * (L + 1) - N <= sum(x == L for x in a) <= L else
    'No'
)

print(ans)

Submission status: Accepted

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

minA, maxA = min(As), max(As)
diff = maxA - minA
if diff > 1:
    print('No')
elif diff == 1:
    numMinA = As.count(minA)
    if numMinA+1 <= maxA <= numMinA+(N-numMinA)//2:
        print('Yes')
    else:
        print('No')
else:
    if 2*maxA <= N or maxA == N-1:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))
    C = Counter(A)
    mn = min(C)
    mx = max(C)
    if mx - mn < 0 or 1 < mx - mn:
        print("No")
        return
    elif mx - mn == 0:
        if mx == N - 1:
            neccessary = N
        else:
            neccessary = mx * 2
    elif mx - mn == 1:
        single = C[mn]
        if mx <= single:
            print("No")
            return
        neccessary = single + (mx - single) * 2
    if neccessary <= N:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [int(item) for item in input().split()]

cnt = Counter(a)
if len(cnt) == 1:
    color_num = max(cnt)
    if color_num == n-1 or color_num <= n // 2:
        print("Yes")
    else:
        print("No")
elif len(cnt) == 2:
    color_num = max(cnt)
    # Cout can be 2 sequential number
    if color_num - 1 not in cnt:
        print("No") 
        exit()
    if cnt[color_num-1] <= color_num - 1 and cnt[color_num-1] >= 2*color_num - n:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import Counter
from sys import exit
def No():
    print('No')
    exit()
def Yes():
    print('Yes')
    exit()

N = int(input())
A = list(map(int, input().split()))
if max(A) - min(A) > 1:
    No()
if len(set(A)) == 1:
    if A == [N-1]*N:
        Yes()
    a = A[0]
    if a <= N//2:
        Yes()
    No()
mA = min(A)
S = max(A)
B = Counter(A)[mA]
if B + 1 <= S <= (N - B)//2 + B:
    Yes()
No()

Submission status: Accepted

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

y=0

x = max(a)

if max(a)-min(a) >1:
    print("No")

elif max(a) == min(a):
    if max(a)==n-1 or n>=2*max(a):
        print('Yes')
    else:
        print('No')
        
else:
    for i in range(n):
        if a[i] == x:
            y += 1

    if y >=2*(x-(n-y)) and x-n+y >0 and n-y>0:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

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

ma = max(a)
for ai in a:
    if ai < ma - 1:
        print("No")
        exit()

flag = 0
for ai in a:
    if ai == ma - 1:
        flag = 1

# 数字が異なるものが存在
if flag:
    count = 0
    for ai in a:
        if ai == ma - 1:
            count += 1
    if (n - count) == 1:
        print("No")
        exit()
    count_min = count + 1
    count_max = count + (n - count) // 2
    if (count_min <= ma) and (ma <= count_max):
        print("Yes")
        exit()
    else:
        print("No")
        exit()

# 数字が全て同じ
if ma == n-1:
    print("Yes")
    exit()
if (1 <= ma) and (ma <= n // 2):
    print("Yes")
    exit()
print("No")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
A=[int(i) for i in input().split()]
A.sort()
K=A[0]
x=0
y=0
for i in range(N):
    if A[i]!=K and A[i]!=K+1:
        print('No')
        sys.exit()
    if A[i]==K:
        x+=1
    elif A[i]==K+1:
        y+=1

if x==N and x >=2*K:
    print('Yes')
    sys.exit()
if x==N and N==K+1:
    print('Yes')
    sys.exit()
if x<=K and y>=(K-x+1)*2:
    print('Yes')
    sys.exit()
print('No')

Submission status: Accepted

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

unum = min(a)
vnum = max(a)

u = a.count(unum)
v = a.count(vnum)

exist = False

if vnum-unum == 1:
  if u+1 <= vnum <= u+v//2:
    exist = True
    
elif vnum == unum:
  if vnum == n-1 or vnum <= n//2:
    exist = True
    
print("Yes" if exist else "No")

Submission status: Accepted

Solution code:
#https://img.atcoder.jp/agc016/editorial.pdf
def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  ans = 'Yes'
  alone = 0
  group = 0
  ha = max(a)
  la = min(a)
  if ha - la >= 2: ans = 'No'
  
  elif ha - la == 1:
   for i in a:
     if i == ha-1 : alone += 1
     else: group += 1
   if alone < ha and 2*(ha-alone)<= group: pass
   else: ans = 'No'
  
  
  elif ha - la == 0:
    if a[0] == n-1 or 2*a[0] <= n:
      pass
    else: ans = 'No'
  return ans

if __name__ == '__main__':
  print(solve())

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
A=list(map(int,input().split()))
a,b=max(A),min(A)
if a-b>1:
    print('No')
elif a==b:
    print('Yes' if a<=n//2 or a==n-1 else 'No')
else:
    c=A.count(b)
    print('Yes' if 1<=a-c<=(n-c)//2 else 'No')

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

exist = True

if max(a) - min(a) > 1:
    exist = False
    
elif max(a) >= n:
    exist = False
    
elif max(a) - min(a) == 1:
    if a.count(min(a)) < max(a) and 2*(max(a)-a.count(min(a))) <= a.count(max(a)):
        exist = True
    else:
        exist = False
        
elif max(a) == min(a):
    if 2*a[0] <= n or a[0]+1 == n:
        exist = True
    else:
        exist = False
        
print("Yes") if exist else print("No")

Submission status: Accepted

Solution code:
n = int(input())

a = list(map(int,input().split()))
a_max = max(a)
a_min = min(a)
if a_max > a_min+1:
    print('No')
    exit()
k = a_max
if a_max == a_min:
    if k == n-1 or 2*k <= n:
        print('Yes')
    else:
        print('No')
else:
    uni = a.count(k-1)
    if k >= uni + 1 and k <= uni + (n-uni)//2:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import Counter


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


def solve():
    N = int(input())
    A = inpl()

    max_a = max(A)
    min_a = min(A)
    num_cnt = Counter(A)

    if max_a - min_a > 1:
        return 'No'

    if len(num_cnt) == 1:
        if max_a == N - 1 or 2 * max_a <= N:
            return 'Yes'
        else:
            return 'No'

    not_alone = num_cnt[max_a]
    alone = num_cnt[min_a]
    if not_alone >= (max_a - alone) * 2 and alone < max_a:
        return 'Yes'

    return 'No'


print(solve())

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import Counter


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


def solve():
    N = int(input())
    A = inpl()

    max_a = max(A)
    min_a = min(A)
    num_cnt = Counter(A)
    min_cnt = num_cnt[min_a]
    max_cnt = num_cnt[max_a]
    # print(num_cnt)

    if max_a - min_a >= 2:
        return 'No'
    elif len(num_cnt) == 1:
        if min_a == N - 1:
            return 'Yes'
        elif min_a * 2 <= N:
            return 'Yes'
        else:
            return 'No'
    elif A.count(1) >= 2:
        return 'No'
    elif min_cnt == 2 and max_cnt >= max_a:
        return 'Yes'
    elif min_cnt == min_a:
        return 'Yes'
    else:
        return 'No'


print(solve())

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
c_min=min(A)
c_max=max(A)
if c_min==c_max:
  if N//2>=c_min or N-1==c_min:
    print("Yes")
  else:
    print("No")
elif c_max-c_min==1:
  if c_max>=A.count(c_min)+1 and A.count(c_max)>=2*(c_max-A.count(c_min)):
    print("Yes")
  else:
    print("No")
else:
  print("No")

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
ctr = Counter(A)

if len(ctr) >= 3:
    print('No')
    exit()
if len(ctr) == 1:
    k,v = list(ctr.items())[0]
    if k == 1:
        print('Yes')
    elif N <= k:
        print('No')
    elif N >= 2*k:
        print('Yes')
    else:
        print('Yes' if k==N-1 else 'No')

else:
    (k1,v1),(k2,v2) = list(sorted(ctr.items()))
    if k2-k1 != 1 or k2 >= N:
        print('No')
    elif v1 > k1:
        print('No')
    else:
        print('Yes' if v2//2 + v1 >= k2 else 'No')

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc016 B
"""

from collections import Counter

n = int(input())
acnt = Counter(map(int, input().split()))

if len(acnt) > 2:
    print('No')
    exit()

if len(acnt) == 1:
    [(a, nn)] = acnt.most_common(1)
    if a in range(1, n//2+1) or a == n-1:
        print('Yes')
    else:
        print('No')
    exit()

if len(acnt) == 2:
    [(a1, n1), (a2, n2)] = sorted(acnt.most_common(2), key=lambda x: x[0])
    if a2-a1 != 1:
        print('No')
    else:
        if 1 <= a2 - n1 <= (n-n1)//2:
            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"
	exit()
if max(a)==min(a):
	print "Yes" if a[0]==n-1 or a[0]*2<=n else "No"
else:
	one_cnt=a.count(min(a))
	more_cnt=min(a)+1-one_cnt
	print "No" if one_cnt+more_cnt*2>n or more_cnt<=0 else "Yes"

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
M=max(A)
m=min(A)
if M-m>=2:
    print("No")
elif M-m==1:
    x=0
    y=0
    for i in range(N):
        if A[i]==m:
            x+=1
        else:
            y+=1
    if x<M and 2*(M-x)<=y:
        print("Yes")
    else:
        print("No")
else:
    if 2*M<=N or M==N-1:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
N = int( input())
A = list( map( int, input().split()))
K = max(A)
L = min(A)
if K == L:
    if K == N-1 or 2*K <= N:
        print('Yes')
    else:
        print('No')
elif abs(K-L) == 1:
    x = K*N - sum(A)
    if 2*K - x <= N and x < K:
        print('Yes')
    else:
        print('No')
else:
    print('No')

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ma = max(A)
mi = min(A)
if ma-mi > 1:
    print("No")
    exit()
if ma-mi == 0 and N-1 == ma:
    print("Yes")
    exit()
d = N-ma
cma = A.count(ma)
if d+1 <= cma <= d*2:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    if (max(a) - min(a)) > 1:
        print("No")
        return 0
    minor = a.count(min(a))
    if n != minor:
        major = n-minor

        mini = minor+1
        maxi = minor + (major//2)
        if mini <= max(a) and max(a) <= maxi:
            print("Yes")
        else:
            print("No")
    else:
        mini = 1
        maxi = minor//2
        if mini <= max(a) and max(a) <= maxi or max(a) == n-1:
            print("Yes")
        else:
            print("No")


main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
c = Counter(a)
if len(c)>2 or a[0]+1<a[-1]: print("No")
elif len(c)==1:
	if a[0]+1==n or n>=2*a[0]: print("Yes")
	else: print("No")
else:
	x,y = c[a[-1]],c[a[0]]
	if y+1<=a[-1]<=x//2+y: print("Yes")
	else: print("No")

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N = int(input())
aa = inpl()
MIN = min(aa)
MAX = max(aa)

if MAX-MIN > 1:
	print('No')
elif MAX == MIN:
	if MAX == N-1:
		print('Yes')
	elif MAX <= N//2:
		print('Yes')
	else:
		print('No')
else: #MAX-MIN == 1
	n_MIN = n_MAX = 0
	for a in aa:
		if a == MIN: n_MIN += 1
		if a == MAX: n_MAX += 1
	x_min = n_MIN + 1
	x_max = n_MIN + n_MAX//2
	if x_min <= MAX <= x_max:
		print('Yes')
	else:
		print('No')

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
sa = max(a)-min(a)
if sa>1:
  print("No")
  exit()
elif sa == 0:
  if max(a) == n-1:
    print("Yes")
  elif max(a) <= n//2:
    print("Yes")
  else:
    print("No")
else:
  alone = a.count(min(a))
  pair = a.count(max(a))
  ceil = alone + pair//2
  floor = alone + 1
  if floor <= max(a) and max(a)<=ceil:
    print("Yes")
  else:
    print("No")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
Min = min(a)
Max = max(a)
if Max - Min > 1:
	print("No")
elif Max == Min:
	if a[0] == n - 1 or a[0] <= n // 2:
		print("Yes")
	else:
		print("No")
else:
	c_M = a.count(Max)
	c_m = n - c_M
	if c_m < Max <= c_m + c_M // 2:
		print("Yes")
	else:
		print("No")

Submission status: Accepted

Solution code:
n=int(input())
s=input().split()
l=[int(s[i]) for i in range(n)]
l.sort()
if l[0]==l[-1]:
    if l[0]<=n//2 or l[0]==n-1:
        print("Yes")
    else:
        print("No")
elif l[-1]-l[0]>1:
    print("No")
else:
    a=l.count(l[0])
    b=l.count(l[-1])
    if a+1<=l[-1]<=a+b//2:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
ma=max(A)
mi=min(A)
ans=True

if ma-mi > 1:
  ans=False
elif ma==mi:
  if ma!=N-1 and ma*2 > N:
    ans=False
else:
  uniq=ma*N - sum(A)
  no_uni=N-uniq
  if no_uni==1:
    ans=False
  else:
    if uniq >= ma or 2*(ma-uniq) > no_uni:
      ans=False
if ans:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)

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

min_ = min(a)
max_ = max(a)

if max_ > min_ + 1:
    print("No")
    exit()

if min_ == max_:
    if min_ == N-1:
        print("Yes")
        exit()
    if 2*min_ <= N:
        print("Yes")
        exit()
    print("No")
    exit()
else:
    # max_ == min_ + 1
    count_min = a.count(min_)
    count_max = a.count(max_)
    if count_min >= max_:
        print("No")
        exit()
    if count_min + 2*(max_ - count_min) <= N:
        debug("hoge")
        print("Yes")
        exit()
    print("No")

Submission status: Accepted

Solution code:
n = int(input())
cats = list(map(int,input().split()))
flag = True
p, q = max(cats), min(cats)
x = cats.count(p)
y = cats.count(q)
if p - q >= 2:
    flag = False
elif p == q:
    if p != n - 1 and p * 2 > n:
        flag = False
else:
    if y >= p or (p-y) * 2 > x:
        flag = False

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
def inpl(): return map(int, input().split())
N = int(input())
A = list(map(int, input().split()))

C = Counter(A)

if len(C) >= 3:
    print("No")
elif len(C) == 1:
    for k, v in C.items():
        if k == N-1 or N >= 2*k:
            print("Yes")
        else:
            print("No")
else:
    k = sorted(C.keys())[0]
    v = C[k]
    X = N - v
    if (k+1-v) * 2 <= C[k+1] and v <= k:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

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

if len(set(A)) == 1:
    if A[0] == N-1 or A[0] <= N // 2:
        print("Yes")
    else:
        print("No")
elif len(set(A)) == 2:
    M = max(A)
    m = min(A)
    if M-m != 1:
        print("No")
    else:
        if A.count(m) < M and 2*(M-A.count(m)) <= A.count(M):
            print("Yes")
        else:
            print("No")
else:
    print("No")

Submission status: Accepted

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

import sys, math, copy
# import fractions, itertools
# import numpy as np
# import scipy

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(input())
    ai = list(map(int, input().split()))
    ma = max(ai)
    k = 0
    for a in ai:
        if a < ma - 1:
            return False
        if a == ma:
            k += 1

    if k == n:
        if ma + 1 == n:
            return True
        elif 1 <= ma <= n // 2:
            return True
        else:
            return False

    if k >= 2 and 1 <= ma - n + k <= k // 2:
        return True
    return False

print("Yes" if main() else "No")

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]

if len(set(a))>=3:
  print('No')
elif len(set(a))==1:
  if a[0]==n-1 or 1 <= a[0] <=n//2:
    print('Yes')
  else:
    print('No')
else:
  m=max(a)
  s=min(a)
  c=sum([1 for i in a if i==m])
  if n-m+1<=c<=n-(m-(n-m)) and s==m-1:
    print('Yes')
  else:
    print('No')

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
B = {}
for a in A:
    B[a] = B.get(a, 0) + 1
if len(B) == 2:
    p, q = sorted(B)
    if p+1 == q:
        if B[q] != 1 and B[p] + 1 <= q <= B[p] + B[q] // 2:
            print('Yes')
            exit(0)
elif len(B) == 1:
    p, = B
    if p <= N // 2 or p == N-1:
        print('Yes')
        exit(0)
print('No')

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
src = list(map(int,input().split()))
ctr = Counter(src)

if len(ctr) > 2:
    print('No')
    exit()

if len(ctr) == 1:
    k = src[0]
    print('Yes' if 2*k <= N or k == N-1 else 'No')
    exit()

min_k, max_k = min(ctr.keys()) ,max(ctr.keys())
min_v, max_v = ctr[min_k], ctr[max_k]
if min_v > min_k:
    print('No')
else:
    print('Yes' if (max_k - min_v)*2 <= max_v else 'No')

Submission status: Accepted

Solution code:
from collections import Counter


def solve(n, cnt):
    if len(cnt) == 1:
        a = next(iter(cnt))
        return (a == n - 1) or (1 <= a <= n // 2)
    a1, a2 = min(cnt), max(cnt)
    if a2 - a1 > 1:
        return False
    c1, c2 = cnt[a1], cnt[a2]
    return c1 < a2 and a2 - c1 <= c2 // 2


n = int(input())
cnt = Counter(map(int, input().split()))

print('Yes' if solve(n, cnt) else 'No')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def solve(N, l):
    a, b = min(l), max(l)
    if b - a > 1:
        return False
    if a == b:
        if a == N - 1:
            return True
        return N >= (a * 2)

    num_a = l.count(a)

    return num_a < b and num_a + 2 * (b - num_a) <= N


def main():
    N = int(input())
    a_list = list(map(int, input().split()))
    print("Yes" if solve(N, a_list) else "No")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def solve(a):
    a = sorted(a)
    if a[0] + 2 <= a[-1]:
        return False
    if a[0] == a[-1]:
        return a[0] + 1 == len(a) or 2 * a[-1] <= len(a)
    x = a.count(a[0])
    return x < a[-1] and x + 2 * (a[-1] - x) <= len(a)
n = int(input())
a = list(map(int, input().split()))
print(['No', 'Yes'][solve(a)])