Đường đi (Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Bắc & miền Trung – Bảng C1, C2)

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Bắc & miền Trung – Bảng C1, C2 Độ khó: Trung bình Đồ thị có hướng không chu trình Hệ nhị phân Số lớn

Đề bài

Cho số nguyên dương $k$. Hãy tự xây dựng một đồ thị có hướng gồm không quá $5 \cdot 10^5$ đỉnh và không quá $10^6$ cạnh, thoả mãn đồng thời:

• giữa hai đỉnh bất kỳ có không quá một cạnh;
• đồ thị không có chu trình;
• có đúng $k$ đường đi từ đỉnh $1$ tới đỉnh có chỉ số lớn nhất (đỉnh $N$).

Dữ liệu vào: một dòng chứa số nguyên $k$ ($1 \le k \le 10^{100}$).

Kết quả: dòng đầu là hai số $N, M$ – số đỉnh và số cạnh (đỉnh đánh số $1..N$); $M$ dòng sau, mỗi dòng hai số $u\ v$ mô tả một cạnh có hướng từ $u$ tới $v$. Có nhiều đồ thị thoả mãn thì in đồ thị nào cũng được.

Subtask:

• Subtask 1 (15%): $k \le 100\,000$.
• Subtask 2 (20%): $k \le 10^{18}$.
• Subtask 3 (15%): $k = 2^x$ ($x$ nguyên không âm).
• Subtask 4 (50%): không có ràng buộc gì thêm.

Giới hạn thời gian 1 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.

Ví dụ – input

4

Ví dụ – output

6 8
1 2
1 3
1 4
1 5
2 6
3 6
4 6
5 6

Giải thích: đồ thị của ví dụ (đỉnh 1 nối tới 4 đỉnh giữa, 4 đỉnh giữa cùng nối tới đỉnh 6):

Có 4 đường đi từ đỉnh 1 tới đỉnh 6: $(1, 2, 6)$, $(1, 3, 6)$, $(1, 4, 6)$, $(1, 5, 6)$.

Lời mở đầu

Lại một bài "xây dựng": không có gì để tính, chỉ cần nghĩ ra một đồ thị. Cái khó nằm ở chỗ $k$ có thể lớn tới $10^{100}$, trong khi số đỉnh chỉ được tới $5 \cdot 10^5$ – nên không thể "mỗi đường đi một đỉnh" như ví dụ. Chìa khoá là hệ nhị phân: dựng các đỉnh có $1, 2, 4, 8, \dots$ đường đi rồi "cộng" lại. Phần còn lại là kỹ thuật đổi một số 101 chữ số sang nhị phân.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởnghình thoi ×2Cách 1hình quạtCách 264 bitCách 3số lớn – fullTổng kếtkết quả

Bộ testBộ test có gì?

Bộ test của mình có 20 test (giống bộ trên CLUE). Vì có vô số đồ thị đúng nên bài được chấm bằng trình chấm: kiểm tra $N \le 5 \cdot 10^5$, $M \le 10^6$, không có khuyên, không có hai cạnh nối cùng cặp đỉnh, không có chu trình (sắp xếp tô-pô), rồi đếm số đường đi từ 1 tới $N$ bằng số lớn và so với $k$. Mình chia test theo subtask "nhỏ nhất" mà nó thoả:

Nhóm	Các test	Số chữ số của $k$	Số bit của $k$	Số bit 1	Đồ thị Cách 3 in ra $N$ lớn nhất / $M$ lớn nhất
Subtask 1	1–3	1 – 6	1 – 17	1 – 6	34 / 54
Subtask 2	4–7	18 – 19	58 – 60	24 – 59	120 / 233
Subtask 3	8–10	19 – 100	64 – 333	1 – 1	666 / 997
Subtask 4	11–20	60 – 101	198 – 333	2 – 332	666 / 1325

• Test 2 là $k = 1$: đồ thị chỉ cần 2 đỉnh và cạnh $1 \to 2$.
• Các test $k = 2^x$ (subtask 3) là test 1, 2, 8–10 – trong đó có $k = 2^{63}$ vẫn vừa unsigned long long, còn các test khác thì $k$ lên tới hơn 300 bit.
• Đồ thị của Cách 3 (full) lớn nhất cũng chỉ khoảng 666 đỉnh và 1.200 cạnh – rất xa giới hạn.

