#111981 (C++11) No.6 使いものにならないハッシュ

• 問題: No.6 使いものにならないハッシュ
• ユーザー: shisyamokongari
• 提出日時: 2016-08-22 01:04:40
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 4 ms / 5,000 ms
• コード長: 1,133 bytes
• コンパイル時間: 624 ms
• コンパイル使用メモリ: 65,520 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-16 16:36:00
• 合計ジャッジ時間: 1,534 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	3 ms; 5,248 KB
testcase_01	AC	4 ms; 5,376 KB
testcase_02	AC	4 ms; 5,376 KB
testcase_03	AC	3 ms; 5,376 KB
testcase_04	AC	3 ms; 5,376 KB
testcase_05	AC	4 ms; 5,376 KB
testcase_06	AC	4 ms; 5,376 KB
testcase_07	AC	4 ms; 5,376 KB
testcase_08	AC	3 ms; 5,376 KB
testcase_09	AC	4 ms; 5,376 KB
testcase_10	AC	3 ms; 5,376 KB
testcase_11	AC	3 ms; 5,376 KB
testcase_12	AC	4 ms; 5,376 KB
testcase_13	AC	3 ms; 5,376 KB
testcase_14	AC	4 ms; 5,376 KB
testcase_15	AC	4 ms; 5,376 KB
testcase_16	AC	3 ms; 5,376 KB
testcase_17	AC	4 ms; 5,376 KB
testcase_18	AC	4 ms; 5,376 KB
testcase_19	AC	4 ms; 5,376 KB
testcase_20	AC	4 ms; 5,376 KB
testcase_21	AC	3 ms; 5,376 KB
testcase_22	AC	4 ms; 5,376 KB
testcase_23	AC	4 ms; 5,376 KB
testcase_24	AC	4 ms; 5,376 KB
testcase_25	AC	3 ms; 5,376 KB
testcase_26	AC	3 ms; 5,376 KB
testcase_27	AC	3 ms; 5,376 KB
testcase_28	AC	3 ms; 5,376 KB
testcase_29	AC	4 ms; 5,376 KB
testcase_30	AC	4 ms; 5,376 KB
testcase_31	AC	4 ms; 5,376 KB

ソースコード

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

#define NMAX 200000

int main(){

	vector<int> sosuu,sosuu2,hash,cnt;
	int hurui[NMAX+1];
	int K,N;

	for(int i=0;i<=NMAX;i++) hurui[i]=0;
	hurui[0]=1,hurui[1]=1;

	for(int i=0;i<=NMAX;i++){
		if(hurui[i]==0){
			sosuu.push_back(i);
			for(int j=i*2;j<NMAX;j+=i) hurui[j]=1;
		}
	}

	cin>>K;
	cin>>N;

	for(int i=0;i<sosuu.size();i++){
		if(sosuu[i]>=K&&sosuu[i]<=N){
			sosuu2.push_back(sosuu[i]);
			hash.push_back(sosuu[i]);
			cnt.push_back(1);
		}
	}

	for(int i=0;i<hash.size();i++){
		while(hash[i]>=10){
			int tmpn=hash[i];
			int sum=0;
			while(tmpn!=0){
				sum+=tmpn%10;
				tmpn/=10;
			}
			hash[i]=sum;
		}
	}

	for(int i=0;i<hash.size();i++){
		int ok[10]={0};
		ok[hash[i]]=1;
		for(int j=1;j<=9;j++){
			if(i+j>=hash.size()) break;
			if(ok[hash[i+j]]) break;
			cnt[i+j]++;
			ok[hash[i+j]]=1;
		}
	}

	int ansmax=1;
	for(int i=0;i<cnt.size();i++){
		if(cnt[i]>ansmax) ansmax=cnt[i];
	}

	int ans=-1;
	for(int i=0;i<cnt.size();i++){
		if(cnt[i]==ansmax){
			if(ans<sosuu2[i-ansmax+1]) ans=sosuu2[i-ansmax+1];
		}
	}

	cout<<ans<<endl;
}