Codeforces Round #407 (Div. 2), problem: (B) Masha and geometric depression Solution in C

#include <iostream>
#include <map>
using namespace std;

map<long long, int> was;
map<long long, int> bad;

int main() {
long long b, q, l, m;
cin >> b >> q >> l >> m;
for(int i = 0; i < m; i++) {
long long a;
cin >> a;
bad[a] = 1;
}
if(q == 1 and bad[b] == 1) {
cout << 0 << endl;
return 0;
}
long long cur = b, ans = 0;
bool ok = (bad[0] == 1), ok1 = 0;
while(abs(cur) <= l) {
if(!bad[cur]) ok1 = 1;
if(cur == 0 and ok) break;
if(was[cur] == 1 and bad[cur] == 0) {
cout << “inf” << endl;
return 0;
}
if(was[cur] and !ok1) {
cout << 0 << endl;
return 0;
}
if(bad[cur] == 1) {
was[cur] = -1;
cur *= q;
continue;
}
was[cur] = 1;
ans++;
cur *= q;
}
cout << ans << endl;
return 0;
}

(Visited 59 times, 1 visits today)

About the Author:

Leave A Comment