結果
| 問題 | No.6 使いものにならないハッシュ |
| ユーザー |
 fantasiabaetica
|
| 提出日時 | 2018-07-14 14:12:45 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,663 bytes |
| コンパイル時間 | 870 ms |
| コンパイル使用メモリ | 79,728 KB |
| 実行使用メモリ | 16,840 KB |
| 最終ジャッジ日時 | 2024-10-09 20:15:06 |
| 合計ジャッジ時間 | 13,185 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
ソースコード
#include <iostream>
#include <string.h>
#include <math.h>
#include <vector>
#include <set>
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
using namespace std;
// 素数かどうか調べる
int if_prime(int n){
if (n == 1) return 0;
int root_n = sqrt(n);
FOR(i, 2, root_n + 1){
if (n % i == 0) return 0;
}
return 1;
}
// hash値を調べる
int to_hash(int n){
while (true){
string a;
a = to_string(n);
if (a.length() == 1) return n;
n = 0;
FOR(i, 0, a.length()){
n += (a[i] - '0');
}
}
}
int main(){
int k, n;
cin >> k >> n;
// 素数のvector
vector<int> primes;
FOR(i, k, n + 1){
if (if_prime(i)) primes.push_back(i);
}
// 素数のhash値のvector
vector<int> prime_hash;
FOR(i, 0, primes.size()){
prime_hash.push_back(to_hash(primes[i]));
}
// 最長部分を求める
int max_length = 0;
int max_start = -1;
// 最長部分を求める
int dp[10];
memset(dp, 0, sizeof(dp));
// 内側のループを抜けた状態では[start, end)がハッシュ値がすべて異なる最長区間
int start = 0;
int end = 0;
while (start < primes.size()){
while (end < primes.size()) {
if (dp[prime_hash[end]] == 0) {
dp[prime_hash[end]] = 1;
end += 1;
} else {
break;
}
}
if (end - start >= max_length){
max_start = primes[start];
max_length = end - start;
}
dp[start] = 0;
}
cout << max_start << endl;
return 0;
}