diff options
-rw-r--r-- | THT/B/QG-2016/REMAINDER.TXT | 15 | ||||
-rwxr-xr-x | THT/B/QG-2016/remainder.py | 13 | ||||
-rw-r--r-- | THT/B/QG-2016/remainder.scm | 20 | ||||
-rw-r--r-- | THT/B/QG-2016/trigrid.scm | 6 | ||||
-rw-r--r-- | others/mHoang/decor.scm | 2 | ||||
-rw-r--r-- | others/mHoang/pfactor.scm | 9 | ||||
-rw-r--r-- | others/mHoang/triangle.scm | 5 | ||||
-rw-r--r-- | others/other/README.md | 48 | ||||
-rw-r--r-- | others/other/game.pas | 62 | ||||
-rw-r--r-- | others/volume1/000.scm | 2 | ||||
-rw-r--r-- | others/volume1/001.scm | 2 | ||||
-rw-r--r-- | others/volume1/003.scm | 8 | ||||
-rw-r--r-- | others/volume1/006.scm | 8 |
13 files changed, 78 insertions, 122 deletions
diff --git a/THT/B/QG-2016/REMAINDER.TXT b/THT/B/QG-2016/REMAINDER.TXT index e69de29..f7c3ff9 100644 --- a/THT/B/QG-2016/REMAINDER.TXT +++ b/THT/B/QG-2016/REMAINDER.TXT @@ -0,0 +1,15 @@ +4 +10 +792 +1 +80498 +73871642 +159372937 +484072840 +998 +14 +78632184 +8080810096 +145654824 +853815140748207456 +222510201505884864 diff --git a/THT/B/QG-2016/remainder.py b/THT/B/QG-2016/remainder.py index 2c4de2d..c70faba 100755 --- a/THT/B/QG-2016/remainder.py +++ b/THT/B/QG-2016/remainder.py @@ -18,17 +18,6 @@ TESTS = [ [123456789123456789, 123456789123456789, 987654321123456789] ] - -def powmod(a, n, m): - if n == 1: - return a % m - - if n % 2: - return powmod(a, n // 2, m) ** 2 * a % m - - return powmod(a, n // 2, m) ** 2 % m - - # Gọi l là "chiều dài" của x, l = int(log10(x) + 1) hay l = len(str(x)) # Đặt l ** 10 = a, dễ thấy y = x * (a**(n-1) + a**(n-2) + ... + a + 1) # = x * (a**n - 1) / (a - 1) @@ -40,5 +29,5 @@ with open('REMAINDER.TXT', 'w') as f: for case in TESTS: a = 10 ** len(str(case[0])) case[2] *= a - 1 - p = powmod(a, case[1], case[2]) + p = pow(a, case[1], case[2]) f.write(str(case[0] * (p - 1) % case[2] // (a - 1)) + '\n') diff --git a/THT/B/QG-2016/remainder.scm b/THT/B/QG-2016/remainder.scm new file mode 100644 index 0000000..3df8468 --- /dev/null +++ b/THT/B/QG-2016/remainder.scm @@ -0,0 +1,20 @@ +(define (sqr x) (* x x)) +(define (pow x y z) + (cond ((= y 1) (remainder x z)) + ((= (remainder y 2) 0) (remainder (sqr (pow x (quotient y 2) z)) z)) + (else (remainder (* (sqr (pow x (quotient y 2) z)) x) z)))) +(with-output-to-file "REMAINDER.TXT" (lambda () + (for-each + (lambda (l) + (let* ((a (integer-expt 10 (string-length (number->string (list-ref l 0))))) + (m (* (list-ref l 2) (- a 1))) + (p (pow a (list-ref l 1) m))) + (display (quotient (remainder (* (list-ref l 0) (- p 1)) m) (- a 1))) + (newline))) + '((12 3 8) (2 15 17) (456 6 1296) (1234 100 9) (11223344 1000000 142857) + (55667788 10000000 1000000007) (1357 24682468 999999999) + (24680 1357913579 777777777) (998 1000000000000 999) + (1234 11111111111111 30) (1 222222222222222 123456789) + (2016 666666666666666 8888888888) (11223344 555666777888999 1357924680) + (999999999999999967 999999999999999877 999999999999999989) + (123456789123456789 123456789123456789 987654321123456789))))) diff --git a/THT/B/QG-2016/trigrid.scm b/THT/B/QG-2016/trigrid.scm new file mode 100644 index 0000000..d99a1fd --- /dev/null +++ b/THT/B/QG-2016/trigrid.scm @@ -0,0 +1,6 @@ +(with-output-to-file "TRIGRID.TXT" (lambda () (for-each + (lambda (a) + (display (remainder (quotient (* a (+ a 2) (+ (* a 2) 1)) 8) 2016)) + (newline)) + '(4 3 5 6 111 222 3333 4444 55555 666666 7777777 88888888 999999999 + 123456789123456789 1000000000000000000)))) diff --git a/others/mHoang/decor.scm b/others/mHoang/decor.scm new file mode 100644 index 0000000..1b4cea2 --- /dev/null +++ b/others/mHoang/decor.scm @@ -0,0 +1,2 @@ +(display (exact-integer-sqrt (read))) +(newline) diff --git a/others/mHoang/pfactor.scm b/others/mHoang/pfactor.scm new file mode 100644 index 0000000..4e3bd17 --- /dev/null +++ b/others/mHoang/pfactor.scm @@ -0,0 +1,9 @@ +(define (div dividend divisor) + (if (= (remainder dividend divisor) 0) + (div (/ dividend divisor) divisor) + dividend)) +(display (let* ((n (read)) (s (exact-integer-sqrt n))) + (do ((i 2 (+ i 1))) + ((or (= (div n i) 1) (> i s)) (if (> i s) n i)) + (set! n (div n i))))) +(newline) diff --git a/others/mHoang/triangle.scm b/others/mHoang/triangle.scm new file mode 100644 index 0000000..33a154b --- /dev/null +++ b/others/mHoang/triangle.scm @@ -0,0 +1,5 @@ +(define (angel-90 a b c) + ((lambda (x) (if (= x 0) 0 (/ x (abs x)))) (+ (* a a) (* b b) (- (* c c))))) +(display (let ((a (read)) (b (read)) (c (read))) + (modulo (* (angel-90 a b c) (angel-90 b c a) (angel-90 c a b)) 3))) +(newline) diff --git a/others/other/README.md b/others/other/README.md index 067ea64..a50ae60 100644 --- a/others/other/README.md +++ b/others/other/README.md @@ -82,54 +82,6 @@ liên tiếp chọn được. | 5<br>2 9 3 7 4 | 3 | Chọn dãy 2, 3, 4 | | 7<br>1 2 4 7 6 0 8 | 5 | Thay 0 bởi 5, chọn dãy 4, 5, 6, 7, 8 | -## Trò chơi với dãy số - -Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây: - -* Mỗi bạn chọn trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất - chọn là (b<sub>1</sub>, b<sub>2</sub>, …, b<sub>n</sub>) còn dãy số bạn thứ - hai chọn là (c<sub>1</sub>, c<sub>2</sub>, …, c<sub>n</sub>). -* Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ - nhất đưa ra số hạng b<sub>i</sub>, còn bạn thứ hai đưa ra số hạng - c<sub>j</sub> thì giá của lượt chơi đó sẽ là |b<sub>i</sub> + c<sub>j</sub>|. - -### Yêu cầu - -Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể. - -### Dữ liệu - -Tệp `GAME.INP` gồm ba dòng: - -* Dòng đầu tiên chứa số nguyên dương n. -* Dòng thứ hai chứa dãy số nguyên b<sub>1</sub>, b<sub>2</sub>, …, - b<sub>n</sub>. -* Dòng thứ ba chứa dãy số nguyên c<sub>1</sub>, c<sub>2</sub>, …, - c<sub>n</sub>. - -### Kết quả - -Tệp `GAME.OUT` gồm một dòng ghi giá nhỏ nhất tìm được. - -### Giới hạn - -* n ≤ 10<sup>5</sup>. -* |b<sub>i</sub>|, |c<sub>j</sub>| < 2<sup>63</sup> ∀ 1 ≤ i, j ≤ n. - -### Ví dụ - -| GAME.INP | GAME.OUT | -| ---------------- | :------: | -| 2<br>1 -2<br>2 3 | 0 | - -#### Giải thích - -Dãy số bạn thứ nhất chọn là (1, −2) còn dãy số mà bạn thứ hai chọn là (2,3). - -Khi đó các khả năng có thể của một lượt chơi là (1,2), (1,3), (−2,2), (−2,3). -Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 -tương ứng với giá của lượt chơi (−2,2). - ## Tìm đoạn thẳng v2 Trên 1 đoạn trục số [−c, c], cho N đoạn thẳng, đoạn thứ i là [a<sub>i</sub>, diff --git a/others/other/game.pas b/others/other/game.pas deleted file mode 100644 index 5be1da2..0000000 --- a/others/other/game.pas +++ /dev/null @@ -1,62 +0,0 @@ -uses - sortnfind; - -var - f: text; - n, i, j: smallint; - b: array of int64; - c: int64; - a: qword = 0; - - -function sign(x: int64): shortint; - begin - if x < 0 then - exit(-1); - exit(1) - end; - - -function min( - x: qword; - y, z: int64 -): qword; - - var - tmp: qword; - - begin - if sign(y) = sign(z) then - tmp := abs(y) + abs(z) - else if abs(y) < abs(z) then - tmp := abs(z) - abs(y) - else - tmp := abs(y) - abs(z); - - if tmp < x then - exit(tmp); - exit(x) - end; - - -begin - assign(f, 'GAME.INP'); - reset(f); - readln(f, n); - setlength(b, n); - for i := 0 to n - 1 do - read(f, b[i]); - qsort(b); - for i := 0 to n - 1 do - begin - read(f, c); - for j := 0 to n - 1 do - a := min(a, b[j], c) - end; - close(f); - - assign(f, 'GAME.OUT'); - rewrite(f); - writeln(f, a); - close(f) -end. diff --git a/others/volume1/000.scm b/others/volume1/000.scm new file mode 100644 index 0000000..2757887 --- /dev/null +++ b/others/volume1/000.scm @@ -0,0 +1,2 @@ +(display (let* ((a (read)) (b (read)) (c (read)) (d (read))) + (if (> c b) "NO\n" "YES\n"))) diff --git a/others/volume1/001.scm b/others/volume1/001.scm new file mode 100644 index 0000000..4e6573b --- /dev/null +++ b/others/volume1/001.scm @@ -0,0 +1,2 @@ +(display (let ((a (read)) (b (read))) (exact->inexact (/ (+ a b) 2)))) +(newline) diff --git a/others/volume1/003.scm b/others/volume1/003.scm new file mode 100644 index 0000000..21431e7 --- /dev/null +++ b/others/volume1/003.scm @@ -0,0 +1,8 @@ +(define n (read)) +(display (string-length (number->string n))) +(display " ") +(define (digitsum n) (if (> n 0) + (+ (modulo n 10) (digitsum (quotient n 10))) + 0)) +(display (digitsum n)) +(newline) diff --git a/others/volume1/006.scm b/others/volume1/006.scm new file mode 100644 index 0000000..f791de2 --- /dev/null +++ b/others/volume1/006.scm @@ -0,0 +1,8 @@ +(display ((lambda (str from to) + (let ((i (string-index str (string->char-set from)))) + (string-replace str to i (+ i (string-length from))))) + (number->string (let* ((a (read)) (b (read)) (c (read)) (d (read))) + (+ (/ a b) (/ c d)))) + "/" + " ")) +(newline) |