読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

codeforces 374 div2 B. Passwords

問題

問題概要

パスワードがいくつか与えれる。正解のpwも与えらる。パスワードを長さが短いものから順に試していく。このようにパスワードを試していったときに、最短なんか秒で答えのパスワードを入力することになるか、また、最大の場合も求める。ただし、パスワードを入力するのに、1秒かかり、k回失敗すると、5秒何もできない。

解法

最短は答えのpwと同じ長さで1個目に当たるとき、最長は答えと同じpwの中で、最後に当たるとき。pwの長さごとにいくつかるかを求める。 あとは、当たるまでに、何回pwを試さないといけないかを求め、その中で、5秒間休まないといけない場合が何回あるかを求めて、計算すればいい。

ミス

どこで本当のpw与えられるんですか、て感じだった。英語きつい。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

int cnt[110];

int main(void){
    int n, k; cin >> n >> k;
    vector<string> v;
    rep(i, n){
        string tm; cin >> tm;
        v.push_back(tm);
    }
    string ans; cin >> ans;
    sort(v.begin(), v.end());
    v.erase( unique(v.begin(), v.end()), v.end() );
    rep(i, 110) cnt[i] = 0;
    rep(i, v.size()){
        int num = v[i].size();
        cnt[num]++;
    }

    int mi, ma;
    int t = 0;
    rep(i, ans.size()){
        t += cnt[i];
    }
    mi = t + (t / k) * 5 + 1;
    int tmp = t + cnt[ans.size()] - 1;
    ma = tmp + (tmp / k) * 5 + 1;
    printf("%d %d\n", mi, ma);
    return 0;
}