# Solution HUE-ICTC 2022 - Junior
## A - Mua gỗ
### Đề bài
Cho 7 số $a, b, c, a+b, b+c, a+c, a+b+c$ nằm trên một mảng. 7 số không nhất thiết đặt theo thứ tự này.
Tìm $a, b, c$.
### Cách giải
$a \le b \le c, a+b \leq a+c \leq b+c \le a+b+c$
$\Rightarrow$ số nhỏ nhất là $a$, số nhỏ nhì là $b$, số lớn nhất là $a+b+c$. Từ đó tính ra $c$.
**Lưu ý, số nhỏ thứ ba chưa chắc là c!**

## B - Chuyển hàng rào gỗ
### Đề bài
Có $n$ thanh loại $A$ và $n$ thanh loại $B$. Mỗi lần bốc một thanh ở $A$ và một thanh ở $B$ sao cho chiều dài thanh $A$ $\le$ thanh $B$.
Có rút được toàn bộ $2n$ hay không?
### Cách giải
Rõ ràng, nếu thanh nhỏ nhất của $B$ không ghép được cho thanh nhỏ nhất của $A$, ta in ra **NO**.
Nếu không, ta ghép hai thanh đó với nhau, và ta lại xét hai thanh tiếp theo.

$\Rightarrow A[i] \le B[i]$ với $i = 1 \rightarrow n$
Vì thế ta chỉ cần dùng một vòng `for` để kiểm tra điều kiện trên.

### Chứng minh
Giả sử tồn tại $i$ sao cho $a_i > b_i$, khi đó gọi $j$ nhỏ nhất sao cho $a_i \leq b_j$ $\Rightarrow$
- $j \geq i+1$
- $a_{\geq j}$ không ghép với $b_i$ được.

với cùng số lượng phần tử $b$ (cụ thể từ $b_j \rightarrow b_n$), bây giờ phải ghép cho $a_i$ và $a_j \rightarrow a_n$, nên $a$ bị dư 1 phần tử, không thể ghép cho $\leq b_i$.
$\Rightarrow$ không ghép được

## C - Số yêu thích
### Đề bài
Cho số $k$. Tìm toàn bộ số $A$ có lẻ ước nguyên dương, sao cho $A+k$ cũng có lẻ ước nguyên dương.
### Cách giải:
Số có lẻ ước nguyên dương là số có trị tuyệt đối là số chính phương.
Đặt $A=a^2, B=b^2$
#### Trường hợp 1
\begin{align*}
&&A+k&=B\\
&\Leftrightarrow &a^2+k &=b^2\\
&\Leftrightarrow &k &=b^2-a^2\\
&\Leftrightarrow &k &=(b-a)(a+b)
\end{align*}

Vì vậy, mình duyệt ước của $k$ để bắt cặp $(x, y)$ có $xy=k$ $(x < y)$.
Khi đó, với mỗi cặp $(x, y)$ ta đặt $b-a = x; a+b=y$ rồi giải tìm $a, b$.
Nếu có nghiệm, đáp án của chúng ta sẽ thêm hai số: $-B, A$ $(-B+k=-A; A+k=B)$
**Lưu ý: không được thêm đáp án có $A=0$ hoặc $B=0$.**

#### Trường hợp 2

\begin{align*}
&&-A+k&=B\\
&\Leftrightarrow &-a^2+k &=b^2\\
&\Leftrightarrow &k &=b^2+a^2\\
\end{align*}

Vì vậy ta có thể thử chạy $a = 1 \rightarrow \sqrt{n}$, nếu $k-a^2$ là một số chính phương thì ta tính $b$, khi đó đáp án sẽ thêm hai số $-A, -B$.

void solve(long long k) {
    vector<long long> allA;

    // a^2+k=b^2 <=> k=(b-a)(a+b)
    for (long long d = 1; d * d <= k; d++) {
        if (k % d != 0) continue;
        // d < k/d => b-a = d, b+a = k/d

        // long long b = (d + k/d) / 2;
        // long long a = (k/d - d) / 2;
        // muốn a và b là số nguyên => d và k/d phải cùng tính chẵn lẻ

        if (d % 2 != (k/d) % 2) continue;
        long long a = (k/d - d) / 2;
        long long b = d + a;
        if (a == 0 or b == 0) continue;
        allA.push_back(-b*b);
        allA.push_back(a*a);
    }
    // -a^2+k=b^2 <=> k = a^2+b^2
    for (long long a = 1; a * a <= k; a++) {
        long long b2 = k - a*a;
        if (b2 == 0) continue;

        long long b = sqrt(b2);
        if (b*b == b2)
            allA.push_back(-a*a),
            allA.push_back(-b*b);
    }

    sort(allA.begin(), allA.end());
    long long n = unique(allA.begin(), allA.end()) - allA.begin();
    allA.resize(n);
    cout << allA.size() << '\n';
    for (long long a: allA) cout << a << ' '; cout << '\n';
}

// iterator unique(iterator begin, iterator end): 
// loại bỏ các phần tử liên tiếp trùng nhau 
// trong đoạn mảng được cho (begin -> end-1), 
// rồi trả về con trỏ sau cuối của đoạn mới
// ví dụ : a = [2, 3, 3, 3, 2, 2] -> a = [2, 3, 2, X, ...],
// trả về iterator trỏ vào a[3] (được đánh dấu bởi chữ X)

k = int(input())
ans = set()   # cấu trúc tập hợp. nếu có trùng, chỉ xuất hiện 1 lần

