# Thi thử Tin học trẻ Khu vực bảng A - ngày 01

## Bài 1: Đấu súng

Xét trường hợp người $u$ đấu với người $v$:
- Xét $a_u = a_v$, ta thấy vì người $v$ phải đi trước nên chắc chắn người $v$ thua. Sau đó $a_u = a_v = 0$
- Xét $a_u > a_v$, giống như trường hợp trước, người $v$ sẽ thua, người $u$ và $v$ sẽ đưa ra $a_v$ lá, hay $a_u = a_u - a_v$ và $a_v = 0$
- Xét $a_u < a_v$, trường hợp này người $v$ sẽ thắng, với người $v$ đưa ra $a_u + 1$ lá, và người $a_u$ sẽ không còn lá nào, hay $a_u = 0$ và $a_v = a_v - a_u - 1$

n = int(input())
a = list(map(int, input().split()))
t = int(input())
for _ in range(t):
    u, v = map(int, input().split())
    u -= 1; v -= 1
    if a[u] == a[v]: a[u] = a[v] = 0
    elif a[u] > a[v]:
        a[u] -= a[v]
        a[v] = 0
    else:
        a[v] -= a[u] + 1
        a[u] = 0
print(*a)

## Bài 2: Hối lộ

Nhận xét: Thao tác trong đề không khác gì việc có thể đổi chỗ các số trong bảng. Ta sẽ tập trung vô cột Tin, vì cột này giúp số tăng lên cao. Ta sẽ bỏ các số lớn nhất vào cột Tin, còn số nhỏ thì bỏ vô các cột khác. Ở cột tin có $n$ ô, nói cách khác ta sẽ chọn $n$ số lớn nhất và bỏ vào cột Tin.

n = int(input())
a = []
for _ in range(n):
    x, y, z, t = map(int, input().split())
    a.append(x)
    a.append(y)
    a.append(z)
    a.append(t)
a.sort(reverse = True)
tong = 0
for i in range(len(a)):
    if i < n: tong += a[i] * 3
    else: tong += a[i]
print(tong)

## Bài 3: Thêm một chữ k

Nhận xét: Nếu ta thực hiện $2$ lần thao tác trên cùng đoạn, thì toàn bộ sẽ về $0$.

Nhận xét $2$: Nếu ta áp dụng thao tác trên đoạn có dạng $0, 0, 0, 0, 0, 0, 1000$, thì ta có thể biến cả dãy thành toàn bộ $1000$, vậy nếu ta biến cả dãy $A$ thành $0$, chừa lại mỗi số lớn nhất, thì ta có thể biến cả dãy $A$ thành số lớn nhất.

5 3 6 19 6 5
1 1 1 19 6 5
0 0 0 19 6 5
0 0 0 19 1 1
0 0 0 19 0 0
19 19 19 19 0 0
19 19 19 19 19 19

Nhận xét $3$: Nếu dãy mình cần biến thành $0$ có độ dài là $1$ thì không thể biến thành $0$

Ý tưởng: Biến dãy đã cho thành $0$ ngoại trừ phần tử lớn nhất, xong nhờ nhận xét $2$ để biến cả dãy thành phần tử lớn nhất. Xét các trường hợp $n = 2$ và $n = 3$ mà có phần tử lớn nhất nằm ở giữa

n = int(input())
a = list(map(int, input().split()))
if n == 2: print(max(a[0] + a[1], 2 * abs(a[0] - a[1])))
elif n == 3: print(max(sum(a), a[0] * 3, a[2] * 3, abs(a[0] - a[1]) * 3, abs(a[1] - a[2]) * 3))
else: print(max(a)*n)

## Số X

Ta gọi làm $\text{goi}(r)$ là số lượng số $X$ trong đoạn từ $1$ đến $r$. Đáp án là $\text{goi}(r) - \text{goi}(l - 1)$.

Để tính hàm $\text{goi}(r)$, ta giả sử $r$ có $2$ chữ số trở lên để thuận tiện tính toán. Gọi $n$ là số lượng chữ số của $r$.

Một số $x$ thỏa nằm trong đoạn từ $1$ đến $r$ sẽ nằm trong $1$ trong các trường hợp sau:
- **TH1:** $x = r$
- **TH2:** $x$ có $n$ chữ số và $x_1 < r_1$
- **TH3:** $x$ có $n$ chữ số và $k$ chữ số đầu của $x$ bằng của $r$ và $x_{k + 1} < r_{k + 1}$ $(1 \leq k \leq n - 2)$
- **TH4:** $x$ có $n$ chữ số và $n - 1$ chữ số đầu của $x$ bằng của $r$ và $x_n < r_n$
- **TH5:** $x$ có ít hơn $n$ chữ số.

Đặt ```tong = 0```, đoạn code xét từng trường hợp là:
- **TH1:** Ta kiểm tra xem $r$ có phải là số thỏa

check = True
for i in range(1, n):
    if r[i] >= r[-1]: check = False; break
tong += check

- **TH2:** Ta for chữ số $x_1$ và $x_n$, mỗi chữ số trong đoạn $[2 : n - 1]$ có số cách đặt là từ $[0 : x_n - 1]$, nhân hết lại ta có số cách đặt là $x_n^{n - 2}$

for x1 in range(1, int(r[1])):   #Chữ số đầu
    for xn in range(x1 + 1, 10): #Chữ số cuối
        tong += pow(xn, n - 2)   #Số cách đặt

- **TH3:** Ta for $k$, $x_{k + 1}$ và $x_n$, mỗi chữ số trong đoạn $[k + 2 : n - 1]$ có số cách đặt từ $[0 : x_n - 1]$, nhân hết lại ta có số cách đặt là $x_n^{n - k - 2}$

mx = int(r[1])
for k in range(1, n - 1):
    for xk1 in range(0, int(r[k + 1])):
        for xn in range(max(mx, xk1) + 1, 10):
            tong += pow(xn, n - k - 2)
    mx = max(mx, int(r[k + 1]))

- **TH4:** Ta for $x_n$, với mỗi $x_n$ thỏa thì là $1$ cách đặt

for xn in range(mx + 1, int(r[-1])): tong += 1

- **TH5:** Ta mặc định $x_1 = 0$, for $x_n$, mỗi chữ số trong đoạn $[2 : n - 1]$ có số cách đặt từ $[0 : x_n - 1]$, nhân hết lại ta có số cách đặt là $x_n^{n - 2}$

tong += 1
for xn in range(1, 10): tong += pow(xn, n - 2)