Xe lôi (Đề tự luyện HSG Tin 12 – Bài 1)

Nguồn: Đề tự luyện HSG Tin học 12 – Bài 1 (đề tự soạn)Độ khó: DễĐồ thị hàmTìm chu trìnhMô phỏngChia lấy phần nguyên

Đề bài

Xe lôi. Thị trấn có $N$ trạm xe lôi. Từ trạm $i$ chỉ có đúng một tuyến, chở tới trạm $t_i$ ($t_i \ne i$) với giá vé $c_i$ nghìn đồng. Thầy Sơn xuất phát ở trạm $1$ với $M$ nghìn đồng; đang ở trạm $i$ mà số tiền còn lại $\ge c_i$ thì thầy trả $c_i$ và đi tới $t_i$, ngược lại thầy dừng. Hỏi thầy đi được bao nhiêu chuyến và dừng ở trạm nào?

Dữ liệu vào: dòng đầu $N, M$ ($2 \le N \le 2 \cdot 10^5$, $1 \le M \le 10^{18}$); dòng hai $t_1, \ldots, t_N$; dòng ba $c_1, \ldots, c_N$ ($1 \le c_i \le 10^9$).

Kết quả: số chuyến xe lôi và số hiệu trạm dừng lại.

• Subtask 1 (30%): $M \le 10^6$.
• Subtask 2 (30%): các $t_i$ đôi một khác nhau.
• Subtask 3 (40%): không có ràng buộc gì thêm.

Input

7 50
7 5 2 7 3 2 5
1 8 4 8 3 9 3

Output

11 5

Giải thích

Thầy đi $1 \to 7 \to 5$, rồi ba lượt $5 \to 3 \to 2 \to 5$; tiền còn lại lần lượt $49, 46, 43, 39, 31, 28, 24, 16, 13, 9, 1$. Sau $11$ chuyến thầy ở trạm $5$, còn $1$ nghìn đồng, không đủ trả vé $c_5 = 3$.

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Xe lôi

Lời mở đầu

Bài "khởi động" của đề. Đọc xong thấy ngay cách làm: cứ mô phỏng thầy Sơn đi từng chuyến là ra. Vấn đề duy nhất là $M$ tới $10^{18}$ còn giá vé có thể chỉ $1$ nghìn – nghĩa là thầy có thể đi tới $10^{18}$ chuyến, mô phỏng tới tết năm sau cũng chưa xong 😅. Vậy phải "nhìn" ra hình dạng đường đi của thầy.

Nhận xét quan trọng. Từ mỗi trạm chỉ có đúng một tuyến đi ra, nên đứng ở trạm nào thì chuyến kế tiếp đã được định sẵn. Có $N$ trạm, nên trong $N + 1$ trạm đầu tiên thầy ghé chắc chắn có một trạm bị lặp lại (nguyên lý Dirichlet). Và kể từ lúc quay lại một trạm đã ghé, thầy sẽ đi lặp lại y hệt đoạn đường cũ mãi mãi. Đường đi của thầy có hình chữ $\rho$ (đọc là "rô"): một đoạn đuôi đi một lần rồi một vòng lặp đi lặp lại.

Hình 1. Đường đi của thầy Sơn trong ví dụ. Trạm $1$ không nằm trên vòng – đây chính là cái bẫy của bài.

Ba cách dưới đây đi từ chậm đến nhanh:

Cách 1Mô phỏng từng chuyến · 30%Cách 2Hoán vị: đi một vòng về trạm 1 · 60%Cách 3Đuôi + vòng · 100%

Cách 1Mô phỏng từng chuyến – O(số chuyến) · 30%

Làm đúng như đề kể: đang ở trạm cur mà m >= c[cur] thì trừ tiền, sang trạm t[cur], tăng số chuyến. Mỗi chuyến tốn ít nhất $1$ nghìn nên số chuyến không vượt quá $M$; với $M \le 10^6$ vòng lặp chạy tối đa $10^6$ lần – quá nhẹ.

