الطالب المتوسط
الزمن المحدد: 1 ثانية الذاكرة المحددة: 256 ميجابايت
يعرف معلمك أنك جيد في حل المسائل، لذلك أعطاك تحديًا أصعب قليلًا من المعتاد.
أُعطيت عددًا صحيحًا \(n\). مهمتك هي إنشاء تبديلة للأعداد من \(1\) إلى \(n\).
لكن المعلم يضيف شرطًا خاصًا: يجب أن تكون التبديلة “مستقرة”، أي ألا تُكوّن أي ثلاثة عناصر متتالية متوالية حسابية.
التبديلة هي ترتيب للأعداد من \(1\) إلى \(n\) بحيث يظهر كل عدد مرة واحدة بالضبط.
بعبارة أخرى، لكل فهرس \(i\) بحيث \(2 \le i \le n-1\)، يجب أن يتحقق \(p[i] \cdot 2 \ne p[i-1] + p[i+1]\).
إذا وُجدت عدة تبديلات صحيحة، يمكنك طباعة أي واحدة منها.
المدخلات
عدد صحيح واحد \(n\)، حيث \(1 \le n \le 10^6\).
المخرجات
اطبع سطرًا واحدًا يحتوي على تبديلة طولها \(n\) تحقق الشرط.
إذا وُجدت عدة إجابات صحيحة، اطبع أي واحدة منها.
التقييم
في هذه المسألة، يتم تقييم كل حالة اختبار بشكل مستقل. نتيجتك هي مجموع الدرجات لجميع حالات الاختبار.
أمثلة
المدخلات
1المخرجات
1المدخلات
5المخرجات
3 4 1 2 5الملاحظات
عندما \(n = 1\)، تكون الإجابة ببساطة \([1]\).
عندما \(n = 5\)، إحدى البنى الصحيحة هي \([3,4,1,2,5]\).
نتحقق من كل ثلاثية متتالية:
- \((3,4,1)\) ليست متوالية حسابية.
- \((4,1,2)\) ليست متوالية حسابية.
- \((1,2,5)\) ليست متوالية حسابية.
لذلك فإن الشرط محقق.
الحل
ابدأ بالتبديلة \([1]\). من تبديلة صحيحة، أضف أولًا كل القيم \(2x-1\) التي لا تتجاوز \(n\)، ثم كل القيم \(2x\). لو وُجدت متوالية حسابية بين ثلاث قيم جديدة، فبعكس التحويل نحصل على متوالية في التبديلة السابقة. ولا يمكن لثلاثية تعبر بين الجزأين الفردي والزوجي أن تكون حسابية لاختلاف زوجية طرفيها. البناء \(O(N)\) زمنيًا وللذاكرة.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> permutation = {1};
while ((int)permutation.size() < n) {
vector<int> next;
next.reserve(n);
for (int x : permutation) {
if (2 * x - 1 <= n) {
next.push_back(2 * x - 1);
}
}
for (int x : permutation) {
if (2 * x <= n) {
next.push_back(2 * x);
}
}
permutation.swap(next);
}
for (int x : permutation) {
cout << x << ' ';
}
cout << '\n';
}