結果
問題 | No.12 限定された素数 |
ユーザー | myanta |
提出日時 | 2017-04-30 22:48:20 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 1,072 ms / 5,000 ms |
コード長 | 1,597 bytes |
コンパイル時間 | 1,841 ms |
コンパイル使用メモリ | 43,764 KB |
実行使用メモリ | 19,144 KB |
最終ジャッジ日時 | 2023-08-16 00:15:14 |
合計ジャッジ時間 | 31,825 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,063 ms
18,328 KB |
testcase_01 | AC | 1,070 ms
18,136 KB |
testcase_02 | AC | 1,065 ms
18,580 KB |
testcase_03 | AC | 1,040 ms
18,648 KB |
testcase_04 | AC | 1,069 ms
18,504 KB |
testcase_05 | AC | 1,067 ms
17,800 KB |
testcase_06 | AC | 1,069 ms
17,604 KB |
testcase_07 | AC | 1,066 ms
18,376 KB |
testcase_08 | AC | 1,069 ms
17,608 KB |
testcase_09 | AC | 1,071 ms
17,868 KB |
testcase_10 | AC | 1,066 ms
18,432 KB |
testcase_11 | AC | 1,066 ms
17,828 KB |
testcase_12 | AC | 1,066 ms
17,788 KB |
testcase_13 | AC | 1,072 ms
18,944 KB |
testcase_14 | AC | 1,067 ms
18,924 KB |
testcase_15 | AC | 1,067 ms
17,872 KB |
testcase_16 | AC | 1,063 ms
17,580 KB |
testcase_17 | AC | 1,063 ms
17,540 KB |
testcase_18 | AC | 1,059 ms
18,144 KB |
testcase_19 | AC | 1,059 ms
18,124 KB |
testcase_20 | AC | 1,068 ms
17,884 KB |
testcase_21 | AC | 1,068 ms
18,592 KB |
testcase_22 | AC | 1,061 ms
19,144 KB |
testcase_23 | AC | 1,064 ms
18,176 KB |
testcase_24 | AC | 1,066 ms
17,696 KB |
testcase_25 | AC | 1,066 ms
18,096 KB |
ソースコード
#include<cstdio> #include<vector> using namespace std; #define L_MAX 5000000 class prime_t { public: int x; int c[10]; prime_t(int x) { int i; for(i=0;i<10;i++) c[i]=0; this->x=x; for(;x;x/=10) { c[x%10]=1; } } }; vector<prime_t> prime; void init(void) { int i, j; prime.clear(); prime.reserve(L_MAX/4); prime.push_back(prime_t(0)); prime.push_back(prime_t(2)); for(i=3;i<=L_MAX;i+=2) { for(j=3;j*j<=i;j+=2) { if(i%j==0) break; } if(j*j>i) { prime.push_back(prime_t(i)); } } prime.push_back(prime_t(L_MAX+1)); } int max_u(int& m, int v) { if(m<v) { m=v; return 1; } return 0; } int main(void) { int n, i; vector<int> a, b, c, f; int ps, pe, max, d, k, l, ok, ng; init(); while(scanf("%d", &n)==1) { a.resize(n); f.clear(); f.resize(10); c.clear(); c.resize(10); for(i=0;i<n;i++) { scanf("%d", &a[i]); f[a[i]]=1; } ok=ng=0; max=-1; ps=1; for(pe=1;pe+1<prime.size();pe++) { for(i=0;i<10;i++) { d=prime[pe].c[i]; if(d==0) continue; if(c[i]==0) { if(f[i]) ok++; else ng++; } c[i]++; } if(ok==n) { for(;ps<=pe;ps++) { if(ng==0) break; for(i=0;i<10;i++) { d=prime[ps].c[i]; if(d==0) continue; c[i]--; if(c[i]==0) { if(f[i]) ok--; else ng--; } } } } if(ok==n && ng==0) { k=prime[ps-1].x+1; l=prime[pe+1].x-1; if(max_u(max, l-k)) { // printf("l=%d k=%d max=%d\n", l, k, max); } } } printf("%d\n", max); } return 0; }