結果

問題 No.6 使いものにならないハッシュ
ユーザー sewoiwataki
提出日時 2018-02-21 23:18:17
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,676 bytes
コンパイル時間 538 ms
コンパイル使用メモリ 61,016 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-16 16:43:01
合計ジャッジ時間 1,394 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>

//#define DEBUG
#define NMAX 200000

using namespace std;

int c_hash(int a){
    while(a/10!=0){
        int tmp=0;
        while(a!=0){
            tmp+=a%10;
            a/=10;
        }
        a=tmp;
    }
    return a;
}
            
            

int main(){
    int K;
    int N;
    int hurui[NMAX+1];
    vector<int> p;
    vector<int> pans;
    bool num[10];
    int cnt;
    int maxcnt;
    int ans;

    cin>>K;
    cin>>N;

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

    for(int i=0;i<=N;i++){
        #ifdef DEBUG
            cout<<i<<endl;
        #endif
        if(hurui[i]==0){
            if(i>=K&&i<=N){
                p.push_back(c_hash(i));
                pans.push_back(i);
            }
            for(int j=i;j<=N;j+=i){
                hurui[j]=1;
            }
        }
    }

    ans=-1;
    cnt=0;
    maxcnt=0;
    for(int i=0;i<=9;i++) num[i]=false;
    for(int i=0;i<p.size();i++){
        #ifdef DEBUG
            cout<<"cnt:"<<cnt<<" p:"<<p[i]<<" num:";
            for(int j=0;j<=9;j++) cout<<num[j]<<",";
            cout<<endl;
        #endif
        if(num[p[i]]==true){
            while(num[p[i]]==true){
                #ifdef DEBUG
                    cout<<"i:"<<i<<" cnt:"<<cnt<<" p-:"<<p[i-cnt]<<"num:";
                    for(int j=0;j<=9;j++) cout<<num[j]<<",";
                    cout<<endl;
                #endif
                num[p[i-cnt]]=false;
                cnt--;
            }
        }
        num[p[i]]=true;
        cnt++;
        if(maxcnt<=cnt){
            maxcnt=cnt;
            ans=i-cnt+1;
        }
    }
    cout<<pans[ans]<<endl;
}
0