結果
問題 | No.334 門松ゲーム |
ユーザー |
![]() |
提出日時 | 2016-01-15 23:15:59 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 658 bytes |
コンパイル時間 | 566 ms |
コンパイル使用メモリ | 6,912 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-19 19:27:43 |
合計ジャッジ時間 | 1,336 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
from itertools import combinations as combN = int(raw_input())K = map(int,raw_input().split())memo = dict()def check(a,b,c):return (K[a]-K[b])*(K[c]-K[b])>0 and K[a] != K[c]def dfs(k):if bin(k).count("1") < 3:return Falseif k not in memo:l = [i for i in xrange(N) if ((1<<i)&k) != 0]tmp = Falsefor a,b,c in comb(l,3):if check(a,b,c):nk = k - (1<<a) - (1<<b) - (1<<c)tmp |= not dfs(nk)memo[k] = tmpreturn memo[k]ans = []for a,b,c in comb(range(N),3):if check(a,b,c) and not dfs((1<<N) - 1 - (1<<a) - (1<<b) - (1<<c)):ans.append((a,b,c))if ans:ans.sort()print ans[0][0],ans[0][1],ans[0][2]else:print -1