結果

問題 No.873 バイナリ、ヤバいなり！ｗ
コンテスト
ユーザー rlangevin
提出日時 2023-10-19 12:49:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,326 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 76,416 KB
最終ジャッジ日時 2024-09-19 08:56:00
合計ジャッジ時間 10,086 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    N = int(input())
    M = int(N ** 0.5) + 2
    temp = []
    minv = 10 ** 18
    # for a in range(1, M):
    #     A = a * a
    #     if A > N:
    #         break
    #     if A == N:
    #         if a == minv:
    #             temp.append([a])
    #         elif a < minv:
    #             temp = [[a]]

    # for a in range(1, M):
    #     A = a * a
    #     if A > N:
    #         break
    #     for b in range(a, M):
    #         B = b * b
    #         if A + B > N:
    #             break
    #         if A + B == N:
    #             if a + b == minv:
    #                 temp.append([a, b])
    #             elif a + b < minv:
    #                 temp = [[a, b]]

    # for a in range(1, M):
    #     A = a * a
    #     if A > N:
    #         break
    #     for b in range(a, M):
    #         B = b * b
    #         if A + B > N:
    #             break
    #         for c in range(b, M):
    #             C = c * c
    #             if A + B + C > N:
    #                 break
    #             if A + B + C== N:
    #                 if a + b + c == minv:
    #                     temp.append([a, b, c])
    #                 elif a + b + c < minv:
    #                     temp = [[a, b, c]]

                
    for a in range(1, M):
        A = a * a
        if A > N or a > minv:
            break
        if A == N:
            if a == minv:
                temp.append([a])
            elif a < minv:
                temp = [[a]]
                minv = a
            break

        for b in range(a, M):
            B = b * b
            if A + B > N or a + b > minv:
                break
            if A + B == N:
                if a + b == minv:
                    temp.append([a, b])
                elif a + b < minv:
                    temp = [[a, b]]
                    minv = a + b
                break

            for c in range(b, M):
                C = c * c
                if A + B + C > N or a + b + c > minv:
                    break
                if A + B + C== N:
                    if a + b + c == minv:
                        temp.append([a, b, c])
                    elif a + b + c < minv:
                        temp = [[a, b, c]]
                        minv = a + b + c
                    break

                for d in range(c, M):
                    D = d * d
                    if A + B + C + D > N or a + b + c + d > minv:
                        break
                    if A + B + C + D == N:
                        if a + b + c + d == minv:
                            temp.append([a, b, c, d])
                        elif a + b + c + d < minv:
                            temp = [[a, b, c, d]]
                            minv = a + b + c + d
                        break

    def f(t):
        L = [None] * len(t)
        for i in range(len(t)):
            L[i] = (-(t[i]%2), t[i] * (-1) ** int(t[i]%2 == 0))
        L.sort()
        lst = []
        now = 0
        for _, a in L:
            a = abs(a)
            for i in range(a):
                lst.append(str(now))
                now = 1 - now
            now = 1 - now
        return "".join(lst)

    ans = None
    for t in temp:
        if ans is None:
            ans = f(t)
        else:
            ans = min(ans, f(t))
    print(ans)

main()
0