Đề THT B - BRVT - 2023: Editorial

Thông tin

Sau đây là lời giải của Kỳ thi Tin học trẻ bảng B tỉnh Bà Rịa - Vũng Tàu năm học 2022 - 2023.

Bạn đọc có thể nộp và chấm bài (test tự sinh) TẠI ĐÂY.

Chuẩn bị bởi team Logica, thuộc khuôn khổ dự án The Algitect (ALGI Project)

• Đề THT B - BRVT - 2023: Editorial
  • Bài 1: Giá trị lớn nhất (40 điểm)
    • Tóm tắt đề bài
    • Subtask 1
    • Subtask 2
  • Bài 2: Cặp số (30 điểm)
    • Tóm tắt đề bài
    • Subtask 1
    • Subtask 2
  • Bài 3: Giá trị lớn nhất (30 điểm)
    • Tóm tắt đề bài
    • Lời giải

Bài 1: Giá trị lớn nhất (40 điểm)

Tóm tắt đề bài

Cho hai số nguyên dương

$n$ và

$m$.

Yêu cầu: Hãy tìm số nguyên dương

$k$ lớn nhất thỏa mãn

$n!$ chia hết cho

$m^k$.

Dữ liệu đảm bảo:

$n\le {10}^{18}$ và

$m\le {10}^6$.

Subtasks:

• $60\mathrm{\%}$ số điểm ứng với
  $n\le {10}^6$.
• $40\mathrm{\%}$ số điểm không có ràng buộc gì thêm.

Subtask 1

Kiến thức toán học cần biết

Giả sử

$a=p_1^{x_1}\cdot p_2^{x_2}\cdot p_3^{x_3}\cdots \cdot p_k^{x_k}$ với

$p_1,p_2,\dots ,p_k$ là các thừa số nguyên tố của

$a$.
Khi đó, một số

$b$ chia hết cho

$a$ khi và chỉ khi với mọi thừa số nguyên tố

$p_i^{x_i}$ của

$a$ thì số

$b$ cũng nhận

$p_j^{x_j}$ làm thừa số nguyên tố trong đó

$p_j=p_i$ và

$x_j\ge x_i$.

Ví dụ:

$a=10=2^1\cdot 5^1$

$b=200=2^3\cdot 5^2$

$b$ chia hết cho

$a$ vì:

• Với thừa số nguyên tố
  $2$, khi phân tích số
  $a$ và
  $b$ ta được số mũ
  $3>2$.
• Với thừa số nguyên tố
  $5$, khi phân tích số
  $a$ và
  $b$ ta được số mũ
  $2>1$

Cách phân tích thừa số nguyên tố của một số

$x$ trong

$\sqrt{x}$

Ta phân tích thừa số nguyên tố của

$k$, được các thừa số

$p$, gọi:

• $x$ là số mũ của
  $p$ trong phân tích thừa số nguyên tố của
  $k$
• $y=cn{t}_p$ là số mũ của
  $p$ trong phân tích thừa số nguyên tố của
  $n!$

Để tính

$cn{t}_p$, ta duyệt từng số từ

$1$ đến

$n$ và chia số đó cho

$p$ đến khi nào không chia được nữa thì dừng.

$cn{t}_p$ bằng tổng số lần chia.

Kết quả: Giá trị nhỏ nhất của

$\lfloor \frac{y}{x}\rfloor$ (

$y$ chia lấy nguyên cho

$x$).

Độ phức tạp thời gian:

$O(\sqrt{1}+\sqrt{2}+\cdots +\sqrt{n})=O\left(\sum _{i=1}^n\sqrt{i}\right)$.

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;
long long n, m, res = 1e18;

long long cnt(long long p) {
    long long ret = 0;
    for (long long i = p; i <= n; i++) {
        long long dup = i;
        while (dup % p == 0) {
            dup /= p;
            ret++;
        }
    }

    return ret;
}

int main() {
    cin >> n >> m;

    long long p = 2;
    while (p*p <= m) {
        if (m % p == 0) {
            long long pw = 0;
            while (m % p == 0) {
                m /= p;
                pw++;
            }

            int x = cnt(p);
            res = min(res, x / pw);
        }

        p++;
    }

    if (m > 1) res = min(res, cnt(m));

    cout << res;

    return 0;
}

Subtask 2

Ý tưởng kế thừa từ subtask trước, tuy nhiên cần cải tiến khâu phân tích thừa số nguyên tố của

