diff options
| -rwxr-xr-x | THT/B/QG-2014/dic.pp | 2 | ||||
| -rw-r--r-- | others/other/README.md | 147 | ||||
| -rwxr-xr-x | others/other/biendoiso.py | 33 | ||||
| -rwxr-xr-x | others/other/bunny.py | 4 | ||||
| -rwxr-xr-x | others/other/express.py | 6 | ||||
| -rwxr-xr-x | others/other/hcn.py | 20 | ||||
| -rwxr-xr-x | others/other/laybi.py | 6 | ||||
| -rwxr-xr-x | others/other/uocso.py | 32 |
8 files changed, 249 insertions, 1 deletions
diff --git a/THT/B/QG-2014/dic.pp b/THT/B/QG-2014/dic.pp index 76f2323..716249d 100755 --- a/THT/B/QG-2014/dic.pp +++ b/THT/B/QG-2014/dic.pp @@ -61,7 +61,7 @@ var i: longint; ok: boolean; begin - assign(f, 'dic.dat'); + assign(f, 'DIC.DAT'); reset(f); while not seekeof(f) do begin 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) |