Next (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng C1, C2)
Đề bài
Với số nguyên dương $x$, gọi $\text{Next}(x)$ là số nguyên dương nhỏ nhất lớn hơn $x$ có cùng số lượng bit 1 với $x$ (khi viết trong hệ nhị phân). Ví dụ $\text{Next}(1) = 2$, $\text{Next}(6) = 9$.
Kí hiệu $\text{Next}^k(x)$ là kết quả khi áp dụng hàm $\text{Next}$ liên tiếp $k$ lần bắt đầu từ $x$: $\text{Next}^k(x)$ $= \text{Next}(\text{Next}(\dots\text{Next}(x)))$.
Yêu cầu: cho số nguyên dương $x \le 10^{15}$ và số nguyên dương $k$, tìm $\text{Next}^k(x)$. Nếu giá trị này vượt quá $10^{15}$ thì in $-1$.
Dữ liệu vào:
- Dòng 1: số nguyên dương $t$ – số truy vấn.
- $t$ dòng tiếp theo, mỗi dòng hai số nguyên dương $x$ và $k$ ($x \le 10^{15}$).
Kết quả: $t$ dòng, mỗi dòng là kết quả của truy vấn tương ứng.
Subtask:
- Subtask 1 (50%): $k \le 10^2$; $t \le 10$;
- Subtask 2 (50%): $k \le 10^{15}$; $t \le 1000$.
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.
2
1 2
6 14
9Giải thích: $1 = 1_2$, $\text{Next}(1) = 2 = 10_2$, $\text{Next}^2(1)$ $= \text{Next}(2)$ $= 4$ $= 100_2$. Còn $6 = 110_2$ có hai bit 1; số nhỏ nhất lớn hơn 6 có hai bit 1 là $9 = 1001_2$ (vì $7 = 111_2$ có ba bit, $8 = 1000_2$ có một bit).
Lời mở đầu
Nếu xếp tất cả các số có đúng $c$ bit 1 theo thứ tự tăng dần thì $\text{Next}$ chỉ là "bước sang số kế tiếp" trong dãy đó, và $\text{Next}^k(x)$ là số đứng sau $x$ đúng $k$ vị trí. Với $k$ nhỏ ta cứ bước từng bước; với $k$ tới $10^{15}$ thì phải "nhảy" thẳng bằng đếm tổ hợp: tính thứ tự của $x$ trong dãy, cộng $k$, rồi dựng lại số có thứ tự đó.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test có gì?
Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ điểm subtask của đề: 20 test (test 1 là ví dụ của đề). Có đủ các kiểu $x$: lũy thừa của 2, toàn bit 1, sát $10^{15}$, $x$ có rất nhiều hoặc rất ít bit 1.
| Nhóm | Test | $t$ lớn nhất | Tổng số truy vấn | $k$ lớn nhất | $x$ lớn nhất | Số truy vấn in $-1$ | Số truy vấn đáp án đúng bằng $10^{15}$ |
|---|---|---|---|---|---|---|---|
| Subtask 1 | 1–10 | 10 | 83 | 100 | $10^{15}$ | 13 | 2 |
| Subtask 2 | 11–20 | 1.000 | 10.000 | $10^{15}$ | $10^{15}$ | 2.714 | 243 |
Kết quả chạy thật các cách bên dưới theo từng subtask:
| Subtask | Điều kiện | Test | Cách 1 tăng dần | Cách 2 mẹo bit | Cách 2 Python | Cách 3 tổ hợp | Cách 3 Python |
|---|---|---|---|---|---|---|---|
| Subtask 1 (50%) | $k \le 10^2$; $t \le 10$ | 1–10 | 3/10 | 10/10 | 10/10 | 10/10 | 10/10 |
| Subtask 2 (50%) | $k \le 10^{15}$; $t \le 1000$ | 11–20 | 0/10 | 0/10 | 0/10 | 10/10 | 10/10 |
Ý tưởngThứ tự trong dãy các số có c bit 1
Gọi $c$ là số bit 1 của $x$. Vì $10^{15} < 2^{50}$, mọi số ta quan tâm đều dưới $2^{50}$, tức viết được bằng 50 bit (bit $49$ tới bit $0$). Hai việc cần làm:
1. Thứ tự của $x$ = số số $y \le x$ có đúng $c$ bit 1. Một số $y < x$ khác $x$ lần đầu tiên (đi từ bit cao xuống) tại một bit $b$ mà $x$ có bit 1 còn $y$ có bit 0. Khi đó các bit cao hơn $b$ giống $x$ (đã dùng $daGap$ bit 1), và $b$ bit thấp chọn tùy ý sao cho đủ $c - daGap$ bit 1: có $\binom{b}{c - daGap}$ cách. Vậy:
$$\text{thứ tự}(x) = 1 + \sum_{\text{bit } b \text{ của } x \text{ bằng } 1} \binom{b}{c - daGap_b}.$$
2. Dựng số thứ $r$ (với $r = \text{thứ tự}(x) + k$): đi từ bit 49 xuống bit 0, đang cần đặt thêm $can$ bit 1. Số các số có bit $b$ bằng 0 (và $can$ bit 1 nằm hết ở $b$ bit thấp) là $\binom{b}{can}$. Nếu $r \le \binom{b}{can}$ thì số cần tìm có bit $b = 0$; ngược lại nó có bit $b = 1$, ta bỏ qua cả nhóm bit 0: $r \mathrel{-}= \binom{b}{can}$, $can \mathrel{-}= 1$.
Nếu $r > \binom{50}{c}$ thì số cần tìm $\ge 2^{50} > 10^{15}$ → in $-1$; dựng xong mà $y > 10^{15}$ cũng in $-1$.
Em nhập $x$, $k$ (bản thu nhỏ: chỉ dùng 12 bit) rồi bấm Tiếp để xem hai bước trên; dòng dưới cùng liệt kê dãy các số có $c$ bit 1 để em đối chiếu:
Cách 1Tăng x từng đơn vị (chưa đủ)
Cách nghĩ ngay theo định nghĩa: lặp $k$ lần, mỗi lần tăng $x$ cho tới khi gặp số có đúng $c$ bit 1 (__builtin_popcountll đếm số bit 1 của số long long).
Vấn đề: khoảng cách giữa hai số liên tiếp có cùng số bit 1 có thể rất xa. Ví dụ $\text{Next}(2^{40}) = 2^{41}$ – phải tăng $2^{40} \approx 10^{12}$ lần! Chỉ cần một truy vấn kiểu này là quá thời gian.
Kết quả chạy thật: Bản C++ đúng 3/20 test, quá thời gian test 2, 4–5, 7–20 (các test đúng chạy lâu nhất 0.027s). Gần như mất hết, kể cả subtask 1 – vì $k$ nhỏ nhưng $x$ lớn tới $10^{15}$.
Cách 2Mẹo bit Gosper – O(k) mỗi truy vấn (Subtask 1)
Có một mẹo bit kinh điển (gọi là Gosper's hack) tính $\text{Next}(x)$ trong $O(1)$. Nhìn $x$ ở dạng nhị phân, xét khối bit 1 thấp nhất, ví dụ $x = 1011\mathbf{1100}_2$:
c = x & -xlấy bit 1 thấp nhất: $c = 100_2$.r = x + c: cộng vào làm khối bit 1 thấp nhất "tràn" lên – bit 0 ngay trên khối thành 1, cả khối thành 0: $r = 1100\,0000_2$.- Ta mất $(\text{độ dài khối}) - 1$ bit 1, phải đặt bù chúng vào cuối số (vị trí thấp nhất để số nhỏ nhất):
r ^ xlà khối đã đổi (dài hơn khối cũ 1 bit), dịch phải 2 rồi chia chocđể đưa về sát bit 0:((r ^ x) >> 2) / c$= 1_2$. - Ghép lại: $\text{Next}(x)$ $= r \,|\,$ $1_2$ $= 1100\,0001_2$.
Vòng lặp dừng sớm khi $x$ đã vượt $10^{15}$ (đi tiếp chỉ càng lớn hơn). Mỗi truy vấn tốn $O(k)$: subtask 1 chỉ $10 \cdot 100$ phép – tức thì; nhưng $k = 10^{15}$ thì không thể.
Kết quả chạy thật: Bản C++ đúng 10/20 test, quá thời gian test 11–20 (các test đúng chạy lâu nhất 0.003s) → 50 điểm. Bản Python đúng 10/20 test, quá thời gian test 11–20 (các test đúng chạy lâu nhất 0.026s).
Cách 3Đếm tổ hợp – O(50) mỗi truy vấn (full)
Làm đúng như phần ý tưởng. Bảng tổ hợp $C[n][r]$ với $n \le 50$ tính bằng tam giác Pascal; $\binom{50}{25} \approx 1{,}26 \cdot 10^{14}$ vừa long long.
thuTubắt đầu bằng 1 (tính cả chính $x$), mỗi bit 1 của $x$ ở vị trí $b$ cộng thêm $\binom{b}{c - daGap}$ – số các số nhỏ hơn $x$ "rẽ nhánh" tại bit $b$. Khican > bthì không có cách nào (tổ hợp bằng 0) – điều kiệnif(can <= b).r = thuTu + ktối đa khoảng $1{,}26 \cdot 10^{14} + 10^{15}$ – vẫn vừalong long.- Nếu $r > \binom{50}{c}$: trong 50 bit không có đủ $r$ số có $c$ bit 1 → in $-1$ ngay.
- Dựng xong $y < 2^{50}$ nhưng vẫn có thể lớn hơn $10^{15}$ (vì $2^{50} \approx 1{,}126 \cdot 10^{15}$) → kiểm tra lần cuối.
Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.005s. Full điểm. Bản Python đúng 20/20 test, chạy lâu nhất 0.042s (Python có sẵn math.comb).
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) | Điểm theo subtask |
|---|---|---|---|---|
| 1. Tăng x từng đơn vị tới khi đủ c bit 1 | C++ | 3/20 | 0.027s | 0% |
| 2. Mẹo bit Gosper, lặp k lần | C++ | 10/20 | 0.003s | 50% |
| Python | 10/20 | 0.026s | 50% | |
| 3. Đếm tổ hợp: tính thứ tự rồi dựng số thứ r | C++ | 20/20 | 0.005s | 100% |
| Python | 20/20 | 0.042s | 100% |
Nhận xét
Đăng nhận xét