結果

問題 No.1837 Same but Different
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2022-02-12 01:25:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 301 ms / 2,000 ms
コード長 2,617 bytes
コンパイル時間 580 ms
コンパイル使用メモリ 86,920 KB
実行使用メモリ 76,276 KB
最終ジャッジ日時 2023-09-10 09:06:19
合計ジャッジ時間 6,281 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
70,828 KB
testcase_01 AC 68 ms
70,928 KB
testcase_02 AC 69 ms
71,100 KB
testcase_03 AC 70 ms
71,000 KB
testcase_04 AC 76 ms
75,796 KB
testcase_05 AC 292 ms
75,760 KB
testcase_06 AC 296 ms
76,188 KB
testcase_07 AC 78 ms
75,876 KB
testcase_08 AC 293 ms
75,780 KB
testcase_09 AC 298 ms
76,068 KB
testcase_10 AC 76 ms
75,948 KB
testcase_11 AC 294 ms
75,512 KB
testcase_12 AC 297 ms
76,040 KB
testcase_13 AC 79 ms
76,008 KB
testcase_14 AC 301 ms
75,644 KB
testcase_15 AC 121 ms
75,860 KB
testcase_16 AC 76 ms
75,840 KB
testcase_17 AC 98 ms
75,876 KB
testcase_18 AC 162 ms
75,960 KB
testcase_19 AC 146 ms
75,492 KB
testcase_20 AC 77 ms
76,276 KB
testcase_21 AC 138 ms
75,952 KB
testcase_22 AC 76 ms
76,188 KB
testcase_23 AC 116 ms
75,644 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

https://yukicoder.me/problems/no/1837

Aを3の倍数
Bを1 mod 3
とする

あとは総和を合わせないと…

Aに対して
+1,+1,+1,+1,+1,0,-2,-2,-2,-2,-2
でバランスを取れるか…

+1,+1,-2
でセットなので…

とりあえず

1000以上くらいの数字だけでA,Bを構築
あと、小さい要素を1 or 2個ずつ加えないといけない

1個はまじで困る
→4個にする

2個を考えたい

1,4 , 999,1002,1008
2,3 , 1000,1003,1006

あー
+1 が増えちゃう！！
→ 0,-1 で総裁


===答えを見た===

気合で頑張るのが正攻法

とりあえず
Aは全部 0 mod 3
Bは全部 1 mod 3
ここまではok
適当に構成したら、数字が合うように3を足していけばok

・N = 0 mod 3 の時
    そのままでok

・N = 1 mod 3 の時
    Aを1個 mod 1 にすればok

・N = 2 mod 3 の時
    Aを2個 mod 1 にする。
    この時, この2個の数字の和が Bのmin2個の和より小さければok

"""

import sys
from sys import stdin

def is_ok(A,B):

    assert sum(A) == sum(B)
    sa = set()
    for i in A:
        for j in A:
            sa.add(i+j)

    sb = set()
    for i in B:
        for j in B:
            sb.add(i+j)

    return sa & sb

N = int(stdin.readline())

if N % 3 == 0:

    btype = [-2] * (N//3) + [1] * (2*N//3)

    A = [3*(i+1) for i in range(N)]
    B = [A[i]+btype[i] for i in range(N)]

    print (" ".join(map(str,A)))
    print (" ".join(map(str,B)))
    print (is_ok(A,B) , file=sys.stderr)

elif N % 3 == 1:
    
    btype = [-2] * (N//3) + [1] * (N - N//3)
    A = [3*(i+1) for i in range(N)]
    B = [A[i]+btype[i] for i in range(N)]

    A[-1] += 7
    B[-1] += 3
    B[-2] += 3

    A.sort()
    B.sort()
    print (" ".join(map(str,A)))
    print (" ".join(map(str,B)))
    print (is_ok(A,B) , file=sys.stderr)

else:

    M = N-2

    btype = [-2] * (M//3) + [1] * (2*M//3)
    A = [3*(i+10) for i in range(M)]
    B = [A[i]+btype[i] for i in range(M)]

    A.append(1)
    A.append(4)
    B.append(B[-1] + 3)
    B.append(B[-1] + 3)


    Asum = sum(A)
    Bsum = sum(B)

    A.sort()
    B.sort()

    if Asum >= Bsum:
        B[-1] += Asum - Bsum
    else:
        rem = Bsum - Asum

        while rem > 0:
            for j in range(len(A)-1,1,-1):
                A[j] += 3
                rem -= 3
                if rem <= 0:
                    break
            
    A.sort()
    B.sort()
    #print (B[-1],A[-1])
    assert max(A) <= 10000
    assert max(B) <= 10000
    print (" ".join(map(str,A)))
    print (" ".join(map(str,B)))
    #print (is_ok(A,B) , file=sys.stderr)
0