---
# System prepended metadata

title: Lời giải thi thử lớp 9 lần 2 - Tân Khoa

---

# Lời giải thi thử lớp 9 lần 2 - TT Tân Khoa 

Lưu ý, các lời giải dưới đây là lời "full" subtask. Có thể đọc lời giải để lấy ý tưởng giải các subtask nhỏ hơn.

# Lần 1
## Gravity

Các viết bi được dồn hết sang phải. Sắp xếp lại độ cao tăng dần của các cột bi, ta sẽ có trạng thái cuối cùng.

::: spoiler C++
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("BAI1.GRAVITY.INP", "r", stdin);
    freopen("BAI1.GRAVITY.OUT", "w", stdout);
    int n; cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    for (auto x : a) cout << x << ' ';
    return 0;
}
```
:::

::: spoiler Python
```python
import sys
sys.stdin = open('BAI1.GRAVITY.INP', 'r')
sys.stdout = open('BAI1.GRAVITY.OUT', 'w')
N = int(input())
A = list(map(int,input().split()))
A.sort()
print(*A)
```
:::

## Stable

Sắp xếp các cặp số theo thứ tự tăng dần theo giá trị `a`. Các cặp số có cùng giá trị `a` giữ nguyên thứ tự (không thay đổi thứ tự theo `b`). 

Hàm `sort` trong C++ không "stable", thay vào đó sử dụng hàm `stable_sort`.
::: spoiler C++
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("BAI2.STABLE.INP", "r", stdin);
    freopen("BAI2.STABLE.OUT", "w", stdout);
    int n; cin >> n;
    vector<pair<long long, long long>> a(n);
    for (int i = 0; i < n; i++) 
        cin >> a[i].first >> a[i].second;
    stable_sort(a.begin(), a.end(), [](const auto& lhs, const auto& rhs) {
        return lhs.first < rhs.first;
    });
    for (int i = 0; i < n; i++)
        cout << a[i].first << ' ' << a[i].second << '\n';
    return 0;
}
```
:::

::: spoiler Python
```python
import sys
sys.stdin = open('BAI2.STABLE.INP', 'r')
sys.stdout = open('BAI2.STABLE.OUT', 'w')
n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda x: x[0])
for x, y in a: print(x, y)
```
:::

## Nth

Với `x` bất kỳ, có thể tìm ra số lượng các số chia hết cho `a` , `b` hoặc `c` không quá `x` trong $O(1)$ (tham khảo sơ đồ Venn phía dưới). Sử dụng thuật toán tìm kiếm nhị phân để tìm ra số thứ `n` thoã mãn điều kiện chia hết.


<img src="https://hackmd.io/_uploads/rJr7tiTta.png" alt="drawing" width="300"/> 

$A$: số lượng chia hết cho `a`. 
$B$: số lượng chia hết cho `b`.
$C$: số lượng chia hết cho `c`. 
$X$: số lượng chia hết cho `a` và `b`. 
$Y$: số lượng chia hết cho `a` và `c`. 
$Z$: số lượng chia hết cho `b` và `c`.
$Q$: số lượng chia hết cho `a`, `b` và `c`.
Số lượng các số chia hết `a`, `b` hoặc `c` là $A+B+C-X-Y-Z+Q$. 


Lưu ý, C++ có trường hợp tràn số (overflow), tham khảo cách xử lý mã nguồn C++ phía dưới. Python không bị tràn, nhưng bị TLE test lớn

::: spoiler C++
```cpp
#include <bits/stdc++.h>
using namespace std;

long long ab, ac, bc, abc, a, b, c;
long long cnt(long long x) {
    long long A = x / a;
    long long B = x / b;
    long long C = x / c;
    long long X = x / ab;
    long long Y = x / ac;
    long long Z = x / bc;
    long long Q = x / abc;
    if (abc % a || abc % b || abc % c) Q = 0; // overflow
    return A + B + C - X - Y - Z + Q;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    freopen("BAI3.NTH.INP", "r", stdin);
    freopen("BAI3.NTH.OUT", "w", stdout);
    int q; cin >> q;
    while (q--) {
        long long n; 
        cin >> a >> b >> c >> n;
        ab = lcm(a, b);
        ac = lcm(a, c);
        bc = lcm(b, c);
        abc = lcm(ab, bc);
        long long l = 1, r = min({a, b, c}) * n;
        while (l < r) {
            long long m = (l + r) / 2;
            if (cnt(m) < n)
                l = m + 1;
            else
                r = m;
        }
        cout << l << '\n';
    }
    return 0;
}
```
:::

::: spoiler Python
```python=
from math import lcm
import sys
sys.stdin = open('BAI3.NTH.INP', 'r')
sys.stdout = open('BAI3.NTH.OUT', 'w')

def cnt(x):
    A = x // a
    B = x // b
    C = x // c
    X = x // ab
    Y = x // ac
    Z = x // bc
    Q = x // abc
    return A + B + C - X - Y - Z + Q

q = int(input())
ans = []
for i in range(q):
    a, b, c, n = map(int, input().split())
    ab = lcm(a, b)
    ac = lcm(a, c)
    bc = lcm(b, c)
    abc = lcm(a, b, c)

    l, r = 1, 10 ** 18
    while l < r:
        m = (l + r) // 2
        if cnt(m) < n:
            l = m + 1
        else:
            r = m
    ans.append(l)
print(*ans)
```
:::

