# Bài 1: Bộ ba số:
## Subtask 2:
Ta sẽ thực hiện for $j$, sau đó ta sử dụng một 2 for lồng khác để tìm được $a_i$ lớn nhất và $a_k$ nhỏ nhất.
Như vậy độ phức tạp sẽ là $O(n^2)$

## Subtask 3:
$ma[i]$: số lớn nhất trong đoạn từ 1 đến $i$
$ma[i] = max(ma[i - 1], a[i])$
Tương tự $mi[i]$: số nhỏ nhất trong đoạn từ $i+1$ đến $n$

for $j$ và tính $S$ = $ma[j - 1]$ + $2$ $*$ $a_j$ + $mi[j + 1]$

Độ phức tạp là $O(n)$

# Bài 2: Future number 1:
**Nhận xét: Số tương lai sẽ là tích của chính xác 2 số nguyên tố. Một hợp số luôn có ít nhất một ước nguyên tố không quá căn.**

# Bài 3: Future number 6:
For ngược từ $n$ về và kiểm tra nếu đó là một số tương lai thì trả về đáp án. Nếu không thì là -1.

bool check(int x) { // trả về true nếu x là một số tương lai
    // Một hợp số sẽ có ít nhất 1 ước nguyên tố không quá căn
    // Tìm 1 ước nguyên tố không quá căn của x
    // Nếu p là một ước nguyên tố của x thì x / p hoặc là bằng 1 hoặc là một số nguyên tố khác
    // Nếu x không phải số tương lai thì x sẽ có nhiều hơn 1 ước nguyên tố bé hơn căn
    for (p là số nguyên tố <= căn(x)) {
        nếu p là ước của x:
            tam = x / p
            for (q là số nguyên tố <= căn(x))
                nếu q là ước của tam => x không phải là số tương lai
            Ngược lại nếu không có q là ước của tam thì x là số tương lai
    }
    
    // không có ước nguyên tố nào <= căn nên suy ra x là số nguyên tố
    return false
} // đpt O(sqrt(x))

for (long long i = n; i > 0; --i) {
    if (check(i)) { // i là 1 số tương lai
        cout << i << '\n';
        return;
    }
}

cout << "-1";

# Bài 4:
## Subtask 1: $(n, k \leq 10^6)$
Duyệt từ 1 đến k và tính như đề bảo.

$\lceil \dfrac{n}{i} \rceil$ = $\lfloor \dfrac{n+i-1}{i} \rfloor$

## Subtask 2:
Nhận xét: Sẽ có không quá $2 * \sqrt{n}$ giá trị khác nhau $\lceil \dfrac{n}{i} \rceil$

**Chứng minh:**
Nếu $i \leq \sqrt{n}$ sẽ có không quá $\sqrt{n}$ giá trị của $i$ nên sẽ có không quá $\sqrt{n}$ giá trị của $\lceil \dfrac{n}{i} \rceil$

Nếu $i > \sqrt{n}$ thì $\dfrac{n}{i} < \sqrt{n}$ nên sẽ chỉ có $\sqrt{n}$ giá trị của $\lceil \dfrac{n}{i} \rceil$

Các giá trị $\dfrac{n}{i}$ sẽ giảm dần khi $i$ tăng dần. Nên các giá trị giống nhau sẽ tạo thành các đoạn liên tiếp. Do có không quá $2 * \sqrt{n}$ giá trị khác nhau nên sẽ có không quá $2 * \sqrt{n}$ đoạn khác nhau.

Giả sử có $start$ là bắt đầu của một đoạn, làm sao để ta tìm được kết thúc $last$ của đoạn đó $?$

Nếu $x$ = $\lceil \dfrac{n}{start} \rceil$ thì $x - 1 < \dfrac{n}{start} \leq x$

Ta biết được $\lceil \dfrac{n}{start} \rceil$ = $\lceil \dfrac{n}{last} \rceil$ nên ta có $x - 1 < \dfrac{n}{last} \leq x$
=> $last < \dfrac{n}{x - 1}$
=> $last \leq \dfrac{n}{x - 1} - 1$

Mà ta đang cần $last$ lớn nhất nên $last = \dfrac{n}{x - 1} - 1$

Có $start, last$ thì sẽ biết được độ dài của đoạn có giá trị là $\lceil \dfrac{n}{start} \rceil$ từ đó tính được tổng của đoạn này

Sau đó ta gán $start = last + 1$ và tiếp tục tính như vậy cho đến khi $start > n$.

# Bài 5: Độ vui vẻ
## Subtask 1:
Chơi trò chơi có độ vui vẻ lớn nhất, sau đó giảm độ vui vẻ trò đó đi $1$ và tiếp tục lặp lại như vậy đến hết $k$ lần chơi.

## Subtask 2:
Gọi $cnt[x]:$ số lượng trò chơi có độ vui vẻ là $x$

for x từ max về 0
    nếu số lượt chơi mà ít hơn cnt[x] thì chúng ta sẽ chơi hết lượt chơi và dừng
    còn nếu số lượt chơi còn lại mà nhiều hơn cnt[x] thì chúng ta sẽ chơi hết các trò chơi có độ vui vẻ là x.
    Sau đó các trò chơi này sẽ có độ vui vẻ là x - 1.
    Số lượng trò chơi có độ vui vẻ là x - 1 đã tăng thêm 1 lượng là cnt[x] hay cnt[x - 1] = cnt[x - 1] + cnt[x]

Độ phức tạp là $O(max)$

