Đề HSG9 - BRVT - 2016: Editorial

• Đề HSG9 - BRVT - 2016: Editorial
  • Bài 1: Đếm số phong phú (7 điểm)
    • Brute - force:
    • Accepted:
  • Bài 2: Ghép số (7 điểm)
    • Brute - force:
    • Accepted:
  • Bài 3: Nối xích (6 điểm)
    • Brute - force:
    • Accepted:

Bài 1: Đếm số phong phú (7 điểm)

Cho số nguyên dương

$n$

$(n\le {10}^5)$. Đếm số lượng số nguyên dương

$x$

$(x\le n)$ sao cho tổng các ước của

$x$ (trừ

$x$) phải lớn hơn

$x$.

Brute - force:

Ta duyệt qua từng số nguyên từ

$1\to n$ rồi tính tổng các ước của mỗi số.

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

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

Code

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

int main() {
    int n; 
    cin >> n;
    
    int res = 0;
    for (int i = 1; i <= n; i++) {
        long long sum = 1;

        //Duyệt qua các ước của i
        //j <= sqrt(i) <=> j * j <= i
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                if (j * j == i) {
                    sum += j;
                }
                else {
                    //Nếu j là ước của i thì i/j cũng là ước của i
                    sum += j + i/j;
                }
            }
        }

        if (sum > i) res++;
    }

    cout << res;

    return 0;
}

Accepted:

Gọi

$su{m}_i$ là tổng các ước của

$i$ trừ chính nó.

Với mỗi số

$i$ từ

$1$ đến

$n$, ta duyệt qua tất cả các bội của

$i$ (không tính

$i$, tức là từ

$2\ast i$ trở đi), và tăng

$su{m}_i$ lên

$i$ đơn vị.

Đáp án của bài toán là số lượng

$i$ từ

$1\to n$ sao cho

$su{m}_i>i$.

Lưu ý:

Thuật toán trên được gọi là "sàng ước". Nhiều người nhầm tưởng thuật toán này có độ phức tạp thời gian lớn, tuy nhiên, vì số lượng bội số không ngừng giảm khi số tăng lên, nên thực chất thuật toán này chạy rất nhanh.

Nếu coi

$n$ là giới hạn để duyệt

$i$, ta có thể tính được độ phức tạp thời gian của thuật toán này như sau:

$$\sum _{i=1}^n\frac{n}{i}\approx n\log n$$

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

$O(n\log n)$.

Code

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

const int N = 1e5;
int n, res;
int sum[N+5];

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        //Duyệt qua các bội của i
        for (int j = i * 2; j <= n; j += i) {
            sum[j] += i; 
        }
    }

    for (int i = 1; i <= n; i++) {
        if (sum[i] > i) {
            res++;
        }
    }

    cout << res;
    
    return 0;
}

Bài 2: Ghép số (7 điểm)

Cho số nguyên dương

$n$

$(n\le 20)$. Đếm số cách tạo ra số có

$n$ chữ số thỏa mãn các điều kiện sau:

• Các chữ số là
  $0$,
  $1$, hoặc
  $2$.
• Là số chia hết cho
  $5$.
• Không có
  $2$ chữ số liền kề giống nhau.
• Chữ số đầu tiên lớn hơn
  $0$.

Brute - force:

Quay lui đơn thuần, thử tất cả cả trường hợp, sau đó mới kiểm tra có thỏa điều kiện hay không.

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

$O(3^n)$.

Accepted:

Cần đặt thêm nhánh cận vào thuật toán quay lui brute - force (chỉ thử các trường hợp có thể thỏa điều kiện).

Nhánh cận trong thuật toán quay lui được hiểu là những điều kiện để dừng hàm quay lui sớm hơn bình thường hoặc chỉ duyệt qua những trường hợp đúng, nhằm tránh việc duyệt qua những trường hợp thừa (chắc chắn sai). Từ đó giảm thời gian chạy chương trình đáng kể.

$\to$ Nhánh cận được đặt trong bài trên là các điều kiện của đề bài.

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

$O(3\cdot 2^{n-3})$

Giải thích độ phức tạp thuật toán:

Nhận xét:

• Có 2 cách chọn số đầu tiên
  $(1,2)$.
• Có 1 cách chọn số cuối cùng
  $(0)$.
• Số cách chọn
  $n-2$ số còn lại ở giữa là số cách tạo dãy độ dài
  $n-2$ từ các chữ số
  $0,1,2$ sao cho không có 2 số liền kề giống nhau.

Ta có thể tính được số cách chọn