## Fairgame

Các số mà T.Hòa lấy, hai số bất kỳ trong đó luôn chênh lệch nhau hơn $k$ hoặc bằng nhau. Sắp xếp lại dãy $a$, và dùng công thức QHĐ như sau.
`F[i]` là điểm tối ưu của T.Hòa với dãy số $a_0, a_1, ..., a_i$ và T.Hòa luôn lấy $a_i$.

Với $j < i$ thõa mãn $a[j]=a[i]$ hoặc $a[i]-a[j]>k$ 
Công thức QHĐ: $F[i] \xleftarrow{max} F[j] + a[i]$.

Lưu ý, điểm T.Hòa có thể vượt giới hạn bộ nhớ 64-bit (long long), cẩn thận xử lý số nguyên lớn.

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

const int MOD = 998244353;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    freopen("BAI4.FAIRGAME.INP", "r", stdin);
    freopen("BAI4.FAIRGAME.OUT", "w", stdout);
    
    long long n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    vector<__int128_t> f(n);
    f[0] = a[0];
    __int128_t cur = 0;
    for (int i = 1, j = 0; i < n; i++) {
        if (a[i] == a[i - 1]) {
            f[i] = f[i - 1] + a[i];
            continue;
        }
        while (a[j] + k < a[i]) {
            cur = max(cur, f[j]);
            j++;
        }
        f[i] = cur + a[i];
    }
    __int128_t sum = 0, mx = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        mx = max(mx, f[i]);
    }
    long long x = mx % MOD;
    long long y = (sum - mx) % MOD;
    cout << x << ' ' << y << '\n';
    return 0;
}
```

# Lần 2
## Subtract

Chọn $k$ phần tử lớn nhất để giảm đi 1.

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

const int MOD = 1e9 + 7;
int main() {
    freopen("BAI5.SUBTRACT.INP", "r", stdin);
    freopen("BAI5.SUBTRACT.OUT", "w", stdout);
    int n, k; cin >> n >> k;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    for (int i = n - 1; i >= n - k; i--) --a[i];
    long long ans = 1;
    for (auto x : a) ans = x % MOD * ans % MOD;
    cout << ans << '\n';
    return 0;
}
```

## Pairmod
 `a[i] % a[j] < a[j]`, vì thế "cặp mod" lớn nhất luôn nhỏ hơn giá trị lớn nhất của dãy `a`. Kết quả tổi ưu, chọn `a[i]` là giá trị lớn nhì và `a[j]` là giá trị lớn nhất.
 
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("BAI6.PAIRMOD.INP", "r", stdin);
    freopen("BAI6.PAIRMOD.OUT", "w", stdout);
    int q; cin >> q;
    while (q--) {
        int n; cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++)
            cin >> a[i];
        sort(a.begin(), a.end());
        long long ans = 0;
        for (int i = 0; i + 1 < n; i++)
            if (a[i] < a[i + 1])
                ans = a[i];
        cout << ans << '\n';
    }
    return 0;
}
```

## Findmax

Sử dụng QHĐ, gọi `dp[i][j]` là kết quả của bài toán với $a_{1..i}$ và $b_{1..j}$. Công thức truy hồi:
$dp[i][j]\xleftarrow{max}dp[i-1][j]$
$dp[i][j]\xleftarrow{max}dp[i-1][j-1]+a[i]*b[j]$
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("BAI7.FINDMAX.INP", "r", stdin);
    freopen("BAI7.FINDMAX.OUT", "w", stdout);
    int n, k;
    cin >> n >> k;
    vector<long long> a(n + 1), b(k + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= k; i++) cin >> b[i];
    vector dp(n + 1, vector<long long> (k + 1, -1e18));
    for (int i = 0; i <= n; i++) dp[i][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + a[i] * b[j]);
        }
    }
    cout << dp[n][k] << '\n';
    return 0;
}
```

## Splitarray
TBN

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

const int MOD = 998244353;
int fpow(int a, int n) {
    int ans = 1;
    while (n) {
        if (n & 1) ans = 1ll * ans * a % MOD;
        a = 1ll * a * a % MOD;
        n /= 2;
    }
    return ans;
}

int main() {
    freopen("BAI8.SPLITARRAY.INP", "r", stdin);
    freopen("BAI8.SPLITARRAY.OUT", "w", stdout);
    int q; cin >> q;
    while (q--) {
        int n;
        cin >> n;
        vector<int> a(n), f(n);
        int positive = 1;
        for (int i = 0; i < n; i++) {
            cin >> a[i]; f[i] = i + 1;
            if (a[i] < 0)
                positive ^= (i + 1) % 2;
        }
        if (!positive) {
            for (int i = n - 1; i >= 0; i--) {
                f[i]--;
                if (a[i] < 0) break;
            }
        }
        long long ans = 1;
        for (int i = 0; i < n; i++)
            ans = ans * fpow((a[i] % MOD + MOD) % MOD, f[i]) % MOD;
        cout << ans << '\n';
    }
    return 0;
}
```