結果
問題 | No.910 素数部分列 |
ユーザー |
![]() |
提出日時 | 2019-10-18 23:29:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 1,000 ms |
コード長 | 1,958 bytes |
コンパイル時間 | 1,040 ms |
コンパイル使用メモリ | 116,040 KB |
最終ジャッジ日時 | 2025-01-07 23:53:53 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <algorithm>#include <cassert>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <cstdlib>#include <deque>#include <functional>#include <iomanip>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <set>#include <stack>#include <string>#include <unordered_map>#include <utility>#include <vector>using namespace std;using i64 = int64_t;#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define all(x) (x).begin(), (x).end()const int INF = (1 << 30);const i64 INFL = (1LL << 62);const i64 MOD = 1000000007;template <class T>T gcd(T a, T b) {return b ? gcd(b, a % b) : a;}template <class T>T lcm(T a, T b) {return a / gcd(a, b) * b;}template <class T>i64 mod_pow(i64 a, i64 n, T mod) {mod = (i64)mod;i64 res = 1, p = a % mod;while (n) {if (n & 1) res = res * p % mod;p = p * p % mod;n >>= 1;}return res;}void print() { std::cout << std::endl; }template <typename T, typename... A>void print(const T& first, const A&... rest) {cout << sizeof...(rest) << endl;std::cout << first;if (sizeof...(rest)) std::cout << " ";print(rest...);}template <typename... A>void print(const A&... rest) {print(rest...);}template <typename A>void print(const std::vector<A>& v) {std::for_each(v.begin(), v.end(), [](A x) { std::cout << x << " "; });std::cout << std::endl;}int main() {cin.tie(0);ios::sync_with_stdio(false);int n;cin >> n;string s;cin >> s;int ans = 0;int cnt_1 = 0;int cnt_9 = 0;rep(i, n) {if ((s[i] != '1') && (s[i] != '9')) {++ans;} else if (s[i] == '1') {cnt_1++;} else if (s[i] == '9') {cnt_9++;if (cnt_1 > 0) {cnt_1--;cnt_9--;ans++;}}}int cnt_991 = min(cnt_9 / 2, cnt_1);ans += cnt_991;ans += (cnt_1 - cnt_991) / 2;cout << ans << endl;return 0;}