Chú ý điều kiện là "không nhỏ hơn", tức >=: còn đúng $c_i$ nghìn thì thầy vẫn đi được (và về $0$ đồng).

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; long long m; cin >> n >> m;
    vector<int> t(n + 1); vector<long long> c(n + 1);
    for (int i = 1; i <= n; i++) cin >> t[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    long long step = 0; int cur = 1;
    while (m >= c[cur]) { m -= c[cur]; cur = t[cur]; step++; }
    cout << step << " " << cur << "\n";
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); m = int(data[1])
    t = [0] + [int(x) for x in data[2:2 + n]]
    c = [0] + [int(x) for x in data[2 + n:2 + 2 * n]]
    step = 0; cur = 1
    while m >= c[cur]:           # con du tien thi di tiep
        m -= c[cur]; cur = t[cur]; step += 1
    sys.stdout.write("%d %d\n" % (step, cur))


main()

Không gian$O(N)$

Thời gian$O(N + \text{số chuyến}) \le O(N + M)$

Cách 2Các t_i đôi một khác nhau: đi một vòng từ trạm 1 – O(N) · 60%

Khi $t_1, \ldots, t_N$ đôi một khác nhau, mỗi trạm có đúng một tuyến đi vào (ngoài đúng một tuyến đi ra). Đi từ trạm $1$, trạm đầu tiên bị lặp lại chỉ có thể là chính trạm $1$: nếu là trạm $v \ne 1$ thì $v$ có hai tuyến đi vào (một từ lần ghé trước, một từ lần này) – vô lý. Vậy trạm 1 nằm trên vòng, đường đi không có đuôi.

Ta đi thử một vòng từ trạm $1$ về lại trạm $1$, đếm số chuyến $L$ và tổng tiền vé $C$ của vòng. Mỗi vòng trọn vẹn đưa thầy về trạm $1$ và tốn đúng $C$ nên thầy đi trọn $\left\lfloor \frac{M}{C} \right\rfloor$ vòng, được $\left\lfloor \frac{M}{C} \right\rfloor \cdot L$ chuyến, còn lại $M \bmod C$ nghìn. Phần còn lại không đủ một vòng nên mô phỏng thêm dưới $L$ chuyến là xong.

Cẩn thận tràn số

$C$ có thể tới $2 \cdot 10^5 \cdot 10^9 = 2 \cdot 10^{14}$, số chuyến tới $10^{18}$: mọi biến đếm tiền và đếm chuyến phải là long long.

