الجمال

الجمال

الأولمبياد الوطني للبرمجة 2026 - المسابقة الثانية

الزمن المحدد: 1 ثانية
الذاكرة المحددة: 256 ميجابايت

يُقال عن العدد إنه جميل إذا كانت جميع أرقامه مختلفة. مثلًا، الأعداد \(123\) و\(5926\) و\(9\) جميلة، بينما \(121\) و\(99\) و\(1090\) ليست جميلة.

أُعطيت عددين صحيحين موجبين \(m\) و\(n\). احسب عدد الأعداد الجميلة بين \(m\) و\(n\) شاملًا الطرفين.

المدخلات

يحتوي السطر الوحيد على \(m\) و\(n\)، حيث \(1 \le m \le n \le 10^7\).

المخرجات

اطبع عدد الأعداد الجميلة بين \(m\) و\(n\).

التقييم

المهمة الفرعية	القيود الإضافية	النقاط
\(1\)	\(m=n\le100\)	\(7\)
\(2\)	\(n\le100\)	\(11\)
\(3\)	\(m=n\le1000\)	\(13\)
\(4\)	\(n\le1000\)	\(14\)
\(5\)	\(n-m\le10^5\)	\(19\)
\(6\)	\(n\le10^6\)	\(16\)
\(7\)	لا توجد قيود إضافية	\(20\)

مثال

المدخلات

90 130

المخرجات

26

ملاحظة

يوجد \(41\) عددًا من \(90\) إلى \(130\). منها \(15\) عددًا لا تختلف جميع أرقامه: \(99,100,101,110,111,112,113,114,115,116,117,118,119,121,122\). إذن الإجابة \(41-15=26\).

الحل

لتكن \(F(x)\) عدد الأعداد الجميلة الموجبة التي لا تتجاوز \(x\)؛ إذن الإجابة \(F(n)-F(m-1)\). احسب \(F\) ببرمجة ديناميكية على الخانات من اليسار إلى اليمين، واحفظ بقناع بتات الأرقام المستخدمة. الأصفار البادئة ليست خانات، ولا يجوز اختيار رقم سبق استخدامه. عدد الحالات \(O(8\cdot2^{10})\) ولكل حالة عشرة انتقالات على الأكثر.

#include <cstring>
#include <iostream>
#include <string>
using namespace std;

string digits;
long long memo[10][1 << 10][2];

long long countWays(int position, int mask, bool started, bool tight) {
    if (position == (int)digits.size()) {
        return started;
    }

    if (!tight && memo[position][mask][started] != -1) {
        return memo[position][mask][started];
    }

    int limit = tight ? digits[position] - '0' : 9;
    long long answer = 0;

    for (int digit = 0; digit <= limit; digit++) {
        bool nextTight = tight && (digit == limit);

        if (!started && digit == 0) {
            answer += countWays(position + 1, mask, false, nextTight);
        } else if ((mask & (1 << digit)) == 0) {
            answer += countWays(
                position + 1,
                mask | (1 << digit),
                true,
                nextTight
            );
        }
    }

    if (!tight) {
        memo[position][mask][started] = answer;
    }
    return answer;
}

long long countBeautiful(long long x) {
    if (x <= 0) return 0;
    digits = to_string(x);
    memset(memo, -1, sizeof(memo));
    return countWays(0, 0, false, true);
}

int main() {
    long long m, n;
    cin >> m >> n;
    cout << countBeautiful(n) - countBeautiful(m - 1) << '\n';
}