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