Mã đề thi thử (Đề tự luyện HSG Tin 12 – Bài 1) – Đồng dư, đếm số lẻ chia hết cho K và công thức O(1)

Nguồn: Đề tự luyện HSG Tin học 12 – Bài 1 (đề tự soạn)Độ khó: DễĐồng dưSố họcCông thức O(1)long long

Đề bài

Mã đề thi thử. Phòng thi có $N$ dãy bàn (dãy $1$ gần bàn giáo viên nhất), mỗi dãy $M$ chỗ, cột đánh số $1..M$ từ trái sang phải. Thầy Sơn có $K$ mã đề $1..K$ và xếp chỗ theo lối rắn lượn: dãy lẻ đi từ cột $1$ đến cột $M$, dãy chẵn đi ngược từ cột $M$ về cột $1$. Có $P$ thí sinh; thí sinh thứ $p$ ngồi vào chỗ thứ $p$ theo thứ tự đó và nhận mã đề $((p - 1) \bmod K) + 1$ (tức là mã $1, 2, \ldots, K, 1, 2, \ldots$). Hai thí sinh ngồi kề nhau nếu cùng dãy ở hai cột liền nhau, hoặc cùng cột ở hai dãy liền nhau. Một cặp ngồi kề nhau có cùng mã đề gọi là cặp trùng mã. Với mỗi phương án, hãy đếm số cặp trùng mã.

Dữ liệu vào: dòng đầu là $T$ ($1 \le T \le 10^5$); $T$ dòng sau, mỗi dòng bốn số $N, M, K, P$ ($1 \le N, M, K \le 10^9$, $1 \le P \le N \times M$).

Kết quả: $T$ dòng, mỗi dòng là số cặp trùng mã của phương án tương ứng.

• Subtask 1 (30%): $T \le 10$ và $N \times M \le 10^5$.
• Subtask 2 (30%): $T \le 1000$ và $M \le 1000$.
• Subtask 3 (40%): không có ràng buộc gì thêm.

Input

3
4 6 7 16
5 4 5 18
3 5 5 15

Output

2
3
2

Giải thích

Phương án 1, mã đề theo từng dãy (từ cột 1): $1, 2, 3, 4, 5, 6$ / $5, 4, 3, 2, 1, 7$ / $6, 7, 1, 2$, –, – / dãy 4 trống. Hai cặp trùng mã: $(1, 3)$ – $(2, 3)$ cùng mã $3$ và $(2, 4)$ – $(3, 4)$ cùng mã $2$. Phương án 2 có $3$ cặp, phương án 3 có $2$ cặp.

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 Mã đề thi thử

Lời mở đầu

Đây là bài "khởi động" của đề: không cần cấu trúc dữ liệu gì cả, chỉ cần một chút đồng dư và cẩn thận. Phòng thi trong subtask cuối có thể rộng tới $10^9 \times 10^9$ chỗ nên dĩ nhiên ta không thể "điền mã vào từng ghế" được 😅. Ta sẽ đi từ cách ngây thơ nhất tới công thức $O(1)$.

Nhận xét 1 (mấu chốt của cả bài). Thí sinh thứ $p$ nhận mã $((p - 1) \bmod K) + 1$. Vậy thí sinh thứ $p$ và thứ $q$ cùng mã khi và chỉ khi $p \equiv q \pmod K$, tức là $K$ chia hết hiệu $|q - p|$. Bài toán biến thành: với mỗi cặp ghế kề nhau, hiệu thứ tự xếp chỗ của hai ghế là bao nhiêu?

Nhận xét 2. Hai ghế kề nhau trong cùng dãy luôn được xếp liên tiếp (rắn lượn đi qua chúng ngay sau nhau), nên hiệu là $1$. $K \mid 1$ chỉ khi $K = 1$. Còn hai ghế cùng cột ở hai dãy liền nhau thì hiệu phụ thuộc vào cột. Hình dưới là phòng $3 \times 6$ với thứ tự xếp chỗ của từng ghế và hiệu giữa hai ghế trên – dưới:

Giữa dãy 1 và dãy 2, hiệu theo cột là $11, 9, 7, 5, 3, 1$; giữa dãy 2 và dãy 3 là $1, 3, 5, 7, 9, 11$. Hai chiều khác nhau nhưng cùng một tập $\{1, 3, 5, \ldots, 2M - 1\}$!

Từ hai nhận xét đó ta có ba cách làm tăng dần:

