問題一覧 > 通常問題

No.910 Prime Subsequence

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 193
作問者 : ei1333333 / テスター : treeone
お気に入りにしたユーザー ProblemId : 3306 / 自分の提出
問題文最終更新日: 2019-10-18 03:11:37
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 228 (順位表) の他の問題:

Problem Statement

There is a string $S$ of length $N$ consisting of 1, 3, 5, 7, 9.

You want to perform the following operation as many times as possible.

  • Choose $1$ subsequence of $S$ that is a prime number when the sequence is regarded as a value, and delete it.

The chosen subsequence does not have to be contiguous.

Find the maximum number of operations.

Input

$N$
$S$
  • $1 \leq N \leq 2 \times 10^5$
  • $S$ is a string of length $N$ consisting of 1, 3, 5, 7, 9
  • $N$ is an integer

Output

Print the answer on $1$ line.

Sample

Sample 1
Input
6
993711
Output
3

For example, you can perform the operations as follows.

  • 993711 $\rightarrow$ 9311 $\rightarrow$ 911 $\rightarrow$ 9 (the underlined characters are the chosen subsequence)

$97$, $3$, $11$ are all prime numbers.

Sample 2
Input
5
99999
Output
0

No subsequence is a prime number, so the operation cannot be performed even $1$ time.

Sample 3
Input
4
1333
Output
3

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。