結果
問題 | No.2593 Reorder and Mod 120 |
ユーザー |
👑 |
提出日時 | 2023-12-21 20:40:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 1,927 bytes |
コンパイル時間 | 292 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 82,704 KB |
最終ジャッジ日時 | 2024-09-27 11:05:16 |
合計ジャッジ時間 | 2,652 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 26 |
ソースコード
def next_permutation(P): n = len(P) for i in range(n - 2, -1, -1): if P[i] < P[i + 1]: l = i + 1 r = n - 1 while r > l: P[l], P[r] = P[r], P[l] l += 1 r -= 1 for j in range(i + 1, n): if P[i] < P[j]: P[i], P[j] = P[j], P[i] return True return False def all_permutations(P): # 全列挙したい場合はソートしてある状態で渡す yield P while next_permutation(P): yield P def prev_permutation(P): n = len(P) for i in range(n - 2, -1, -1): if P[i] > P[i + 1]: l = i + 1 r = n - 1 while r > l: P[l], P[r] = P[r], P[l] l += 1 r -= 1 for j in range(i + 1, n): if P[i] > P[j]: P[i], P[j] = P[j], P[i] return True return False def rev_all_permutations(P): # 全列挙したい場合は逆順ソートしてある状態で渡す yield P while prev_permutation(P): yield P n = int(input()) S = list(map(int, input())) if n <= 3: tf = [False] * 120 S.sort() for P in all_permutations(S): tot = 0 for p in P: tot = tot * 10 + p tf[tot % 120] = True print(sum(tf)) else: cnt = [0] * 10 for s in S: cnt[s] += 1 tf = [False] * 40 for i in range(1, 10): if cnt[i] == 0: continue cnt[i] -= 1 for j in range(1, 10): if cnt[j] == 0: continue cnt[j] -= 1 for k in range(1, 10): if cnt[k] == 0: continue x = i * 100 + j * 10 + k tf[x % 40] = True cnt[j] += 1 cnt[i] += 1 print(sum(tf))