$n-2$ số còn lại bằng quy hoạch động.

Gọi

$d{p}_i$ là số cách tạo dãy độ dài

$i$ từ các chữ số

$0,1,2$ sao cho không có 2 số liền kề giống nhau.

Công thức quy hoạch động:

• $d{p}_1=3$.
• $d{p}_i=2\cdot d{p}_{i-1}$ (Do không được điền số giống số trước đó).

$\Rightarrow d{p}_{n-2}=3\cdot 2^{n-3}$

Tức là có

$3\cdot 2^{n-3}$ trường hợp phải duyệt trong thuật toán quay lui nhánh cận ở trên.

Bài toán này cũng có thể được giải bằng thuật toán quy hoạch động nói trên.

Code

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

const int N = 21;
int n;
int A[N+5];
long long res;

void backTrack(int x) {
    //Quay lui đến n-1 vì số thứ n luôn luôn là số 0
    if (x == n) {
        res++;
        return;
    }

    for (int i = 0; i < 3; i++) {
        //Số đầu tiên phải khác 0
        if (x == 1 && i == 0) {
            continue;
        }
        
        //Hai số liên tiếp phải khác nhau
        if (i == A[x-1]) {
            continue;
        }
        
        //Số kế cuối phải khác 0
        if (i == 0 && x == n-1) {
            continue;
        }
        
        A[x] = i;
        backTrack(x+1);
    }
}

int main() {
    cin >> n;
    
    if (n == 1) {
        cout << 0;
        return 0;
    }

    A[0] = -1;
    backTrack(1);

    cout << res;
    
    return 0;
}

Bài 3: Nối xích (6 điểm)

Cho một dãy

$n$ mắt xích có độ bền

$A_1,A_2,...,A_n$. Nếu nối mắt xích

$i$ và

$i+1$

$(1\le i<n)$ thì độ bền của mối nối là

$d_i$ với:

$$d_i=\{\begin{array}{rcl}0& \text{khi}& a_i>a_{i+1}.\\ a_{i+1}-a_i& \text{khi}& a_i<a_{i+1}\end{array}$$

Tìm cách sắp xếp các mắt xích sao cho tổng độ bền của các mối nối và độ bền của từng mắt xích là lớn nhất.

Brute - force:

Quay lui đơn thuần, thử tất cả cả trường hợp tất cả trường hợp sắp xếp của mảng

$A$ rồi lấy tổng lớn nhất.

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

$O(n!)$.

Accepted:

Nhận xét: Tổng độ bền các mắt xích không đổi, do đó chỉ cần tìm cách sắp xếp các mắt xích sao cho tổng độ bền của các mối nối lớn nhất.

Không mất tính tổng quát, giả sử có bốn mắt xích

$x,y,z,t$ được xếp liền kề nhau thỏa mãn

$x<y<z<t$ thì ta có tổng độ bền của các mối nối là:

$$t-z+z-y+y-x=t-x$$

$\to$ Thay vì thêm mắt xích

$y,z$ vào giữa

$x$ và

$t$, ta nên xếp

$x$ và

$t$ vào cùng một mối nối ngay từ đầu, để có thể dùng

$y$ và

$z$ vào một mối nối khác. Khi đó tổng độ bền ta đạt được là:

$$t-x+z-y>t-x$$

Vậy để đạt độ bền lớn nhất thì ta sẽ lặp đi lặp lại thao tác lấy mối nối nhỏ nhất chưa được nối và nối với mối nối lớn nhất chưa được nối.

Do đó, ta sắp xếp mảng

$A$ tăng dần:

$A_1<A_2...A_{n-1}<A_n$ và thực hiện nối như sau:

• $A_1$ nối với
  $A_n$.
• $A_2$ nối với
  $A_{n-1}$.
• …
• $A_i$ nối với
  $A_{n-i+1}$.

Nếu sắp xếp dựa theo mối nối, ta được mảng:

$B_1<B_2>B_3<B_4...$

$B_1$ nối với

$B_2$,

$B_3$ nối với

$B_4$, …

Đáp án:

$B_2-B_1+B_4-B_3+\cdots =A_n-A_1+A_{n-1}-A_2+\dots$

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

$O(n\log n)$.

Code

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

const int N = 1e6;
int n;
int A[N+5];
long long res;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        res += A[i];
    }

    sort(A+1, A+1+n);

    int i = 1, j = n;
    while (i < j) {
        res += (A[j] - A[i]);
        i++;
        j--;
    }

    cout << res;
    
    return 0;
}