owned this note
owned this note
Published
Linked with GitHub
## Bài 1 - Bể nước
Chỉ mở vòi 1, mất $a$ giờ để đầy bể $\Rightarrow$ trong 1 giờ, vòi đồ được $\dfrac{1}{a}$ bể
Chỉ mở vòi 2, mất $b$ giờ để đầy bể $\Rightarrow$ trong 1 giờ, vòi đồ được $\dfrac{1}{b}$ bể
$\Rightarrow$ nếu mở cả hai vòi, trong một giờ đổ được $\dfrac{1}{a} + \dfrac{1}{b}$ bể
$\Rightarrow$ vì đây là mối quan hệ tỉ lệ nghịch, nên bể sẽ được đổ đầy **sau $\dfrac{1}{\dfrac{1}{a} + \dfrac{1}{b}}$ giờ.**
## Bài 2 - Đếm tam giác
Đếm số cặp (a, b) sao cho $a \le b < N$ và $a+b > N$
- $a=1 \Rightarrow$ không có
- $a=2 \Rightarrow b = N-1$
- $a=3 \Rightarrow b = N-1; N-2$
- $a=4 \Rightarrow b = N-1; N-2; N-3$
- $a=5 \Rightarrow b = N-1; N-2; N-3; N-4$
- $\dots$ với điều kiện $b \ge a$
Giả sử $N=7$
- $a=2 \Rightarrow b=6$
- $a=3 \Rightarrow b=6;5$
- $a=4 \Rightarrow b=6;5;4$
- $a=5 \Rightarrow b=6;5$
- $a=6 \Rightarrow b=6$
$\Rightarrow$ mô hình giống kim tự tháp.
### Cách 1 (nộp bằng PyPy):
Với mỗi số $a$, tìm số lượng thỏa mãn
```python=
answer = 0
for a = 2 -> N-1:
bLow = (N+1) - a
bHigh = N-1
answer += bHigh - bLow + 1
```
### Cách 2: tìm công thức
Lấy thêm một ví dụ $a$ chẵn:
$N = 8$:
- $a=2 \Rightarrow b=7$
- $a=3 \Rightarrow b=7;6$
- $a=4 \Rightarrow b=7;6;5$
- $a=5 \Rightarrow b=7;6;5$
- $a=6 \Rightarrow b=7;6$
- $a=7 \Rightarrow b=7$
Suy ra:
- Với $a$ lẻ, ta có $n-2$ trường hợp $a$. Khi tổng các trường hợp $b$ tương ứng với $a$, ta sẽ có công thức:
$1 + 2 + \dots + X-1 + X + X-1 + \dots + 2 + 1 = X^2$
với $X = N - \dfrac{N+1}{2}$.
- Với $a$ chắn, ta cũng có $n-2$ trường hợp $a$. Ta có công thức:
- $1 + 2 + \dots + \dfrac{n-2}{2} + \dfrac{n-2}{2} + \dots + 2 + 1 = 2 \times \dfrac{\dfrac{n-2}{2} \times \left(\dfrac{n-2}{2}+1\right)}{2} = \dfrac{n(n-2)}{4}$
## Bài 3 - Tích các số là bội của $D$
$d=5$
```
1 2 3
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
| | | | | |
a-> a b <- b'
10 * 15 * 20 * 25
5*2 * 5*3 * 5*4 * 5*5
5*5*5*5 * 2*3*4*5
5^4. 2* 2^2 * 5
2^3 * 5^5 =
```
Ta nhận thấy, sẽ tốt hơn nếu đưa $a$ về số gần nhất lớn hơn nó chia hết cho $d$, và $b$ về số gần nhất nhỏ hơn chia hết cho $d$; vì cấc số không chia hết cho $d$ thì không liên quan
Gọi $a' = a \div d; b' = b \div d$, tích của chúng ta sẽ là:
\begin{align*}
ANS = a \times (a+1) \times \dots \times (b-1) \times b &= da' \times d(a'+1) \times \dots \times d(b'-1) \times db' \\
&= d^{b'-a'+1} \times (a'\times (a'+1) \times \dots \times (b'-1) \times b')
\end{align*}
Để biết $ANS$ có bao nhiêu chữ số $0$, ta tìm cách phân tích ANS thành thừa số nguyên tố (đặc biệt là của $2$ và $5$), và xem thử số mũ của $2$ hay của $5$ nhỏ hơn, đó sẽ là đáp án.
- Bước 1: xử lý $d^{b'-a'+1}$
- Phân tích thừa số nguyên tố $2$ và $5$ của $d$
- Sau đó nhân cho $b'-a'+1$.
- Bước 2: xử lý $a'\times (a'+1) \times \dots \times (b'-1) \times b' = \dfrac{b'!}{(a'-1)!}$, vì vậy ta phân tích TSNT 2 và 5 của $b'!$ và $(a'-1)!$ rồi trừ ra.
- https://lqdoj.edu.vn/problem/five
- Phân tích thừa số nguyên tố 2 của $n!$ bất kỳ: $\left\lfloor\dfrac{n!}{2}\right\rfloor+\left\lfloor\dfrac{n!}{2^2}\right\rfloor+\left\lfloor\dfrac{n!}{2^3}\right\rfloor+\dots$ (cho tới khi $\left\lfloor\dfrac{n!}{2^i}\right\rfloor = 0$ thì dừng). với $5$ cũng tương tự.
```python=
def ptso(d: int):
cnt2 = 0;
while d % 2 == 0:
cnt2 += 1; d //= 2
cnt5 = 0;
while d % 5 == 0:
cnt5 += 1; d //= 5
return cnt2, cnt5
def ptgiaithua(n: int):
cnt2 = 0; gt2 = 2
while n >= gt2:
cnt2 += n // gt2
gt2 *= 2
cnt5 = 0; gt5 = 5
while n >= gt5:
cnt5 += n // gt5
gt5 *= 2
return cnt2, cnt5
# biến đổi a thành a', b thành b'
cnt2, cnt5 = ptso(d)
cnt2 *= b - a+1
cnt5 *= b - a +1
cntB2, cntB5 = ptgiaithua(b)
cntA2, cntA5 = ptgiaithua(a-1)
cnt2 += cntB2 - cntA2
cnt5 += cntB5 - cntA5
```
## Bài 4 - Số Even thứ $N$
**Nhận xét đầu tiên**
- Có $f(1) = 5$ số có $l=1$ là số Even: 0, 2, 4, 6, 8
- Có $f(l) = 4 \times 5^{l-1}$ số có $l \ge 2$ chữ số là số Even
Để tìm số Even thứ $N$,
- bước 1: xem thử số đó có bao nhiêu chữ số
- Bắt đầu từ $i=1$, nếu số lượng số Even có $i$ chữ số nhỏ hơn $N$ $\Rightarrow$ Đáp án không thể có $i$ chữ số, khi đó ta lấy $N$ trừ đi cho số lượng đó rồi chuyển sang $i$ tiếp theo
- Ví dụ: $N=35 \Rightarrow$ $i$ không thể có 1, 2 chữ số $\Rightarrow N = 35-5-20=15 < 4 \times f(3)$, vì vậy đáp án phải có 3 chữ số
- bước 2: lần lượt duyệt từ hàng lớn nhất đến nhỏ nhất, để kết luận chữ số đáp án của từng hàng
- Lần lượt cho $i = (0), 2, 4, 6, 8$; cũng tương tự: nếu không đủ, trừ bớt rồi chuyển sang chữ số khác
- Ví dụ, lúc này $n=15$,
- ta sẽ xét các số có dạng $\overline{2**}$ (25 số > $n=15$) $\Rightarrow$ chữ số hàng trăm là 2
- ta sẽ xét các số có dạng $\overline{20*}$ (5 số < $n=15$) $\Rightarrow$ n = 15 - 5 = 10$ và chuyển
- ta sẽ xét các số có dạng $\overline{22*}$ (5 số < $n=10$) $\Rightarrow$ n = 10 - 5 = 5$ và chuyển
- ta sẽ xét các số có dạng $\overline{24*}$ (5 số = $n$) $\Rightarrow$ chữ số hàng chục là $4$
- lần lượt xét các số $240, 242, 244, 246, 248$; rõ ràng mỗi số chỉ có 1 lần, lần lượt trừ cho $n$ như trên, ta sẽ có đáp án là 248.
```python=
def f(l):
if l == 1: return 5
else return 4 * (5 ** (l-1))
length = 1
while f(length) < n:
n -= f(length)
length += 1
answer = 0
# lần lượt đắp chữ số vào phía sau answer
# đắp chữ số x vào answer => answer = answer * 10 + x
for vitri = length -> 1
batdau = 2; if _ > 0: batdau = 0
ketthuc = 8
for chuso = batdau -> ketthuc:
soso = 5 ** (vitri-1)
if soso < n:
n -= soso # chuyen sang chu so khac
answer = answer * 10 + chuso # hết vòng for nhưng biến chuso vẫn còn đó
print(answer)
```