Cách 1Điền mã từng ghế · 30%Cách 2Xét từng cột · 60%Cách 3Đếm số lẻ chia hết cho K · 100%

Cách 1Điền mã vào từng ghế – O(N·M) · 30%

Làm đúng như đề kể: tạo mảng $g$ gồm $N \times M$ ô (ô trống là $0$). Với thí sinh thứ $q$ ($q$ đếm từ $0$): dãy của bạn ấy là $i = q / M$, vị trí trong dãy là $s = q \bmod M$; nếu dãy $i$ (đếm từ $0$) là dãy chẵn thì ngồi cột $j = s$, ngược lại ngồi cột $j = M - 1 - s$. Ghi $g[i][j] = (q \bmod K) + 1$.

Sau đó duyệt mọi ghế có người, so với ghế bên phải và ghế phía sau: cùng mã thì tăng đáp án. Mỗi cặp kề nhau chỉ được đếm đúng một lần (ta chỉ nhìn sang phải và xuống dưới).

Vì sao dùng mảng một chiều?

Ô $(i, j)$ được lưu ở vị trí $i \cdot M + j$. Cách này gọn và nhanh hơn vector<vector>; với $N \times M \le 10^5$ thì thoải mái.

#include <bits/stdc++.h>
using namespace std;
// Cach 1: dien ma de cho P cho ngoi dau tien roi dem cap ke cung ma
int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n, m, k, p;
        cin >> n >> m >> k >> p;
        vector<long long> g(n * m, 0);         // g[i*m + j] = ma de, 0 = trong
        for (long long q = 0; q < p; q++) {
            long long i = q / m, s = q % m;
            long long j = (i % 2 == 0) ? s : m - 1 - s;   // day le (dem tu 1) di trai -> phai
            g[i * m + j] = q % k + 1;
        }
        long long ans = 0;
        for (long long i = 0; i < n; i++)
            for (long long j = 0; j < m; j++) {
                long long v = g[i * m + j];
                if (v == 0) continue;
                if (j + 1 < m && g[i * m + j + 1] == v) ans++;      // ben phai
                if (i + 1 < n && g[(i + 1) * m + j] == v) ans++;    // phia sau
            }
        cout << ans << '\n';
    }
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    pos = 1
    for _ in range(t):
        n, m, k, p = (int(x) for x in data[pos:pos + 4])
        pos += 4
        g = [0] * (n * m)  # g[i*m + j] = ma de, 0 = trong
        for q in range(p):
            i, s = divmod(q, m)
            j = s if i % 2 == 0 else m - 1 - s  # day le (dem tu 1) di trai -> phai
            g[i * m + j] = q % k + 1
        ans = 0
        for i in range(n):
            for j in range(m):
                v = g[i * m + j]
                if v == 0:
                    continue
                if j + 1 < m and g[i * m + j + 1] == v:
                    ans += 1  # ben phai
                if i + 1 < n and g[(i + 1) * m + j] == v:
                    ans += 1  # phia sau
        out.append(ans)
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()

Không gian$O(N \cdot M)$

Thời gian$O(N \cdot M)$ mỗi phương án

Với subtask 2, $N$ có thể tới $10^9$ nên mảng $N \times M$ không thể cấp phát được: cách này chỉ được 30%.

Cách 2Xét từng cột – O(M) · 60%

Đánh số dãy và cột từ $1$. Thứ tự xếp chỗ (đếm từ $1$) của ghế $(i, j)$ là:

• dãy $i$ lẻ (đi trái → phải): $p(i, j) = (i - 1)M + j$;
• dãy $i$ chẵn (đi phải → trái): $p(i, j) = (i - 1)M + (M + 1 - j)$.

Lấy hiệu hai ghế cùng cột $j$ ở dãy $i$ và $i + 1$:

• nếu $i$ lẻ: $p(i + 1, j) - p(i, j) = M + (M + 1 - j) - j = 2M + 1 - 2j$;
• nếu $i$ chẵn: $p(i + 1, j) - p(i, j) = M + j - (M + 1 - j) = 2j - 1$.

Hiệu không phụ thuộc $i$, chỉ phụ thuộc $i$ chẵn hay lẻ và cột $j$. Gọi $r = \lfloor P / M \rfloor$ là số dãy đã kín người, $rem = P \bmod M$ là số người ở dãy dở dang $r + 1$. Trong các cặp dãy kín $(i, i + 1)$ với $1 \le i < r$ có $\lfloor r / 2 \rfloor$ cặp với $i$ lẻ và $\lfloor (r - 1) / 2 \rfloor$ cặp với $i$ chẵn. Vậy chỉ cần duyệt $j = 1..M$:

