結果
問題 |
No.910 素数部分列
|
ユーザー |
![]() |
提出日時 | 2025-06-12 16:43:58 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,209 bytes |
コンパイル時間 | 412 ms |
コンパイル使用メモリ | 82,228 KB |
実行使用メモリ | 97,704 KB |
最終ジャッジ日時 | 2025-06-12 16:44:18 |
合計ジャッジ時間 | 5,091 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 WA * 45 |
ソースコード
def main(): import sys n = int(sys.stdin.readline()) s = sys.stdin.readline().strip() # Step 1: Count 3,5,7 and collect remaining characters count = 0 remaining = [] for c in s: if c in {'3', '5', '7'}: count += 1 else: remaining.append(c) n_remain = len(remaining) used = [False] * n_remain # Step 2: Greedily find '19' in remaining i = 0 while i < n_remain - 1: if not used[i] and not used[i+1] and remaining[i] == '1' and remaining[i+1] == '9': count += 1 used[i] = used[i+1] = True i += 2 else: i += 1 # Step 3: Greedily find 3-digit primes in remaining three_digit_primes = {'191', '199', '911', '919', '991'} i = 0 while i <= n_remain - 3: if not used[i] and not used[i+1] and not used[i+2]: substr = ''.join(remaining[i:i+3]) if substr in three_digit_primes: count += 1 used[i] = used[i+1] = used[i+2] = True i += 3 else: i += 1 else: i += 1 print(count) if __name__ == '__main__': main()