Solution
A price rounds to \(P_i\) exactly when
\[ P_i-500 \le Q_iX < P_i+500. \]
Because \(X\) is an integer, the smallest value allowed by this menu item is
\[ \left\lceil\frac{P_i-500}{Q_i}\right\rceil. \]
\(X\) must satisfy every item, so the answer is the maximum of these lower bounds. The statement guarantees that the resulting constraints are consistent.
The complexity is \(O(N)\) time and \(O(1)\) memory.
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long answer = 0;
while (n--) {
long long quantity, price;
cin >> quantity >> price;
long long minimumPrice =
(price - 500 + quantity - 1) / quantity;
answer = max(answer, minimumPrice);
}
cout << answer << '\n';
}