Kết quả chạy thật của 3 cách bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 hình quạt	Cách 2 nhị phân 64 bit	Cách 3 nhị phân số lớn
Subtask 1 (15%)	$k \le 100\,000$	1–3	qua	qua	qua
Subtask 2 (20%)	$k \le 10^{18}$	4–7	0/4 test	qua	qua
Subtask 3 (15%)	$k = 2^x$	8–10	0/3 test	1/3 test	qua
Subtask 4 (50%)	không ràng buộc thêm	11–20	0/10 test	0/10 test	qua

Lời giải Cách 3 mình đã nộp thử trên trang chấm chính thức tinhoctre.vn và đạt 100 điểm (AC).

Ý tưởngĐếm đường đi và "nhân đôi" bằng hình thoi

Trong đồ thị không chu trình, gọi $f(v)$ là số đường đi từ đỉnh 1 tới $v$. Ta có $f(1) = 1$ và $$f(v) = \sum_{u \to v} f(u)$$ (mỗi đường tới $v$ phải đi qua đúng một cạnh cuối $u \to v$). Vậy muốn có đỉnh với $f = k$, ta cần các đỉnh có số đường đi "đẹp" rồi cộng chúng lại.

Hình thoi nhân đôi

Từ đỉnh $v$ đi tới đỉnh $w$ bằng 2 lối: cạnh thẳng $v \to w$ và lối vòng $v \to a \to w$ qua một đỉnh phụ $a$. Khi đó $f(w) = f(v) + f(a) = 2 f(v)$. Xâu chuỗi $L$ hình thoi như vậy ta được "xương sống" $v_0 = 1, v_1, \dots, v_L$ với $f(v_i) = 2^i$.

Viết $k$ trong hệ nhị phân: $k = \sum_{i:\ \text{bit } i = 1} 2^i$. Thêm đỉnh cuối $T$ và nối $v_i \to T$ với mọi bit $i$ bằng 1, ta được $f(T) = k$. Đánh số $v_i = 2i + 1$, $a_i = 2i + 2$, còn $T = 2L + 2$ là số lớn nhất (đỉnh $a_L$ không cần nên dùng số đó cho $T$). Đồ thị chỉ có cạnh từ số nhỏ sang số lớn nên chắc chắn không có chu trình.

Với $k \le 10^{100} < 2^{333}$: $L \le 332$, số đỉnh $\le 666$, số cạnh $\le 3 \cdot 332 + 333$. Em nhập $k$ (tới 4095) rồi bấm Tiếp để xem đồ thị được dựng dần, số dưới mỗi đỉnh là số đường đi từ đỉnh 1:

k =

Ví dụ nhanh:

Cách 1Hình quạt như ví dụ (subtask 1)

Làm y như ví dụ: đỉnh 1 nối tới $k$ đỉnh giữa $2, 3, \dots, k+1$, mỗi đỉnh giữa nối tới đỉnh cuối $k + 2$. Mỗi đỉnh giữa cho đúng một đường đi, tổng cộng $k$ đường. Cần $k + 2$ đỉnh và $2k$ cạnh – chỉ dùng được khi $k + 2 \le 5 \cdot 10^5$.

C++▶ Chạy tay từng dòng codeCách 1: hình quạt – đỉnh 1, k đỉnh giữa, đỉnh cuối k + 2.

Dữ liệu vào (stdin) – sửa thoải mái4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(1)$, đồ thị $k + 2$ đỉnh

Thời gian$O(k)$

Kết quả chạy thật: bản C++ đúng 3/20 test, sai test 8–20, quá thời gian test 4–7; các test đúng chạy lâu nhất 0,027 giây. Bản Python đúng 3/20 test, quá thời gian test 4–20; các test đúng chạy lâu nhất 0,075 giây.

Đúng trọn subtask 1. Từ test 4 trở đi $k$ quá lớn: bản C++ đọc $k$ vào long long nên với $k$ 100 chữ số bị tràn (in ra đồ thị sai), còn với $k \approx 10^{18}$ thì in không xuể – quá thời gian.

Cách 2Xương sống nhị phân với unsigned long long (subtask 1, 2)

Cài đặt đúng ý tưởng hình thoi. Bit cao nhất $L$ của $k$ lấy bằng 63 - __builtin_clzll(k) (hàm đếm số bit 0 ở đầu), bit thứ $i$ là k >> i & 1.

C++▶ Chạy tay từng dòng codeCách 2: xương sống hình thoi (f = 1, 2, 4, …) và nối các đỉnh ứng với bit 1 tới T.