## Subtask 3:
Sắp xếp lại mảng $a$.

Chơi trò chơi có độ vui vẻ lớn nhất cho đến khi trò chơi này có độ vui vẻ bằng độ vui vẻ của trò chơi lớn thứ hai.

Khi đó ta chơi một lúc 2 trò chơi này cho đến khi 2 trò chơi này có độ vui vẻ bằng trò chơi lớn 3.

Tiếp tục như vậy đến khi hết lượt chơi.

Khi chơi trò chơi lớn nhất đến khi nó có độ vui vẻ bằng trò chơi lớn thứ hai thì chúng ta hoàn toàn tính được số lượt chơi nên có thể tính được tổng độ vui vẻ khi chơi trò thứ nhất.

Sau đó ta tiếp tục làm như vậy khi chơi trò chơi lớn nhất và lớn thứ hai đến khi hết lượt.

Giả sử đang chơi $m$ trò chơi cùng lúc, số lượt còn lại không đủ để chơi $m$ trò chơi thêm $1$ lần nữa mà chỉ đủ để chơi $p < m$ trò chơi. Ta tính được tổng độ vui vẻ khi chơi đầy đủ $m$ trò sau đó tính được tổng độ vui vẻ khi chơi thêm $p$ trò nữa.

Mỗi lần "skip" trò chơi như vậy ta có thể tính được độ vui vẻ trong $O(1)$ mà chúng ta có thể "skip" tối đa $n$ lần vì chỉ có $n$ trò chơi nên là độ phức tạp của thuật toán này là $O(n)$

# Bài 6: DOMINO
## Subtask 1:
Duyệt vét cạn trường hợp
## Subtask 2:
$f(i)$ là số cách để đặt các quân domino lên hình chữ nhất $1 * i$

$f(0) = 0, f(1) = 1$
Để tính $f(i)$, ta có các trường hợp sau:
- Ô thứ $i$ được phủ bởi 1 quân domino phủ 2 ô $i-1$ và $i$ khi đó ta có phần còn lại có độ dài $i-2$ nên số cách đặt của trường hợp này là $f(i-2)$
- Ô thứ $i$ không được phủ bởi quân domino nào khi đó ta coi như ô thứ $i$ này không tồn tại nên phần còn lại có độ dài $i-1$ nên có số cách đặt là $f(i-1)$

Tổng hợp cả 2 trường hợp trên ta có công thức:
- $f(i) = f(i - 2) + f(i - 1)$

## Subtask 3:
Duyệt vét cạn trường hợp

## Subtask 4:
$f(i)$ là số cách để đặt các quân domino lên hình chữ nhật $2 * i$

Ta có các trường hợp:
- Cột $i$ không được phủ bởi bất kì quân domino nào khi đó ta coi như cột $i$ không tồn tại nên sẽ có $f(i-1)$ cách đặt trong trường hợp này
- Đặt 1 quân domino dọc phủ cột $i$ khi đó ta cũng coi như mất cột $i$ nên cũng có $f(i-1)$ cách đặt trường hợp này
- Có 2 quân domino ngang lần lượt phủ các ô $((1, i-1), (1, i))$ và $((2, i - 1), (2, i))$ khi đó ta mất đi cả cột $i$ và cột $i-1$ nên sẽ có $f(i-2)$ cách đặt trường hợp này
- Có 1 quân domino ngang phủ $((1, i-1), (1, i))$. Khi đó ô $(2, i)$ không thể được phủ bởi bất kì quân domino nào nữa(do trường hợp bị phủ bởi $2$ quân domino ngang đã được xét ở trên) nên ta coi như ô $(2, i)$ này không tồn tại. Như vậy ta sẽ còn lại hình $2 * (i-1)$ bị thiếu mất ô $(1, i-1)$ là chưa được đặt quân domino nào. Số cách đặt của trường hợp này là $g(i-1)$.
- Có 1 quân domino ngang phủ $((2, i - 1), (2, i))$ trường hợp này tương tự trường hợp trên nên số cách đặt là $g(i-1)$

Gọi $g(i)$ là số cách để đặt các quân domino lên hình $2 * i$ nhưng bị thiếu mất $1$ ô ở cột cuối cùng

Some image

Ta sẽ có $g(i) = g(i-1) + f(i-1)$

Tính được $g(i)$ ta sẽ tính được $f(i)$ và $f(n)$ chính là đáp án của bài toán.

Như vậy ta sẽ có $f(i) = f(i-1) + f(i-1) + f(i-2) + g(i-1) + g(i-1) = 2f(i-1) + f(i-2) + 2g(i-1)$

=> $f(i) - f(i-2) = 2 * (f(i-1) + g(i-1))$
=> $2 * g(i) = f(i) - f(i-2)$
=> $2 * g(i-1) = f(i-1) - f(i-3)$

Thế ngược vào ta được $f(i) = 2f(i-1) + f(i-2) + f(i-1) - f(i-3) = 3f(i-1) + f(i-2) - f(i-3)$

Độ phức tạp $O(n)$

## Subtask 5:
Ta thấy $f(i), g(i)$ chỉ được tính từ $f(i-1), f(i-2), g(i-1)$ nên chúng ta có thể nhân ma trận được.

Độ phức tạp là $O(27 * log(n))$

Nhân ma trận:
https://vnoi.info/wiki/algo/trick/matrix-multiplication.md
https://www.youtube.com/watch?v=bxcLLcWJwhM

Trick lỏ: oeis.org A030186