yukicoder No.928 軽減税率?
想定解は 全探索ですが、100で割った余りを決め打ちする ( の形にする) とfloor関数が消え、 店内で食べるほうが安くなる場合に が満たすべき必要十分条件は1次不等式で表すことができます。そのため、 を全探索することで の値にかかわらず で解けます。実装はやや面倒。
int p, q, a; cin >> p >> q >> a; // special case: avoid division by zero if (p == q) { if (a > 0) { cout << (int)(1e+9) << endl; } else { cout << 0 << endl; } return; } ll ret = 0; for(int s=1; s<=100; s++) { int qs = q*s/100; int ps = p*s/100; if (p > q) { int k = qs-ps+a; if (k <= 0) continue; if (k%(p-q)==0) { ret += min(k/(p-q),(int)1e+7); } else { ret += min(k/(p-q)+1,(int)1e+7); } } else { int k = ps-qs-a; if (k < 0) { ret += 1e+7; continue; } ret += max(0, (int)(1e+7)-(k/(q-p)+1)); } } cout << ret << endl;