$n!$

Quan sát và nhận xét

Xét

$10!=1\cdot 2\cdot 3\dots n$ và số nguyên tố

$p=2$. Từ

$1$ đến

$n$ có:

• $2=2^1$.
• $4=2^2$.
• $6=2\cdot 3$.
• $8=2^3$.
• $10=2\cdot 5$

Khi đó ta nói

$10!$ có:

• $5$ số
  $2$ bậc
  $1$ ở
  $2,4,6,8,10$.
• $2$ số
  $2$ bậc
  $2$ ở
  $4,8$.
• $1$ số
  $2$ bậc
  $3$ ở
  $8$.

Như vậy, có thể tính nhanh số mũ

$x$ của một số nguyên tố

$p$ bất kỳ trong phân tích thừa số nguyên tố của

$n!$ bằng cách:

• Tính số lượng số
  $p$ xuất hiện ở bậc
  $1$.
• Tính số lượng số
  $p$ xuất hiện ở bậc
  $2$.
• $\dots$

Và tính tổng số lượng số

$p$ ở tất cả các bậc.

Công thức

Số lượng thừa số nguyên tố

$p$ bậc

$k$ trong phân tích thừa số nguyên tố của

$n!$ là:

$$\lfloor \frac{n}{p^k}\rfloor$$
Dễ thấy, ta chỉ có thể thực hiện chia cho tối đa

$p^{lo{g}_{p}n}$ trước khi kết quả của phép tính đạt

$0$.

Vậy số lần tối đa ta cần phải chia để đếm số mũ của số nguyên tố

$p$ trong phân tích thừa số nguyên tố của

$n!$ là

$\log n$.

Độ phức tạp thời gian:

$O(\log n\times \sqrt{k})$

Code

#include <bits/stdc++.h>
using namespace std;

long long n, m, res = 1e18;

long long cnt(long long p) {
    long long ret = 0, dup = n;
    while (dup /= p) {
        ret += dup;
    }

    return ret;
}

int main() {
    cin >> n >> m;

    int p = 2;
    while (p*p <= m) {
        if (m % p == 0) {
            int pw = 0;
            while (m % p == 0) {
                m /= p;
                pw++;
            }

            long long x = cnt(p);
            res = min(res, x / pw);
        }

        p++;
    }

    if (m > 1) res = min(res, cnt(m));

    cout << res;

    return 0;
}

Bài 2: Cặp số (30 điểm)

Tóm tắt đề bài

Cho số nguyên dương

$n$. Hai số nguyên dương

$a$,

$b$ được gọi là cặp số may mắn nếu thỏa mãn tất cả các điều kiện sau:

• $0<a\le b$
• $a+b=n$
• Ước số chung lớn nhất của
  $a$ và
  $b$ là lớn nhất.

Yêu cầu: Hãy tìm cặp số

$(a,b)$ thỏa mãn tất cả các điều kiện trên. Nếu có nhiều cặp thì cho biết cặp số có giá trị

$a$ nhỏ nhất.

Dữ liệu đảm bảo:

$2\le n\le {10}^{12}$.

Subtasks:

• $60\mathrm{\%}$ số điểm ứng với
  $n\le {10}^6$.
• $40\mathrm{\%}$ số điểm không có ràng buộc gì thêm.

Subtask 1

Duyệt

$a$ từ

$1$ đến

$\lfloor \frac{n}{2}\rfloor$, ta tính được

$b=n-a$ (nếu

$a>\lfloor \frac{n}{2}\rfloor$ thì

$b<a$).

Sử dụng hàm __gcd() có sẵn trong C++ STL để kiểm tra điều kiện ước số chung lớn nhất của

$a$ và

$b$ là lớn nhất và lấy đáp án.

Độ phức tạp thời gian:

$O(n\log X)$ với

$X=1^2+2^2+\cdots +n^2$.

Để tính UCLN của hai số

$a,b$ mất độ phức tạp

$\log max(a,b)$.
Với mỗi số

$x$, có

$x$ cặp số mà trong đó

$x$ là số lớn hơn.

Code

#include <bits/stdc++.h>
using namespace std;

long long n, res, resA, resB;

int main() {
    cin >> n;
    for (int a = 1; a <= n/2; a++) {
        long long b = n - a, t = __gcd(a, b);
        if (t > res) {
            res = t;
            resA = a;
            resB = b;
        } else if (t == res && resA > a) {
            resA = a;
            resB = b;
        }
    }

    cout << resA << " " << resB;

    return 0;
}