• nếu $K \mid 2M + 1 - 2j$ thì cộng thêm số cặp dãy "$i$ lẻ";
• nếu $K \mid 2j - 1$ thì cộng thêm số cặp dãy "$i$ chẵn".

Dãy dở dang $r + 1$ (nếu $r \ge 1$ và $rem > 0$): nếu $r$ lẻ thì dãy $r + 1$ là dãy chẵn, đi từ phải sang trái nên $rem$ người ngồi ở cột $M - rem + 1..M$, hiệu là $2M + 1 - 2j$; nếu $r$ chẵn thì dãy $r + 1$ đi từ trái sang phải, người ngồi ở cột $1..rem$, hiệu là $2j - 1$. Cuối cùng, nếu $K = 1$ thì mọi cặp trái – phải đều trùng mã: có $r(M - 1)$ cặp ở các dãy kín và $\max(rem - 1, 0)$ cặp ở dãy dở dang.

Cẩn thận khi r = 0

Khi $P < M$ thì $r = 0$: không có cặp dãy nào. Trong Python, (0 - 1) // 2 = -1 chứ không phải $0$ như C++, nên mình viết max(r - 1, 0) // 2 cho chắc ăn.

#include <bits/stdc++.h>
using namespace std;
// Cach 2: xet tung cot j, hieu so thu tu tren - duoi chi phu thuoc j
int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n, m, k, p;
        cin >> n >> m >> k >> p;
        long long r = p / m, rem = p % m;
        long long le = r / 2, chan = max(r - 1, 0LL) / 2;   // so cap day (i, i+1) voi i le / i chan, 1 <= i < r
        long long ans = 0;
        for (long long j = 1; j <= m; j++) {
            if ((2 * m + 1 - 2 * j) % k == 0) ans += le;     // day i le: hieu = 2m + 1 - 2j
            if ((2 * j - 1) % k == 0) ans += chan;          // day i chan: hieu = 2j - 1
        }
        if (r >= 1) {                                       // day r + 1 chua kin
            if (r % 2 == 1) {                               // day r+1 di phai -> trai: cot m-rem+1..m
                for (long long j = m - rem + 1; j <= m; j++)
                    if ((2 * m + 1 - 2 * j) % k == 0) ans++;
            } else {                                        // day r+1 di trai -> phai: cot 1..rem
                for (long long j = 1; j <= rem; j++)
                    if ((2 * j - 1) % k == 0) ans++;
            }
        }
        if (k == 1) ans += r * (m - 1) + max(rem - 1, 0LL);  // cap trai - phai
        cout << ans << '\n';
    }
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    pos = 1
    for _ in range(t):
        n, m, k, p = (int(x) for x in data[pos:pos + 4])
        pos += 4
        r, rem = divmod(p, m)
        le, chan = r // 2, max(r - 1, 0) // 2  # so cap day (i, i+1) voi i le / i chan, 1 <= i < r
        ans = 0
        for j in range(1, m + 1):
            if (2 * m + 1 - 2 * j) % k == 0:
                ans += le  # day i le: hieu = 2m + 1 - 2j
            if (2 * j - 1) % k == 0:
                ans += chan  # day i chan: hieu = 2j - 1
        if r >= 1:  # day r + 1 chua kin
            if r % 2 == 1:  # day r+1 di phai -> trai: cot m-rem+1..m
                for j in range(m - rem + 1, m + 1):
                    if (2 * m + 1 - 2 * j) % k == 0:
                        ans += 1
            else:  # day r+1 di trai -> phai: cot 1..rem
                for j in range(1, rem + 1):
                    if (2 * j - 1) % k == 0:
                        ans += 1
        if k == 1:
            ans += r * (m - 1) + max(rem - 1, 0)  # cap trai - phai
        out.append(ans)
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()

Không gian$O(1)$

Thời gian$O(M)$ mỗi phương án

Subtask 2 có $T \le 1000$, $M \le 1000$ nên tổng chỉ khoảng $10^6$ phép tính. Nhưng ở subtask 3, $M$ tới $10^9$ và có tới $10^5$ phương án: duyệt từng cột là quá chậm.

Mô phỏng: hiệu thứ tự giữa các dãy

