結果
問題 | No.1837 Same but Different |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2022-02-12 01:21:27 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,542 bytes |
コンパイル時間 | 1,242 ms |
コンパイル使用メモリ | 86,584 KB |
実行使用メモリ | 76,424 KB |
最終ジャッジ日時 | 2023-09-10 09:00:59 |
合計ジャッジ時間 | 7,711 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,012 KB |
testcase_01 | AC | 69 ms
71,108 KB |
testcase_02 | WA | - |
testcase_03 | AC | 69 ms
70,880 KB |
testcase_04 | WA | - |
testcase_05 | AC | 299 ms
75,628 KB |
testcase_06 | AC | 296 ms
76,396 KB |
testcase_07 | WA | - |
testcase_08 | AC | 301 ms
75,776 KB |
testcase_09 | AC | 300 ms
76,044 KB |
testcase_10 | WA | - |
testcase_11 | AC | 301 ms
75,892 KB |
testcase_12 | AC | 298 ms
76,364 KB |
testcase_13 | WA | - |
testcase_14 | AC | 299 ms
75,844 KB |
testcase_15 | AC | 121 ms
75,948 KB |
testcase_16 | WA | - |
testcase_17 | AC | 98 ms
76,032 KB |
testcase_18 | AC | 164 ms
76,296 KB |
testcase_19 | AC | 143 ms
75,892 KB |
testcase_20 | WA | - |
testcase_21 | AC | 144 ms
75,864 KB |
testcase_22 | WA | - |
testcase_23 | AC | 118 ms
75,908 KB |
ソースコード
""" 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 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) 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 #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)