قائمة الشاورما
الزمن المحدد: 0.5 ثانية الذاكرة المحددة: 256 ميجابايت
السعر الحقيقي لشاورما واحدة هو \(X\) ريالًا، وهو عدد صحيح، لكن لا أحد يشتري شاورما واحدة فقط. لذلك تعرض عربة شاورما حميد قائمتها كما يلي.
تحتوي القائمة على \(N\) عناصر على الشكل: “\(Q\) شاورما مقابل \(P\) ريال”، حيث إن \(P\) يساوي \(Q \cdot X\) بعد تقريبه إلى أقرب ألف.
على سبيل المثال، إذا كان \(X = 67\)، فقد تكون القائمة كما يلي:
- \(100\) شاورما مقابل \(7000\) ريال.
- \(200\) شاورما مقابل \(13000\) ريال.
- \(300\) شاورما مقابل \(20000\) ريال.
- \(512\) شاورما مقابل \(34000\) ريال.
المدخلات
يحتوي السطر الأول على عدد صحيح واحد \(N\)، وهو عدد عناصر القائمة، حيث \(1 \le N \le 10^5\).
يحتوي كل واحد من الأسطر الـ \(N\) التالية على عددين صحيحين: \(Q_i\) و\(P_i\)، وهما الكمية والسعر لعنصر القائمة رقم \(i\)، حيث \(1 \le Q_i \le 10^9\) و\(1000 \le P_i \le 10^9\).
ويُضمن أن \(P_i\) من مضاعفات \(1000\).
المخرجات
اطبع أقل قيمة ممكنة لـ \(X\)، وهي السعر الحقيقي لشاورما واحدة.
يُضمن أن \(X \le 10^9\).
التقييم
| المهمة الفرعية | القيود | النقاط |
|---|---|---|
| \(1\) | \(N = 1\) | \(10\) |
| \(2\) | \(N = 2\) | \(20\) |
| \(3\) | \(N \le 1000,\ X \le 1000\) | \(30\) |
| \(4\) | \(1000 < N \le 10^5\) | \(40\) |
أمثلة
المدخلات
2
100 7000
200 13000المخرجات
65الملاحظات
يُقرّب العدد الصحيح \(Z\) إلى أقرب ألف بفحص باقي قسمته على \(1000\). إذا كان الباقي أقل من \(500\) فإن \(P = \left\lfloor \frac{Z}{1000} \right\rfloor \cdot 1000\)، وإلا فإن \(P = \left\lceil \frac{Z}{1000} \right\rceil \cdot 1000\).
الحل
يُقرّب السعر إلى \(P_i\) بالضبط عندما \(P_i-500\le Q_iX<P_i+500\). ولأن \(X\) صحيح، فأصغر قيمة يسمح بها الصنف هي \(\left\lceil(P_i-500)/Q_i\right\rceil\). يجب أن يحقق \(X\) كل الأصناف، فالإجابة أكبر هذه الحدود الدنيا، والمسألة تضمن اتساق القيود. التعقيد \(O(N)\) زمنيًا و\(O(1)\) للذاكرة.
#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';
}