Em nhập $N, M, K, P$ nhỏ rồi bấm Tiếp để xem từng cặp dãy: mỗi cột ghi hiệu thứ tự giữa ghế trên và ghế dưới, ô xanh là hiệu chia hết cho $K$ (cặp trùng mã). Để ý tập các hiệu của mỗi cặp dãy luôn là các số lẻ $1, 3, 5, \ldots$

N M K P

Ví dụ nhanh:

Cách 3Đếm số lẻ chia hết cho K – O(1) · 100%

Nhìn lại Cách 2: khi $j$ chạy từ $1$ đến $M$,

• $2M + 1 - 2j$ nhận các giá trị $2M - 1, 2M - 3, \ldots, 3, 1$;
• $2j - 1$ nhận các giá trị $1, 3, \ldots, 2M - 1$.

Cả hai đều là đúng tập các số lẻ từ $1$ đến $2M - 1$, mỗi số một lần! Vậy mỗi cặp dãy kín, dù $i$ chẵn hay lẻ, đều đóng góp đúng $c(M)$ cặp trùng mã, với

$$c(x) = \text{số các số lẻ trong } [1, 2x - 1] \text{ chia hết cho } K.$$

Dãy dở dang cũng thế: nếu $r$ lẻ, các cột $M - rem + 1..M$ cho hiệu $2M + 1 - 2j \in \{2\,rem - 1, \ldots, 3, 1\}$; nếu $r$ chẵn, các cột $1..rem$ cho hiệu $2j - 1 \in \{1, 3, \ldots, 2\,rem - 1\}$. Cả hai trường hợp đều là $c(rem)$. Thế là khỏi phải quan tâm chiều rắn lượn nữa 🎉.

Tính $c(x)$ trong $O(1)$.

• Nếu $K$ chẵn: mọi bội của $K$ đều chẵn, không có số lẻ nào chia hết cho $K$ ⇒ $c(x) = 0$.
• Nếu $K$ lẻ: các bội của $K$ không vượt quá $2x - 1$ là $K, 2K, 3K, \ldots, tK$ với $t = \lfloor (2x - 1) / K \rfloor$. Bội $sK$ lẻ khi và chỉ khi $s$ lẻ, nên số bội lẻ là số số lẻ trong $1..t$, bằng $\lfloor (t + 1) / 2 \rfloor$.

Công thức cuối cùng

Với $r = \lfloor P / M \rfloor$, $rem = P \bmod M$:
đáp án $= (r - 1)\,c(M) + c(rem)$ (khi $r \ge 1$) $+\ [K = 1]\cdot\big(r(M - 1) + \max(rem - 1, 0)\big)$.

Kiểm tra với phương án 1 của ví dụ: $M = 6$, $K = 7$, $P = 16$ ⇒ $r = 2$, $rem = 4$. Các số lẻ $\le 11$ chia hết cho $7$: chỉ có $7$ ⇒ $c(6) = 1$. Các số lẻ $\le 7$ chia hết cho $7$: $7$ ⇒ $c(4) = 1$. Đáp án $= 1 \cdot 1 + 1 = 2$ ✓.

Ba cái bẫy

• Quên điều kiện "lẻ": đếm $\lfloor (2x - 1)/K \rfloor$ là đếm cả bội chẵn (ví dụ $K = 3$, $M = 6$: các bội $3, 6, 9$ nhưng hiệu chỉ có $3$ và $9$).
• Quên $K = 1$: lúc này mọi cặp trái – phải cũng trùng mã.
• Tràn số: với $N = M = 10^9$, $K = 1$, đáp án gần $2 \cdot 10^{18}$, phải dùng long long cho cả $r$ và $c(x)$.

#include <bits/stdc++.h>
using namespace std;
// so cac so le trong [1, 2x - 1] chia het cho k
long long demLe(long long x, long long k) {
    if (x <= 0 || k % 2 == 0) return 0;
    return ((2 * x - 1) / k + 1) / 2;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        long long n, m, k, p;
        cin >> n >> m >> k >> p;
        long long r = p / m, rem = p % m;  // r day kin, day sau co rem nguoi
        long long ans = 0;
        if (r >= 1) ans += (r - 1) * demLe(m, k) + demLe(rem, k);  // cap tren - duoi
        if (k == 1) ans += r * (m - 1) + max(rem - 1, 0LL);       // cap trai - phai
        cout << ans << '\n';
    }
    return 0;
}

import sys