Subtask 2

Giả sử ta có hai số

$a,b$ thỏa mãn

$a+b=n$ và

$d=\mathrm{UCLN}(a,b)$.

Ta có:

• $a=d\times x$ với
  $x\in N^{\ast }$
• $b=d\times y$ với
  $y\in N^{\ast }$
• $a+b=d\times (x+y)$

Lại có:

$a+b=n$

$\iff d\times (x+y)=n$

$\iff x+y=\frac{n}{d}$

Có thể thấy, chỉ tồn tại hai số

$a,b$ nhận ước chung lớn nhất là

$d$ nếu

$d$ là ước của

$n$ và

$\frac{n}{d}\ge 2$.

Khi tìm được

$d$ lớn nhất thỏa mãn, để

$a$ nhỏ nhất, ta xác định:

• $a=d$.
• $b=d\times (\frac{n}{d}-1)$.

Giá trị

$d$ lớn nhất ở đây cũng chính là ước lớn nhất của

$n$ mà bé hơn hoặc bằng

$\frac{n}{2}$. Ta duyệt qua các ước của

$n$ để tìm giá trị này.

Độ phức tạp thời gian:

$O\left(\sqrt{n}\right)$.

Code

#include <bits/stdc++.h>
using namespace std;

long long n, res;

int main() {
    cin >> n;
    for (int i = 1; i*i <= n; i++) {
        if (n % i == 0) {
            if (i <= n/2) res = max(res, i);
            if ((n/i) <= n/2) res = max(res, n/i);
        }
    }

    cout << res << " " << res * (n / res - 1);

    return 0;
}

Bài 3: Giá trị lớn nhất (30 điểm)

Tóm tắt đề bài

Có

$n$ con kiến đi theo một đoàn, con kiến thứ

$i$ có khối lượng

$k_i$ và vận tốc di chuyển

$v_i$. Trên đường đi có một cành cây có độ dài

$l$ chỉ cho phép khối lượng của một nhóm kiến đi qua tối đa là

$m$.

Ở mọi thời điểm, chỉ được có tối đa một nhóm kiến trên cành cây, sau khi nhóm đó đi xong thì nhóm sau mới được đi.

Vận tốc của một nhóm kiến là vật tốc của con kiến chậm nhất.

Yêu cầu: Sắp xếp các nhóm kiến sao cho thời gian qua cành cây là nhỏ nhất.

Lưu ý: Đoàn kiến bắt buộc phải đi tuần từ (không được thay đổi thứ tự của các con kiến).

Dữ liệu đảm bảo:

$n\le {10}^3$,

$1\le m,l,k_i,v_i\le 100$.

Lời giải

Áp dụng quy hoạch động:

• Định nghĩa:
  $d{p}_i$ là thời gian ngắn nhất để
  $i$ con kiến đầu tiên đi qua cành cây.
• Khởi gán:
  $d{p}_0=0$ ban đầu chưa có con kiến nào đi qua.
• Công thức:
  $d{p}_i=min(d{p}_j+\mathrm{cost}(j+1,i))$
  • Giải thích: Tách các con kiến
    $j+1,j+2,\dots ,i$ thành một nhóm.
  • Điều kiện:
    $j<i$ và
    $k_{j+1}+k_{j+2}+\cdots +k_i\le m$.
  • $\mathrm{cost}(j+1,i)=\frac{l}{min(v_{j+1},v_{j+2}\dots ,v_i)}$ là thời gian để nhóm kiến này đi qua cành cây.
• Đáp án:
  $d{p}_n$.

Độ phức tạp thời gian:

$O\left(n^2\right)$.

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;
long long n, m, l, K[N+1], V[N+1];
double F[N+1];

int main() {
    cin >> n >> m >> l;
    for (int i = 1; i <= n; i++)
        cin >> K[i] >> V[i];

    for (int i = 1; i <= n; i++) {
        long long sum = K[i], velo = V[i];
        F[i] = F[i-1] + double(l)/velo;

        for (int j = 1; sum + K[i-j] <= m && j < i; j++) {
            sum += K[i-j];
            velo = min(velo, V[i-j]);
            F[i] = min(F[i], F[i-j-1] + double(l)/velo);
        }
    }

    cout << fixed << setprecision(2) << F[n];

	return 0;
}