結果

問題 No.910 素数部分列
コンテスト
ユーザー ntuda
提出日時 2025-01-01 11:30:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 61 ms / 1,000 ms
コード長 667 bytes
コンパイル時間 308 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 71,668 KB
最終ジャッジ日時 2025-01-01 11:30:49
合計ジャッジ時間 5,001 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
S = [int(s) for s in input()]
'''
3,5,7は単体で素数
9,1は組合せで素数
19でとれるものは優先
　最左の1と最右の9を取る
991で取れるものを取る
11で取れるものを取る
'''
ans = 0
na1, na9 = 0, 0
tmp = []
#3,5,7,19をカウント
for i, s in enumerate(S):
    if s == 9:
        if na1 > 0:
            na1 -= 1
            ans += 1
        else:
            na9 += 1
    elif s == 1:
        na1 += 1
    else:
        ans += 1
#99１をカウント
if na9 >= na1 * 2:
    ans += na1
    na1 = 0
    na9 -= na1 * 2
else:
    ans += na9 // 2
    na1 -= na9 // 2
#11 をカウント
ans += na1 // 2
print(ans)
0