Dữ liệu vào (stdin) – sửa thoải mái13

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Với $k = 1$: $L = 0$, không có hình thoi nào, $T = 2$ và chỉ có cạnh $1 \to 2$.
2. Với $k = 2^L$: chỉ bit $L$ bằng 1, nên chỉ có một cạnh $v_L \to T$.
3. Thứ tự cạnh in ra không quan trọng.

Không gian$O(\log k)$

Thời gian$O(\log k)$

Kết quả chạy thật: bản C++ đúng 8/20 test, sai test 8, 9, 11–20; các test đúng chạy lâu nhất 0,004 giây. Bản Python đúng 20/20 test; các test đúng chạy lâu nhất 0,027 giây.

Bản C++ đúng mọi test có $k < 2^{64}$ (subtask 1, 2 và test $k = 2^{63}$); các test $k$ 60–101 chữ số thì cin đọc tràn nên sai. Riêng bản Python đúng hết vì số nguyên Python tự lớn tuỳ ý – với Python, Cách 2 đã là lời giải full!

Cách 3Đổi số lớn sang nhị phân bằng "chia cho 2 trên xâu" (full)

C++ không có kiểu số nguyên 333 bit, nên ta giữ $k$ ở dạng xâu thập phân và đổi sang nhị phân như cách làm tay: chia liên tiếp cho 2, các số dư (từ lần chia đầu) chính là các bit từ thấp tới cao.

Chia một xâu cho 2 cũng như chia dọc ở tiểu học: đi từ chữ số đầu, mang theo số dư $r$; ở mỗi chữ số $c$ tính $cur = 10r + c$, ghi chữ số thương $\lfloor cur / 2 \rfloor$, dư mới $r = cur \bmod 2$. Ví dụ $13 : 2$: chữ số 1 → thương 0 dư 1; chữ số 3 → $cur = 13$, thương 6 dư 1. Thương "06" → bỏ số 0 đầu → "6", dư 1.

Gợi ý của subtask 3 ($k = 2^x$) cũng chính là xương sống không có cạnh phụ nào tới $T$ ngoài $v_x \to T$ – nhưng vẫn phải tìm $x$ từ xâu, nên làm luôn cách tổng quát.

C++▶ Chạy tay từng dòng codeCách 3: đổi xâu thập phân sang nhị phân bằng chia liên tiếp cho 2, rồi dựng đồ thị như Cách 2.

Dữ liệu vào (stdin) – sửa thoải mái13

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Lần gọi divTwo đầu tiên được chạy từng chữ số; các lần sau khung chạy tay tua nhanh (chỉ báo thương và số dư).

1. Mỗi lần gọi divTwo tốn $O(\text{độ dài xâu}) \le 101$, gọi khoảng 333 lần – chưa tới $4 \cdot 10^4$ phép tính.
2. Khi thương bằng 0, find_first_not_of('0') trả về npos nên ta gán "0" để vòng lặp dừng.
3. Phần dựng đồ thị y hệt Cách 2, chỉ thay k >> i & 1 bằng bits[i].

Không gian$O(\log k)$

Thời gian$O(\text{số chữ số} \cdot \log k)$ $\approx 101 \cdot 333$

Kết quả chạy thật: bản C++ đúng 20/20 test; các test đúng chạy lâu nhất 0,004 giây. Full điểm. (Bản Python chính là Cách 2 ở trên.)

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Ghi chú
1. Hình quạt $k$ đỉnh giữa	C++	3/20	0,027s	Sai test 8–20, quá thời gian test 4–7
	Python	3/20	0,075s	quá thời gian test 4–20
2. Nhị phân, unsigned long long	C++	8/20	0,004s	Sai test 8, 9, 11–20
2. Nhị phân (Python: số nguyên tự lớn)	Python	20/20	0,027s	Full điểm
3. Nhị phân, đổi cơ số trên xâu	C++	20/20	0,004s	Full điểm

Ghi chú của mình: thời gian là thời gian CPU trên máy mình (giới hạn 1 giây), mọi đồ thị được trình chấm kiểm tra đầy đủ (không đa cạnh, không chu trình, đếm đúng $k$ đường đi bằng số lớn). Ý tưởng "nhân đôi bằng hình thoi + cộng theo bit" gặp rất nhiều trong các bài xây dựng (dựng đồ thị/lưới có đúng $k$ đường, dựng xâu có đúng $k$ xâu con...) – các bạn nhớ kỹ nhé.

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 😇