Digit Queries

Digit Queries
CSES medium

اعتبر السلسلة اللانهائية الناتجة عن لصق جميع الأعداد الصحيحة الموجبة بالترتيب:

[ 1234567891011121314]

لدينا \(q\) استعلامات. في كل استعلام، يُعطى لك موقع \(k\) (مرقّم بداية من 1) داخل هذه السلسلة اللانهائية. مهمتك هي طباعة الخانة (digit) الموجودة في الموقع \(k\).

القيود:

  • \(1 \le q \le 1000\)
  • \(1 \le k \le 10^{18}\)

Solution

لا يمكننا بناء السلسلة اللانهائية فعليًا (ولا حتى بادئة بطول \(10^{18}\)). بدلًا من ذلك، نفكّر في كتل من الأعداد ذات نفس عدد الخانات.

1. تجميع الأعداد حسب عدد الخانات

  • الأعداد ذات الخانة الواحدة: من 1 إلى 9

    • عدد الأعداد: \(9\)
    • عدد الخانات الكلي: \(9 \cdot 1\)

  • الأعداد ذات الخانتين: من 10 إلى 99

    • العدد: \(90\)
    • الخانات: \(90 \cdot 2 = 180\)

  • الأعداد ذات الثلاث خانات: من 100 إلى 999

    • العدد: \(900\)
    • الخانات: \(900 \cdot 3 = 2700\)

بشكل عام، للأعداد ذات \(d\) خانات:

  • أول عدد له \(d\) خانات هو \(10^{d-1}\)
  • يوجد \(9 \cdot 10^{d-1}\) عددًا كهذا
  • تساهم هذه الكتلة بعدد إجمالي من الخانات يساوي \(9 \cdot d \cdot 10^{d-1}\)

لأي موضع \(k\):

  1. نبدأ بعدد خانات \(d = 1\) وبـ base = 1 (وهي \(10^{d-1}\)).

  2. نحسب block_len = 9 * base * d وهو عدد الخانات الكلي في كتلة الأعداد ذات \(d\) خانات.

  3. إذا كان k > block_len، فهذا يعني أن الموضع ليس في هذه الكتلة، فنطرح حجمها وننتقل للكتلة التالية:

    • k -= block_len
    • نزيد d++، ونضرب base *= 10 (ننتقل إلى أعداد ذات d+1 خانات)

  4. نتوقف عندما يصبح k <= block_len، أي أن الموضع داخل الكتلة الحالية.

الآن نعلم أن:

  • الخانة المطلوبة تقع ضمن كتلة الأعداد ذات \(d\) خانات،
  • بداية هذه الكتلة هي start = base = 10^{d-1}.

2. تحديد العدد نفسه والخانة داخله

داخل كتلة الأعداد ذات \(d\) خانات:

  • نستخدم ترقيمًا يبدأ من الصفر داخل الكتلة:

    • k0 = k - 1 (موضع 0-based داخل الكتلة)
    • index_of_number = k0 / d (أي عدد داخل الكتلة)
    • index_in_number = k0 % d (أي خانة داخل هذا العدد)

  • العدد الفعلي هو:

    • num = start + index_of_number

  • لاستخراج الخانة المطلوبة:

    • نحوّل num إلى نص ونأخذ الحرف رقم index_in_number، أو
    • نستخدم عمليات القسمة والباقي لاستخراج الخانة.

ضمن القيود المعطاة، استخدام تحويل num إلى سلسلة نصية في ++C مقبول تمامًا.

3. التعقيد

لكل استعلام:

  • قيمة d لن تتجاوز تقريبًا 17 (لأن \(k \le 10^{18}\))، لذا حلقة البحث عن الكتلة تعمل في زمن ثابت تقريبًا.
  • كل العمليات على نوع long long وسلاسل نصية قصيرة.

إجمالي التعقيد: \(O(q)\).

Noteمنطق كتل الخانات (لكل استعلام)

  • نجد \(d\) بحيث يقع \(k\) ضمن كتلة الأعداد ذات \(d\) خانات:

    • نكرر:

      • block_len = 9 * base * d

      • إذا كان k > block_len:

        • k -= block_len
        • d++
        • base *= 10

  • ثم نحسب:

    • k0 = k - 1
    • index_of_number = k0 / d
    • index_in_number = k0 % d
    • num = base + index_of_number
    • الجواب = الخانة رقم index_in_number من العدد num.
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;

    while (q--) {
        long long k;
        cin >> k;

        long long d = 1;       // current digit length
        long long base = 1;    // 10^(d-1)

        // Step 1: find the block (digit length d) that contains position k
        while (true) {
            long long count_numbers = 9 * base;      // how many d-digit numbers
            long long block_len = count_numbers * d; // total digits in this block

            if (k > block_len) {
                k -= block_len;
                d++;
                base *= 10;
            } else {
                break; // k is inside this block
            }
        }

        // Step 2: find the exact number and digit within this d-digit block
        long long k0 = k - 1;                 // 0-based index within this block
        long long index_of_number = k0 / d;   // which number in this block
        long long index_in_number = k0 % d;   // which digit inside that number

        long long num = base + index_of_number;

        // Convert number to string and pick the right digit
        string s = to_string(num);
        char answer_digit = s[index_in_number];

        cout << answer_digit << endl;
    }

    return 0;
}
Cautionحذر من تجاوز السعة
  • استخدم نوع long long لكل من k وbase وblock_len.
  • في هذه المسألة، لا نحتاج أن يتجاوز d القيمة 17 عندما \(k \le 10^{18}\)، لذا فإن القيمة 9 * base * d تبقى ضمن حدود نوع long long.