## trường hợp 1: a^2+k=b^2
for x in range(1, int(k ** 0.5) + 1):   # x=b-a
    if k % x == 0:
        y = k // x                      # y = a + b
        if (x + y) % 2 == 1:
            continue
            
        a = (y-x) // 2; b = y - a
        A = a ** 2; B = b ** 2
        if A != 0 and B != 0:
            ans.add(-B); ans.add(A)

## trường hợp 2: -a^2+k=b^2
for a in range(1, int(k ** 0.5) + 1):
    A = a ** 2
    B = k - A; b = int(B ** 0.5)
    if b ** 2 == B:
        if A != 0 and B != 0:
            ans.add(-B); ans.add(-A)    

ans = list(ans); ans.sort()             # đổi sang mảng mới sort được
print(len(ans))
if len(ans) > 0:
    for num in ans:
        print(num, end = ' ')
    print()

## D - Chơi game
### Đề bài
Cho $n$ thẻ bài, mỗi thẻ gồm hai chữ số $1-9$. Cần tìm hai thẻ bất kỳ, sao cho khi lấy tổng giữa chữ số bên trái của một thẻ, và chữ số bên phải của thẻ còn lại, thì tổng của chúng là lớn nhất.

### Cách giải
Nhận xét: có tối đa $9\times 9=81$ loại thẻ. Vì vậy ta tạo mảng 2 chiều `appear[][]`, với `appear[a][b]` cho biết số lần xuất hiện của thẻ $(a, b)$.

Ta lần lượt duyệt các cặp thẻ bài (có thể trùng nhau nếu xuất hiện từ hai lần trở lên) để xử lý

appear = [[0] * 10 for i in range(10)]
n = int(input())
for i in range(n):
    a, b = map(int, input().split())
    appear[a][b] += 1

ans = 0
for a = 1 -> 9: 
for b = 1 -> 9: 
for c = 1 -> 9: 
for d = 1 -> 9:                # tự indent lại
    if appear[a][b] and appear[c][d]:
        if a == c and b == d and appear[a][b] == 1:
            continue
        ans = max(ans, b+c, a+d)
print(ans)

Cách khác: Chọn ra hai thẻ tốt nhất bên trái và hai thẻ tốt nhất bên phải

struct Card{int l, r;};
bool cmpL(Card a, Card b) {
    return (a.l != b.l)
        ? a.l >= b.l
        : a.r >= b.r;
}
bool cmpR(Card a, Card b) {
    return (a.r != b.r)
        ? a.r >= b.r
        : a.l >= b.l;
}

int n;
Card cards[100005];

vector<int> findBestL() {
    int first = 0, second = 0;
    for (int i = 1; i <= n; i++)
        if (first == 0 or cmpL(cards[i], cards[first])) // >=, vì nếu = thì vẫn đẩy first -> second
            second = first, first = i;
        else if (second == 0 or cmpL(cards[i], cards[second]))
            second = i;
    return {first, second};
}
vector<int> findBestR() {
    int first = 0, second = 0;
    for (int i = 1; i <= n; i++)
        if (first == 0 or cmpR(cards[i], cards[first])) // >=, vì nếu = thì vẫn đẩy first -> second
            second = first, first = i;
        else if (second == 0 or cmpR(cards[i], cards[second]))
            second = i;
    return {first, second};
}

int sumDigits(int number) {
    int sum = 0;
    while (number > 0)
        sum += number % 10,
        number /= 10;
    return sum;
}

main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int l, r; cin >> l >> r;
        cards[i] = {sumDigits(l), sumDigits(r)};
    }

    vector<int> bestL = findBestL();
    vector<int> bestR = findBestR();
    int bestSum = 0;
    for (int r: bestR) for (int l: bestL)
        if (l != r) {
            int sum = cards[r].r + cards[l].l;
            if (sum > bestSum) bestSum = sum;
        }
    cout << bestSum;
}

## E - Đi dạo
Từ $p$ bất kỳ có thể đi tới $p+1, p+2, p+3$.
Có bao nhiêu cách khác nhau đi từ $s$ tới $e$?

### Cách giải
#### Đệ quy quay lui

cnt = 0
def dqql(pos: int, e: int):
    global cnt
    if pos > e: # vượt quá
        return
    if pos == e: # về đích
        cnt += 1
        return

    dqql(pos + 1, e)
    dqql(pos + 2, e)
    dqql(pos + 3, e)


t = int(input())
for _ in range(t):
    s, e = map(int, input().split())
    cnt = 0; dqql(s, e)
    print(cnt)

#### Cách chuẩn:
**Nhận xét:** Vị trí bắt đầu, kết thúc không quan trọng, quan trọng là độ dài quãng đường.

Đặt $l = e - s$. Ta gọi $f(l)$ là số cách đi trên quãng đường độ dài $f(l)$.

Ta mặc định $f(0) = 1$. Công thức sẽ là:
$f(l) = f(l-1) + f(l-2) + f(l-3)$.

Tức là, đáp án bằng
- số cách có bước đầu là 1 bước, $l-1$ bước còn lại tùy ý
- số cách có bước đầu là 2 bước, $l-2$ bước còn lại tùy ý (nếu $l \ge 2$)
- số cách có bước đầu là 3 bước, $l-3$ bước còn lại tùy ý (nếu $l \ge 3$)

*vì vậy theo công thức này, $f(0) = 1$, vì cách đi trên cung đường độ dài 0 là... không làm gì cả. nếu đặt $f(0)=0$ thì tất cả bằng 0 tất.

f = [0] * 61

f[0] = 1
for i = 1 -> 60:
    f[i] = f[i - 1]
    if i >= 2: f[i] += f[i - 2]
    if i >= 3: f[i] += f[i - 3]

t = int(input())
for _ in range(t):
    s, e = map(int, input().split())
    print(f[e-s])