مسألة المصافحة

مسألة المصافحة

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

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

يعيش مُعاذ وموسى في بيشة، وهي مدينة على شكل خط أعداد يمتد إلى ما لا نهاية في كلا الاتجاهين، حيث يُعدّ كل عدد صحيح موضعًا صالحًا.

يوجد \(Q\) جولة تتكرر في دورة، مرارًا وتكرارًا إلى ما لا نهاية. في الجولة \(i\)، يتحرك أحد الشخصين \(X_i\) خطوة: - إذا كانت \(T_i = 1\)، فإن مُعاذًا يتحرك. - إذا كانت \(T_i = 2\)، فإن موسى يتحرك.

إذا كانت \(X_i\) موجبة، فإنه يتحرك في الاتجاه الموجب. وإذا كانت \(X_i\) سالبة، فإنه يتحرك في الاتجاه السالب. في كلتا الحالتين، إذا كان الشخص في الموضع \(P\) حاليًا، فإنه ينتهي عند الموضع \(P + X_i\) بعد انتهاء الجولة.

لا يحدث انتقال آني، فالشخص يمشي خطوة واحدة في كل ثانية، متوقفًا عند كل موضع في طريقه. على سبيل المثال، إذا كان شخصٌ ما في الموضع \(3\) وتحرك \(+4\) خطوات، فإنه يمر بالمواضع \(4\) ثم \(5\) ثم \(6\)، ثم يستقر عند \(7\)، مستغرقًا \(4\) ثوانٍ في المجموع.

يبدأ مُعاذ من الموضع \(A\) ويبدأ موسى من الموضع \(B\). تُنفَّذ الجولات الـ \(Q\) بالترتيب (الجولة \(1\)، ثم الجولة \(2\)، …، ثم الجولة \(Q\))، ثم تعود مباشرةً لتبدأ من الجولة \(1\) مجددًا، ثم الجولة \(2\)، وهكذا إلى الأبد.

كلما تواجدا في الموضع نفسه في الثانية نفسها، فإنهما يتصافحان. أوجد الثانية الأولى التي يتصافحان فيها.

المدخلات

يحتوي السطر الأول على \(Q\) و\(A\) و\(B\)، حيث \((-10^6 \le A, B \le 10^6), (1 \le Q \le 5 \cdot 10^5)\).

تحتوي الأسطر الـ \(Q\) التالية على \(T_i\) و\(X_i\) في كل سطر، حيث \((T_i = 1 \text{ or } 2), (-10^6 \le X_i \le 10^6)\).

المخرجات

اطبع عددًا صحيحًا واحدًا، وهو الثانية التي ستحدث فيها أول مصافحة، أو اطبع \(-1\) إذا لم يحدث ذلك أبدًا.

التقييم

المجموعة	القيود	النقاط
\(1\)	إذا كانت \(T_i = 1\) فإن \(X_i \le 0\) وإلا \(X_i \ge 0\)	\(9\)
\(2\)	\((Q = 1), (-10^2 \le A, B, X_i \le 10^2)\)	\(16\)
\(3\)	\(\sum_{i:T_i=1} X_i = \sum_{i:T_i=2} X_i\)	\(15\)
\(4\)	\(Q = 1\)	\(26\)
\(5\)	إذا كانت \(T_i = 1\) فإن \(X_i \le 0\)	\(13\)
\(6\)	—	\(21\)

المجموعة الفرعية \(1\) تعني أن مُعاذًا يتحرك دائمًا في الاتجاه غير الموجب وأن موسى يتحرك دائمًا في الاتجاه غير السالب.

المجموعة الفرعية \(3\) تعني أن مُعاذًا وموسى يقطعان المسافة الإجمالية نفسها عبر جميع الجولات الـ \(Q\).

أمثلة

المدخلات

2 -5 4
1 2
2 -2

المخرجات

9

المدخلات

3 0 10
2 -1
1 1
2 1

المخرجات

26

ملاحظة

في حالة الاختبار الأولى، يحدث ما يلي في كل ثانية:

الثانية	مُعاذ	موسى
0	-5	4
1	-4	4
2	-3	4
3	-3	3
4	-3	2
5	-2	2
6	-1	2
7	-1	1
8	-1	0
9	0	0

الحل

تتبّع الموضع النسبي \(D=\text{موضع معاذ}-\text{موضع موسى}\). خلال الجولة يتحرك \(D\) بمقدار واحد في اتجاه ثابت كل ثانية، فتكوّن القيم المزارة فترة صحيحة. بعد دورة كاملة يتغير \(D\) بقيمة ثابتة \(\Delta\) وتستغرق الدورة \(L\) ثانية. لكل جولة، لتكن \([low,high]\) فترة الموضع النسبي في الدورة الأولى؛ في الدورة \(c\) تصبح \([low+c\Delta,high+c\Delta]\). استخدم القسمة الصحيحة إلى الأسفل والأعلى لإيجاد أصغر \(c\ge0\) تحتوي فيه الفترة الصفر، ثم خذ أبكر مرشح بين الجولات. التعقيد \(O(Q)\) زمنيًا وللذاكرة.

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

using int64 = long long;
using int128 = __int128_t;

struct Round {
    int64 change;
    int64 duration;
};

int64 floorDiv(int64 a, int64 b) {
    // b is positive.
    if (a >= 0) return a / b;
    return -((-a + b - 1) / b);
}

int64 ceilDiv(int64 a, int64 b) {
    return -floorDiv(-a, b);
}

void printInt128(int128 value) {
    if (value == 0) {
        cout << "0\n";
        return;
    }

    string digits;
    while (value > 0) {
        digits.push_back(char('0' + value % 10));
        value /= 10;
    }
    reverse(digits.begin(), digits.end());
    cout << digits << '\n';
}

int main() {
    int q;
    int64 a, b;
    cin >> q >> a >> b;

    vector<Round> rounds(q);
    int64 cycleChange = 0;
    int64 cycleLength = 0;

    for (Round& round : rounds) {
        int person;
        int64 x;
        cin >> person >> x;

        round.change = (person == 1 ? x : -x);
        round.duration = llabs(x);
        cycleChange += round.change;
        cycleLength += round.duration;
    }

    if (a == b) {
        cout << "0\n";
        return 0;
    }

    int64 relative = a - b;
    int64 timeInCycle = 0;
    const int128 INF = (int128(1) << 120);
    int128 answer = INF;

    for (const Round& round : rounds) {
        int64 start = relative;
        int64 finish = relative + round.change;
        int64 low = min(start, finish);
        int64 high = max(start, finish);

        bool possible = false;
        int64 cycle = 0;

        if (cycleChange == 0) {
            possible = (low <= 0 && 0 <= high);
        } else if (cycleChange > 0) {
            int64 first = max(0LL, ceilDiv(-high, cycleChange));
            int64 last = floorDiv(-low, cycleChange);
            if (first <= last) {
                possible = true;
                cycle = first;
            }
        } else {
            int64 step = -cycleChange;
            int64 first = max(0LL, ceilDiv(low, step));
            int64 last = floorDiv(high, step);
            if (first <= last) {
                possible = true;
                cycle = first;
            }
        }

        if (possible) {
            int64 shiftedStart = start + cycle * cycleChange;
            int64 secondsIntoRound = llabs(shiftedStart);
            int128 candidate = int128(cycle) * cycleLength
                            + timeInCycle + secondsIntoRound;
            answer = min(answer, candidate);
        }

        relative = finish;
        timeInCycle += round.duration;
    }

    if (answer == INF) {
        cout << -1 << '\n';
    } else {
        printInt128(answer);
    }
}