結果

問題 No.6 使いものにならないハッシュ
コンテスト
ユーザー shisyamokongari
提出日時 2016-08-22 01:04:40
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0