def dem_le(x, k):
    # so cac so le trong [1, 2x - 1] chia het cho k
    if x <= 0 or k % 2 == 0:
        return 0
    return ((2 * x - 1) // k + 1) // 2


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    pos = 1
    for _ in range(t):
        m = int(data[pos + 1]); k = int(data[pos + 2]); p = int(data[pos + 3])
        pos += 4
        r, rem = divmod(p, m)  # r day kin, day sau co rem nguoi
        ans = 0
        if r >= 1:
            ans += (r - 1) * dem_le(m, k) + dem_le(rem, k)  # cap tren - duoi
        if k == 1:
            ans += r * (m - 1) + max(rem - 1, 0)  # cap trai - phai
        out.append(ans)
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()

Không gian$O(1)$

Thời gian$O(1)$ mỗi phương án, tổng $O(T)$

C++▶ Chạy tay từng dòng codeTheo dõi r, rem, các lần gọi demLe và ans của từng phương án.

Dữ liệu vào (stdin) – sửa thoải mái3 4 6 7 16 5 4 5 18 3 5 5 15

Dữ liệu mẫu:

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

2using namespace std;

3// so cac so le trong [1, 2x - 1] chia het cho k

4long long demLe(long long x, long long k) {

5 if (x <= 0 || k % 2 == 0) return 0;

6 return ((2 * x - 1) / k + 1) / 2;

7}

8int main() {

9 ios::sync_with_stdio(false);

10 cin.tie(nullptr);

11 int t;

12 cin >> t;

13 while (t--) {

14 long long n, m, k, p;

15 cin >> n >> m >> k >> p;

16 long long r = p / m, rem = p % m; // r day kin, day sau co rem nguoi

17 long long ans = 0;

18 if (r >= 1) ans += (r - 1) * demLe(m, k) + demLe(rem, k); // cap tren - duoi

19 if (k == 1) ans += r * (m - 1) + max(rem - 1, 0LL); // cap trai - phai

20 cout << ans << '\n';

21 }

22 return 0;

23}

ChậmVừaNhanhRất nhanh

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

Bộ test có 29 test: 9 test subtask 1 (phòng nhỏ, có các trường hợp biên $1 \times 1$, một dãy, một cột), 9 test subtask 2 (mỗi test $1000$ phương án, $N$ tới $10^9$, $M \le 1000$) và 11 test subtask 3 (mỗi test $2 \cdot 10^4$ – $10^5$ phương án, $M > 10^8$, có phòng $10^9 \times 10^9$ kín người với $K = 1$, đáp án gần $2 \cdot 10^{18}$). Các test trộn đủ loại $K$: $K = 1$, $K$ chẵn, $K$ lẻ nhỏ, $K$ gần $2M - 1$, $K > 2M$, và đủ kiểu dãy dở dang (số dãy kín chẵn / lẻ, vừa kín dãy, chưa kín dãy đầu).

Cách làm	Sub 1 (30%)	Sub 2 (30%)	Sub 3 (40%)	Điểm
Cách 1 – điền mã từng ghế	Đúng	RE (không cấp phát nổi)	RE/TLE	30
Cách 2 – xét từng cột	Đúng	Đúng	TLE	60
Cách 3 – đếm số lẻ chia hết cho K	Đúng	Đúng	Đúng	100
Sai 1 – dùng int cho $r$ và $c(x)$	Đúng	2/9 test	4/11 test	≈ 51
Sai 2 – đếm mọi bội của $K$ (quên "lẻ")	3/9 test	0/9 test	3/11 test	≈ 21
Sai 3 – quên cặp trái – phải khi $K = 1$	6/9 test	1/9 test	5/11 test	≈ 41
Sai 4 – dãy dở dang luôn tính từ cột 1	5/9 test	4/9 test	2/11 test	≈ 37

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 9/9 test subtask 1 và trượt mọi test còn lại (mảng $N \times M$ quá lớn); Cách 2 đúng hết hai subtask đầu và chạy quá 3 giây ở cả 11 test subtask 3; Cách 3 đúng 29/29 test, test lâu nhất khoảng 0,03 giây. Ví dụ của đề cố ý chỉ có $K$ lẻ, $K \ne 1$ và $K \ge M$, nên cả bốn lời giải sai ở bảng trên đều vẫn ra đúng ví dụ – các bạn nhớ tự thử thêm $K = 1$, $K$ chẵn, $K = 3$ trước khi nộp 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 😇