結果
問題 |
No.831 都市めぐり
|
ユーザー |
👑 ![]() |
提出日時 | 2021-03-03 03:19:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 162 ms / 2,000 ms |
コード長 | 981 bytes |
コンパイル時間 | 195 ms |
コンパイル使用メモリ | 82,456 KB |
実行使用メモリ | 171,468 KB |
最終ジャッジ日時 | 2024-10-03 03:05:40 |
合計ジャッジ時間 | 2,522 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
def dist(i,j): if i==j: return 0 else: return i*j-(j-i) from itertools import permutations N=int(input()) if N<=8: X=[] Ans=float("Inf") for p in permutations(range(2,N+1)): p=(1,)+p+(1,) Money=0 for i in range(N): Money+=dist(p[i],p[i+1]) if Money<Ans: Ans=Money X=[p] elif Money==Ans: X.append(p) elif N%2==1: X=[1,N] for k in range(2,N,2): X+=[k,N-k] Ans=0 for i in range(N): Ans+=dist(X[i],X[i+1]) elif N%4==0: X=[1,N] for k in range(2,N//2,2): X+=[k,N-k] X+=[N//2] for k in range(N//2+1,N,2): X+=[k,N-k] Ans=0 for i in range(N): Ans+=dist(X[i],X[i+1]) elif N%4==2: X=[1,N] for k in range(2,N//2,2): X+=[k,N-k] X+=[N//2] for k in range(N//2+2,N,2): X+=[k,N-k] Ans=0 for i in range(N): Ans+=dist(X[i],X[i+1]) print(Ans)