Thầy Nguyễn Thanh Tùng ôn THT XXIII

7 files changed, 248 insertions, 0 deletions

diff --git a/others/other/README.md b/others/other/README.md
index a50ae60..222391b 100644
--- a/others/other/README.md
+++ b/others/other/README.md
@@ -228,3 +228,150 @@ vấn tương ứng.
 * 2 từ có tiền tố `ban` là: `banana`, `ban`.
 * 3 từ có tiền tố `ba` là: `banana`, `ban`, `baconsoi`.
 * 2 từ có tiền tố `ali` là: `alibaba`.
+
+## Hình chữ nhật
+
+Cho tọa độ 3 điểm trên mặt phẳng, tìm 1 điểm còn lại để 4 điểm tạo thành 1 hình
+chữ nhật.
+
+### Dữ liệu
+
+Gồm 3 dòng, mỗi dòng gồm 2 số nguyên x, y (-100 ≤ x, y ≤ 100) là là toạ độ của
+1 điểm.
+
+### Kết quả
+
+2 số nguyên là toạ độ hai điểm còn lại của hình chữ nhật.
+
+### Ví dụ
+
+|      hcn.inp      | hcn.out |
+| :---------------: | :-----: |
+| 2 1<br>2 4<br>3 1 |   3 4   |
+| 2 5<br>5 1<br>1 3 |   6 3   |
+
+## Lấy bi
+
+Cho 3 lọ đựng bi, mỗi lọ đựng 1 số viên bi. Có quy tắc lấy bi là: lấy ở 2 lọ
+bất kì, mỗi lọ 1 viên bi, và cho vào lọ còn lại. Hỏi cách lấy bi nào sao cho
+tất cả bi đều ở trong 1 lọ, 2 lọ còn lại không có viên bi nào.
+
+### Dữ liệu
+
+1 dòng duy nhất gồm 3 số a, b, c (0 ≤ a, b, c ≤ 10<sup>9</sup>).
+
+### Kết quả
+
+`YES` nếu có cách chuyển bi để tất cả bi đều ở trong 1 lọ, nếu không `NO`.
+
+### Ví dụ
+
+| laybi.inp | laybi.out |
+| :-------: | :-------: |
+|   2 3 3   |    YES    |
+|   2 4 6   |    NO     |
+
+## Biến đổi số
+
+Cho 2 số nguyên x, y và 2 phép biến đổi là phép tăng lên a đơn vị b đơn vị. Hỏi
+có thể biến đổi x thành y được không?
+
+### Dữ liệu
+
+1 dòng duy nhất gồm 4 số x, y, a, b (0 ≤ x < y ≤ 2x10<sup>9</sup>; 0 ≤ a, b ≤
+10<sup>9</sup>).
+
+### Kết quả
+
+1 số duy nhất là số phép biến đổi ít nhất để x thành y. Nếu không biến đổi
+được thì in ra `-1`.
+
+| biendoiso.inp | biendoiso.inp |
+| :-----------: | :-----------: |
+|   3 20 2 3    |       6       |
+|   5 30 6 4    |      -1       |
+
+## Số cách đi của thỏ
+
+Một con thỏ cần băng qua một đoạn đường dài n mét, thỏ có ba cách nhảy với các
+độ dài bước nhảy là 3 mét, 2 mét, 1 mét. Một cách đi đúng của thỏ là dãy các
+bước nhảy của nó có tổng độ dài bằng n và bước nhảy liền sau không dài hơn bước
+nhảy liền trước trong dãy bước nhảy của nó.
+
+### Yêu cầu
+
+Cho biết số nguyên dương n, hãy tính số cách đi đúng khác nhau của thỏ để đi
+hết đoạn đường n mét. Số cách đi có thể rất lớn nên kết quả in ra được viết
+dưới dạng số dư của phép chia kết quả cho 1000000.
+
+### Dữ liệu
+
+Gồm một dòng chứa số nguyên n.
+
+### Kết quả
+
+In ra số nguyên duy nhất là số cách đi đúng của thỏ viết dưới dạng số dư của
+kết quả chia cho 1000000.
+
+### Hạn chế
+
+* 40% test đầu tiên có n ≤ 1000.
+* 30% test tiếp theo có 1000 < n ≤ 10<sup>9</sup>.
+* 30% test cuối cùng có 10<sup>9</sup> < n ≤ 10<sup>15</sup>.
+
+### Ví dụ
+
+| bunny.inp | bunny.out |
+| :-------: | :-------: |
+|     6     |     7     |
+
+#### Giải thích
+
+Với n = 6, thỏ có 7 cách đi như sau: 3+3, 3+2+1, 3+1+1+1, 2+2+2, 2+2+1+1,
+2+1+1+1+1, 1+1+1+1+1+1.
+
+## Biểu thức nhân, cộng
+
+Cho n số nguyên dương a<sub>i</sub>, i=1..n. Bạn phải đặt giữa n số này 2 phép
+nhân và n - 3 phép cộng sao cho kết quả biểu thức là lớn nhất.
+
+Chú ý: Không được thay đổi thứ tự xuất hiện các số nguyên dương của trong biểu
+thức thu được.
+
+### Dữ liệu
+
+* Dòng 1 chứa số nguyên dương n (4 ≤ n ≤ 1000).
+* n dòng tiếp theo, dòng thứ i + 1 chứa số nguyên dương a<sub>i</sub> ≤ 10000.
+
+### Kết quả
+
+Số nguyên dương lớn nhất là giá trị biểu thức thu được.
+
+### Ví dụ
+
+|  express.inp   | express.out |    Giải thích     |
+| -------------- | :---------: | ----------------- |
+| 5<br>4 7 1 5 3 |     44      | 4 * 7 + 1 + 5 * 3 |
+
+## Ước số
+
+Cho đoạn [a; b] \(a, b là số nguyên dương), tính các giá trị:
+
+* min: Số nhỏ nhất và có nhiều ước số nhất trong đoạn này.
+* cmin: Số lượng ước của min.
+* count: Số lượng số trong đoạn có số ước là cmin.
+
+### Dữ liệu
+
+Hai số nguyên dương a và b (a ≤ b ≤ 10<sup>9</sup>; b - a ≤ 10000).
+
+### Kết quả
+
+Ba số nguyên dương theo thứ tự min, cmin, count
+
+### Ví dụ
+
+| uocso.inp | uocso.out |
+| --------- | --------- |
+|  2 10     | 6 4 3     |
+|  200 200  | 200 12 1  |
diff --git a/others/other/biendoiso.py b/others/other/biendoiso.py
new file mode 100755
index 0000000..4b5e09d
--- /dev/null
+++ b/others/other/biendoiso.py
@@ -0,0 +1,33 @@
+#!/usr/bin/env python3
+from math import gcd
+
+
+def xgcd(a, b):
+    """Return a tuple (u, v), such that u*a + v*b == gcd(a, b).
+
+    https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm#Iterative_algorithm
+    """
+    u0, u1, v0, v1 = 1, 0, 0, 1
+    while b:
+        q, a, b = a // b, b, a % b
+        u0, v0, u1, v1 = u1, v1, u0 - q*u1, v0 - q*v1
+    return u0, v0
+
+
+def biendoiso(a, b, c):
+    g = gcd(a, b)
+    if c % g:
+        return -1
+    elif not c % a:
+        return c // a
+    elif not c % b:
+        return c // b
+    if a > b: a, b = b, a
+    u, v = map(lambda n: n * c // g, xgcd(a, b))
+    m = u * g // b
+    return u + v + m*(a-b)
+
+
+with open('biendoiso.inp') as fi, open('biendoiso.out', 'w') as fo:
+    x, y, a, b = map(int, fi.read().split())
+    fo.write('{}\n'.format(biendoiso(a, b, y - x)))
diff --git a/others/other/bunny.py b/others/other/bunny.py
new file mode 100755
index 0000000..befe288
--- /dev/null
+++ b/others/other/bunny.py
@@ -0,0 +1,4 @@
+#!/usr/bin/env python3
+with open('bunny.inp') as fi, open('bunny.out', 'w') as fo:
+    # OEIS A069905 (http://oeis.org/A069905)
+    print(((int(fi.read()) + 3) ** 2 + 6) // 12 % 10 ** 6, file=fo)
diff --git a/others/other/express.py b/others/other/express.py
new file mode 100755
index 0000000..70b8316
--- /dev/null
+++ b/others/other/express.py
@@ -0,0 +1,6 @@
+#!/usr/bin/env python3
+with open('express.inp') as fi, open('express.out', 'w') as fo:
+    a = tuple(map(int, fi.read().split()))[1:]
+    print(max(
+        sum(a[:i]) + a[i]*a[i+1] + sum(a[i+2:j]) + a[j]*a[j+1] + sum(a[j+2:])
+        for i in range(len(a) - 3) for j in range(i + 2, len(a) - 1)), file=fo)
diff --git a/others/other/hcn.py b/others/other/hcn.py
new file mode 100755
index 0000000..6b2fa2b
--- /dev/null
+++ b/others/other/hcn.py
@@ -0,0 +1,20 @@
+#!/usr/bin/env python3
+from collections import deque
+
+
+def not_square(A, B, C):
+    """Return False is ABC is a square angle, True otherwise."""
+    return (B[0]-A[0])*(B[0]-C[0]) + (B[1]-A[1])*(B[1]-C[1])
+
+
+def parallelogram_last_point(A, B, C):
+    """Return the (x, y) coordinates of the point D of the parallelogram
+    ABCD.
+    """
+    return A[0] - B[0] + C[0], A[1] - B[1] + C[1]
+
+
+with open('hcn.inp') as fi, open('hcn.out', 'w') as fo:
+    d = deque(tuple(map(int, line.split())) for line in fi.readlines())
+    while not_square(*d): d.rotate()
+    print(*parallelogram_last_point(*d), file=fo)
diff --git a/others/other/laybi.py b/others/other/laybi.py
new file mode 100755
index 0000000..ce00396
--- /dev/null
+++ b/others/other/laybi.py
@@ -0,0 +1,6 @@
+#!/usr/bin/env python3
+from itertools import combinations as C
+
+with open('laybi.inp') as fi, open('laybi.out', 'w') as fo:
+    m = map(int, fi.read().split())
+    fo.write('NO\n' if all(int.__sub__(*i) % 3 for i in C(m, 2)) else 'YES\n')
diff --git a/others/other/uocso.py b/others/other/uocso.py
new file mode 100755
index 0000000..dec1390
--- /dev/null
+++ b/others/other/uocso.py
@@ -0,0 +1,32 @@
+#!/usr/bin/env python3
+from functools import reduce
+
+primes_dict = dict.fromkeys(range(3, 31608, 2), True)
+primes_dict[2] = True
+for i in range(3, 174, 2):
+    if primes_dict[i]:
+        primes_dict.update(dict.fromkeys(range(i * i, 31608, i * 2), False))
+primes = [key for key, value in primes_dict.items() if value]
+primes.sort()
+
+with open('uocso.inp') as fi, open('uocso.out', 'w') as fo:
+    a, b, counts = *map(int, fi.read().split()), {}
+    for n in range(a, b + 1):
+        l = []
+        for p in primes:
+            if p > n: break
+            m, tmp = 0, n
+            while not tmp % p:
+                tmp //= p
+                m += 1
+            l.append(m)
+        counts[n] = reduce(int.__mul__, (m + 1 for m in l)) if sum(l) else 2
+
+    cmin = max(counts.values())
+    for n in range(a, b + 1):
+        if counts[n] == cmin:
+            nmin, count = n, 1
+            break
+    for n in range(nmin + 1, b + 1):
+        if counts[n] == cmin: count += 1
+    print(nmin, cmin, count, file=fo)