Code dưới đây gộp luôn Cách 1 (khi $M \le 10^6$):

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; long long m; cin >> n >> m;
    vector<int> t(n + 1); vector<long long> c(n + 1);
    for (int i = 1; i <= n; i++) cin >> t[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    long long step = 0; int cur = 1;
    if (m > 1000000) {                       // t la hoan vi: tram 1 nam tren vong
        long long L = 0, C = 0;
        int x = 1;
        do { C += c[x]; x = t[x]; L++; } while (x != 1);   // di het mot vong ve lai tram 1
        step = (m / C) * L;
        m %= C;
    }
    while (m >= c[cur]) { m -= c[cur]; cur = t[cur]; step++; }   // mo phong phan con lai
    cout << step << " " << cur << "\n";
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); m = int(data[1])
    t = [0] + [int(x) for x in data[2:2 + n]]
    c = [0] + [int(x) for x in data[2 + n:2 + 2 * n]]
    step = 0; cur = 1
    if m > 1000000:              # t la hoan vi: tram 1 nam tren vong
        L = 0; C = 0; x = 1
        while True:              # di het mot vong ve lai tram 1
            C += c[x]; x = t[x]; L += 1
            if x == 1:
                break
        step = (m // C) * L
        m %= C
    while m >= c[cur]:           # mo phong phan con lai
        m -= c[cur]; cur = t[cur]; step += 1
    sys.stdout.write("%d %d\n" % (step, cur))


main()

Không gian$O(N)$

Thời gian$O(N)$ (khi $M > 10^6$)

Vì sao Cách 2 không qua Subtask 3?

Khi trạm $1$ nằm trên đoạn đuôi, vòng lặp do ... while (x != 1) không bao giờ quay về trạm $1$ – chương trình chạy mãi (TLE). Ví dụ của đề chính là trường hợp này.

Cách 3Đuôi + vòng: ghi nhớ lần đầu gặp mỗi trạm – O(N) · 100%

Tổng quát, đường đi có dạng chữ $\rho$. Ta vẫn mô phỏng từng chuyến, nhưng ghi lại cho mỗi trạm $v$ lần đầu tiên thầy đứng ở đó:

• firstStep[v] – lúc đó thầy đã đi bao nhiêu chuyến;
• spentAt[v] – lúc đó thầy đã tiêu bao nhiêu tiền.

Trong lúc mô phỏng, nếu hết tiền thì in kết quả luôn (thầy dừng trên đoạn đuôi hoặc ngay vòng đầu tiên). Nếu chưa hết tiền mà thầy bước vào một trạm cur đã có firstStep – đó chính là điểm vào vòng. Khi đó:

• Một vòng có $L$ = step - firstStep[cur] chuyến và tốn $C$ = spent - spentAt[cur] nghìn.
• Thầy đang đứng ở điểm vào vòng, còn m - spent nghìn, nên đi thêm được full = (m - spent) / C vòng trọn vẹn; cộng full * L chuyến và full * C tiền.
• Số tiền còn lại nhỏ hơn $C$, mô phỏng thêm (dưới $L$ chuyến) là xong.

Mỗi trạm được ghi nhớ một lần nên phần mô phỏng trước khi phát hiện vòng có không quá $N$ chuyến, phần lẻ cuối cũng dưới $N$ chuyến: tổng cộng $O(N)$.

Lỗi hay gặp: chia ngay từ trạm 1

Nhiều bạn tìm được vòng rồi viết ans = (M / C) * L; M %= C; và mô phỏng lại từ trạm 1. Cách này coi như thầy "đi vòng" ngay từ đầu, quên mất phải trả tiền đoạn đuôi trước. Ở ví dụ của đề nó vẫn tình cờ ra đúng 11 5, nhưng bộ test có rất nhiều đoạn đuôi dài và "đắt" để bắt lỗi này.

Các bạn tự nhập dữ liệu và bấm "Tiếp" để xem từng bước:

M t_1..N c_1..N

Ví dụ nhanh:

Code hoàn chỉnh:

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    long long m;
    cin >> n >> m;
    vector<int> t(n + 1);
    vector<long long> c(n + 1);
    for (int i = 1; i <= n; i++) cin >> t[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    vector<long long> firstStep(n + 1, -1), spentAt(n + 1, 0);
    long long step = 0, spent = 0;   // so chuyen da di, so tien da tieu
    int cur = 1;
    firstStep[1] = 0; spentAt[1] = 0;
    while (true) {
        if (m - spent < c[cur]) {             // khong du tien di tiep
            cout << step << " " << cur << "\n";
            return 0;
        }
        spent += c[cur]; cur = t[cur]; step++;
        if (firstStep[cur] != -1) break;      // quay lai mot tram da gap: tim thay vong
        firstStep[cur] = step; spentAt[cur] = spent;
    }
    long long L = step - firstStep[cur];      // so chuyen cua mot vong
    long long C = spent - spentAt[cur];       // tien ve cua mot vong
    long long full = (m - spent) / C;         // so vong tron ven con di duoc
    step += full * L;
    spent += full * C;
    while (m - spent >= c[cur]) {             // phan le: duoi L chuyen
        spent += c[cur]; cur = t[cur]; step++;
    }
    cout << step << " " << cur << "\n";
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); m = int(data[1])
    t = [0] * (n + 1)
    c = [0] * (n + 1)
    for i in range(1, n + 1):
        t[i] = int(data[1 + i])
        c[i] = int(data[1 + n + i])
    first = [-1] * (n + 1)
    spent_at = [0] * (n + 1)
    step = 0; spent = 0          # so chuyen da di, so tien da tieu
    cur = 1
    first[1] = 0
    while True:
        if m - spent < c[cur]:   # khong du tien di tiep
            sys.stdout.write("%d %d\n" % (step, cur))
            return
        spent += c[cur]; cur = t[cur]; step += 1
        if first[cur] != -1:     # quay lai mot tram da gap: tim thay vong
            break
        first[cur] = step; spent_at[cur] = spent
    L = step - first[cur]        # so chuyen cua mot vong
    C = spent - spent_at[cur]    # tien ve cua mot vong
    full = (m - spent) // C      # so vong tron ven con di duoc
    step += full * L
    spent += full * C
    while m - spent >= c[cur]:   # phan le: duoi L chuyen
        spent += c[cur]; cur = t[cur]; step += 1
    sys.stdout.write("%d %d\n" % (step, cur))


main()

Không gian$O(N)$

Thời gian$O(N)$

C++▶ Chạy tay từng dòng codeTheo dõi firstStep, spentAt, lúc phát hiện vòng và phép chia lấy số vòng trọn.

Dữ liệu vào (stdin) – sửa thoải mái7 50 7 5 2 7 3 2 5 1 8 4 8 3 9 3

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3int main() {

4 ios::sync_with_stdio(false); cin.tie(nullptr);

5 int n;

6 long long m;

7 cin >> n >> m;

8 vector<int> t(n + 1);

9 vector<long long> c(n + 1);

10 for (int i = 1; i <= n; i++) cin >> t[i];

11 for (int i = 1; i <= n; i++) cin >> c[i];

12 vector<long long> firstStep(n + 1, -1), spentAt(n + 1, 0);

13 long long step = 0, spent = 0; // so chuyen da di, so tien da tieu

14 int cur = 1;

15 firstStep[1] = 0; spentAt[1] = 0;

16 while (true) {

17 if (m - spent < c[cur]) { // khong du tien di tiep

18 cout << step << " " << cur << "\n";

19 return 0;

20 }

21 spent += c[cur]; cur = t[cur]; step++;

22 if (firstStep[cur] != -1) break; // quay lai mot tram da gap: tim thay vong

23 firstStep[cur] = step; spentAt[cur] = spent;

24 }

25 long long L = step - firstStep[cur]; // so chuyen cua mot vong

26 long long C = spent - spentAt[cur]; // tien ve cua mot vong

27 long long full = (m - spent) / C; // so vong tron ven con di duoc

28 step += full * L;

29 spent += full * C;

30 while (m - spent >= c[cur]) { // phan le: duoi L chuyen

31 spent += c[cur]; cur = t[cur]; step++;

32 }

33 cout << step << " " << cur << "\n";

34 return 0;

35}

ChậmVừaNhanhRất nhanh

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 30 test: 10 test subtask 1 ($M \le 10^6$), 9 test subtask 2 ($t$ là hoán vị, $M \approx 10^{18}$), 11 test subtask 3 (trạm 1 luôn nằm trên đoạn đuôi, $M \approx 10^{18}$). Hầu hết test có $N = 2 \cdot 10^5$; đuôi và vòng có đủ kiểu độ dài (đuôi $1$ trạm – vòng $199999$ trạm, đuôi $199998$ trạm – vòng $2$ trạm, ...); nhiều test chỉnh $M$ để lần dừng cuối thầy còn "vừa đủ" đúng giá vé; ở subtask 3, $M$ được chọn để lỗi "chia ngay từ trạm 1" lộ ra.

Cách làm	Sub 1 (30%)	Sub 2 (30%)	Sub 3 (40%)	Điểm
Cách 1 – mô phỏng từng chuyến	Đúng	TLE	TLE	30
Cách 2 – đi một vòng từ trạm 1	Đúng	Đúng	TLE	60
Cách 3 – đuôi + vòng	Đúng	Đúng	Đúng	100
Sai 1 – tiền một vòng kiểu int	Đúng	4/9 test	6/11 test	≈ 65
Sai 2 – chỉ đi khi tiền còn lại > giá vé	5/10 test	3/9 test	5/11 test	≈ 43
Sai 3 – M % C rồi mô phỏng lại từ trạm 1	6/10 test	Đúng	1/11 test	≈ 52

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test subtask 1 và chạy quá 3 giây ở mọi test còn lại (có test cần tới $10^{18}$ chuyến); Cách 2 đúng hết hai subtask đầu và chạy mãi không dừng ở cả 11 test subtask 3 (vì trạm 1 không nằm trên vòng); Cách 3 đúng 30/30 test, test lâu nhất khoảng 0,05 giây. Lỗi "chia ngay từ trạm 1" vẫn ăn trọn subtask 2 (không có đuôi) nhưng gần như mất trắng subtask 3; lỗi dùng int chỉ sai ở những test có tiền một vòng vượt $2^{31}$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