結果

問題 No.6 使いものにならないハッシュ
コンテスト
ユーザー drymouse
提出日時 2024-02-14 17:02:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 23 ms / 5,000 ms
コード長 2,016 bytes
コンパイル時間 716 ms
コンパイル使用メモリ 93,872 KB
最終ジャッジ日時 2025-02-19 13:06:01
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:88:13: warning: ‘maxfirst’ may be used uninitialized [-Wmaybe-uninitialized]
   88 |     cout << maxfirst << endl;
      |             ^~~~~~~~
main.cpp:54:9: note: ‘maxfirst’ was declared here
   54 |     int maxfirst;
      |         ^~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

bool is_prime(int a) {
    if (a < 4) {
        if (a == 1) {return false;}
        else {return true;}
    } else if (a % 2 == 0) {
        return false;
    }
    for (int i = 3; i < sqrt(a) + 2; i+=2) {
        if (a % i == 0) {return false;}
    }
    return true;
}

int sum_digit(int a) {
    int x = a;
    int sum = 0;
    for (int i = 0; i < 6; i++) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

int frank_hash(int a) {
    int sum = a;

    for (;sum > 9;) {
        sum = sum_digit(sum);
    }
    return sum;
}

void output(vector<int> a) {
    int l = a.size();
    cout << "[";
    for (int i = 0; i < l; i++) {
        cout << a[i] << ", ";
    }
    cout << "]" << endl;
}

int main(void) {
    int K, N;
    cin >> K >> N;
    //cout << sum_digit(K) << endl;
    //cout << frank_hash(K) << endl;

    int maxfirst;
    int maxlen = 0;
    int curlen = 0;
    vector<int> ps, hs;

    for (int i = K; i < N + 1; i++) {
        if (!is_prime(i)) {continue;}
        int h = frank_hash(i);
        bool is_exest = false;
        for (int j = 0; j < hs.size(); j++) {
            if (hs[j] == h) {
                if (curlen >= maxlen) {
                    maxlen = curlen;
                    maxfirst = ps[0];
                }
                curlen -= j + 1;
                ps.erase(ps.begin(), ps.begin() + j + 1);
                hs.erase(hs.begin(), hs.begin() + j + 1);
                is_exest = true;
                break;
            }
        }
        ps.push_back(i);
        hs.push_back(h);
        curlen++;
        //cout << i << ", " << h << ", " << curlen << ", " << maxlen << ", " << maxfirst << endl;
        //output(ps);
        //output(hs);
    }
    if (curlen >= maxlen) {
        maxlen = curlen;
        maxfirst = ps[0];
    }
    //cout << "max first: " << maxfirst << ", max len: " << maxlen << endl;
    cout << maxfirst << endl;

    return 0;
}
0