結果

問題 No.3363 Two Closest Numbers
コンテスト
ユーザー tassei903
提出日時 2025-11-17 23:58:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 168 ms / 2,000 ms
コード長 2,128 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 105,588 KB
最終ジャッジ日時 2025-11-17 23:58:52
合計ジャッジ時間 7,468 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
"""
n が偶数

桁数は同じがいい

同じ

nが奇数

- x 


"""

from itertools import permutations

def naive(n, c):
    if n == 0:
        return 0
    ans = 10 ** 18
    c = sorted(c)
    for bit in range(1 << n):
        A = []
        B = []
        for i in range(n):
            if bit >> i & 1:
                A.append(c[i])
            else:
                B.append(c[i])
        if len(A) != len(B):
            continue
        
        
        for i in range(n//2):
            for j in range(n//2):
                a = list(A)
                b = list(B)
                a.remove(A[i])
                b.remove(B[j])
                if A[i] <= B[j]:
                    x = str(A[i]) + "".join([str(x) for x in a[::-1]])
                    y = str(B[j]) + "".join([str(x) for x in b])
                else:
                    x = str(A[i]) + "".join([str(x) for x in a])
                    y = str(B[j]) + "".join([str(x) for x in b[::-1]])
                # print(x, y)
                ans = min(abs(int(x) - int(y)), ans)

    return ans

def large(m1, c):
    c = sorted(c)
    A = c[:m1]
    B = c[m1:][::-1]
    # print(A, B)
    a = 0
    for i in range(len(A)):
        a = (a * 10 + A[i]) % mod
    b = 0
    for i in range(len(B)):
        b = (b * 10 + B[i]) % mod
    return (a - b) % mod


mod = 998244353
n = ni()
c = na()

if n % 2 == 1:
    print(large((n+1)//2, c))
else:
    # assert False
    cnt = [0] * 10
    for i in range(n):
        cnt[c[i]] += 1
    
    cc = []
    for i in range(10):
        if cnt[i] % 2:
            cc.append(i)
    ans = naive(len(cc), cc)
    for i in range(10):
        dd = list(cc)
        if cnt[i] >= 2:
            ans = min(ans, naive(len(cc) + 2, dd + [i, i]))
    

    print(ans % mod)
0