結果

問題 No.2479 Sum of Squares
ユーザー ntuda
提出日時 2025-02-11 16:31:00
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 813 bytes
コンパイル時間 2,676 ms
コンパイル使用メモリ 81,880 KB
実行使用メモリ 80,736 KB
最終ジャッジ日時 2025-02-11 16:31:11
合計ジャッジ時間 7,131 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other RE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def search(x):  # a * a <= y を満たす最大のaを求める
    lb = 1
    ub = x + 1
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if mid * mid <= x:
            lb = mid
        else:
            ub = mid
    return lb

def dfs(x,y,n):
    global ans,tmp,ans2
    if n >= ans:
        return
    if x == 0:
        if ans > n:
            ans = n
            ans2 = tmp[:]
        return
    if y == 1:
        if ans > n + x:
            ans = n + x
            ans2 = tmp + [1] * x
        return
    ret = 0
    if x - y * y >= 0:
        tmp.append(y)
        dfs(x - y * y, y, n + 1)
        tmp.pop()
    y -= 1
    if x // (y * y) + n < 16:
        dfs(x, y, n)

tmp = []
ans2 = []
S = int(input())
ans = S + 1
y = search(S)
dfs(S,y,0)
print(ans)
ans2 = [i*i for i in ans2]
print(*ans2)
0