THT/B/QG-2016: Add remainder.py

7 files changed, 285 insertions, 26 deletions

diff --git a/THT/B/QG-2016/QG-2016.pdf b/THT/B/QG-2016/QG-2016.pdf
deleted file mode 100644
index e98feac..0000000
--- a/THT/B/QG-2016/QG-2016.pdf
+++ /dev/null
Binary files differdiff --git a/THT/B/QG-2016/README.md b/THT/B/QG-2016/README.md
new file mode 100644
index 0000000..8406fd7
--- /dev/null
+++ b/THT/B/QG-2016/README.md
@@ -0,0 +1,233 @@
+# ĐỀ THI BẢNG B – TRUNG HỌC CƠ SỞ
+
+HỘI THI TIN HỌC TRẺ TOÀN QUỐC LẦN THỨ XXII – 2016
+
+Thời gian làm bài 180 phút, không kể thời gian phát đề
+
+## Bài 1: LƯỚI TAM GIÁC (30 điểm)
+
+Đề thi năng lực của trường mầm non SuperKids có một bài toán rất đơn giản: Trên
+mặt phẳng cho một tam giác đều độ dài cạnh là `a` (`a` là một số nguyên), người
+ta đặt `a` − 1 điểm trên mỗi cạnh để chia đều các cạnh ra thành các đoạn thẳng
+dài 1 đơn vị. Với mỗi cặp hai điểm trên hai cạnh khác nhau, người ta vẽ một
+đoạn thẳng nối chúng nếu đoạn thẳng này song song với cạnh thứ ba. Sau khi vẽ
+hết các đoạn thẳng như vậy, ta thu được một lưới các tam giác đều cạnh 1 đơn vị
+mà những điểm trên mặt phẳng ở vị trí đỉnh của các tam giác đều đó được gọi là
+**nút lưới**.
+
+Hình vẽ dưới đây thể hiện lưới tam giác đều được xây dựng với `a` = 4
+
+![](http://i.stack.imgur.com/c8X1c.jpg)
+
+Nhiệm vụ của các bé thí sinh là đếm số tam giác đều có trong hình vẽ. Nói một
+cách chính xác, các bé cần đưa ra **số bộ ba nút lưới** là ba đỉnh của một tam
+giác đều có ba cạnh song song với ba cạnh của tam giác ban đầu. Như ví dụ trên,
+có thể đếm được có 27 tam giác đều bao gồm: 16 tam giác đều cạnh 1 đơn vị, 7
+tam giác đều cạnh 2 đơn vị, 3 tam giác đều cạnh 3 đơn vị và 1 tam giác đều cạnh
+4 đơn vị.
+
+Tuy bài toán không khó với các bé thí sinh trường SuperKids nhưng lại là thách
+thức lớn cho ban giám khảo trong việc làm đáp án chấm điểm. Hãy giúp ban giảm
+khảo đưa ra đáp số. Chú ý là vì đáp số rất lớn nên chỉ cần đưa ra số dư của đáp
+số khi chia cho 2016.
+
+Em cần tạo file kết quả có tên là `TRIGRID.TXT` gồm 15 dòng, mỗi dòng ghi một số
+nguyên duy nhất là số dư của số tam giác đếm được khi chia cho 2016 ứng với một
+giá trị `a` trong bảng dưới đây:
+
+         a          | TRIGRID.TXT
+------------------- | -----------
+4                   | 27
+3                   |
+5                   |
+6                   |
+111                 |
+222                 |
+3333                |
+4444                |
+55555               |
+666666              |
+7777777             |
+88888888            |
+999999999           |
+123456789123456789  |
+1000000000000000000 |
+
+Chú ý: Kết quả tương ứng với giá trị `n` nào cần ghi ĐÚNG trên dòng tương ứng
+với giá trị `a` đó.
+
+## Bài 2. SỐ DƯ (30 điểm)
+
+Giờ học về phép chia có dư tỏ ra quá dễ dàng cho các bé trường mầm non
+SuperKids, để tăng tính hấp dẫn cho giờ học, cô giáo muốn đặt ra một thách thức
+mới.
+
+Cho ba số nguyên dương `x`, `n`, `m`. Cô giáo xét dãy chữ số là biểu diễn thập
+phân của `x` và viết lặp đi lặp lại dãy chữ số này `n` lần để được biểu diễn
+thập phân của một số `y`. Nhiệm vụ của các bé là phải cho biết số
+dư của `y` khi chia cho `m`.
+
+Ví dụ với `x` = 12, `n` = 3, `m` = 8. số `y` = 121212, số dư của `y` khi chia
+cho 8 là 4.
+
+Các bé làm việc rất hào hứng và nhanh chóng đưa ra kết quả, vấn đề của cô giáo
+là cần biết kết quả đúng để phát phiếu bé ngoan cho các bé làm đúng và nhanh
+nhất. Em hãy giúp cô giáo tính toán kết quả.
+
+Em cần tạo file kết quả có tên là `REMAINDER.TXT` gồm 15 dòng, mỗi dòng ghi một
+số nguyên duy nhất là kết quả tìm được ứng một bộ giá trị `x`, `n`, `m` dưới
+đây:
+
+         x         |         n          |         m          | REMAINDER.TXT
+------------------ | ------------------ | ------------------ | -------------
+12                 | 3                  | 8                  | 4
+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 |
+
+Chú ý: Kết quả tương ứng bộ dữ liệu nào cần ghi ĐÚNG trên dòng tương ứng với bộ
+dữ liệu đó.
+
+## Bài 3. NÔNG TRẠI VUI VẺ (40 điểm)
+
+Bản đồ trang trại của ông Đông có thể mô tả như một bảng kích thước `n` × `n`
+được chia thành lưới ô vuông đơn vị. Các hàng của bảng được đánh số từ 1 đến
+`n` từ trên xuống dưới, các cột của bảng được đánh số từ 1 đến `n` từ trái sang
+phải. Ô nằm ở hàng `i`, cột `j` được gọi là ô (`i`, `j`).
+
+Ông Đông là người rất trật tự vì vậy ông đã bố trí xem kẽ những chuồng trâu và
+chuồng bò trong trang trại của mình. Cụ thể là: nếu ô (`i`, `j`) có `i` + `j`
+chẵn thì ông sẽ đặt một chuồng trâu; nếu ô (`i`, `j`) có `i` + `j` lẻ thì ông
+sẽ đặt chuồng bò. Có thể thấy rằng, theo cách thức như vậy sẽ không có hai
+chuồng giáp cạnh nhau cùng nuôi trâu hoặc cùng nuôi bò.
+
+Vì số lượng chuồng rất lớn, nên ông Đông thiết kế một máy đếm tự động. Cách
+thức làm việc của máy là mỗi khi ông Đông đưa vào một phạm vi hình chữ nhật
+được giới hạn bởi ô ở góc trái trên (`r1` , `c1` ) và góc phải dưới (`r2` ,
+`c2` ) thì máy đếm sẽ tự động đếm số chuồng trâu trong các ô thuộc phạm vi này
+(Những ô (`i`, `j`) có `r1` ≤ `i` ≤ `r2` và `c1` ≤ `j` ≤ `c2` ). Dĩ nhiên từ
+con số máy trả về cũng có thể suy ra số chuồng bò trong phạm vi đó.
+
+Lũ trâu bò của ông Đông rất tinh nghịch và thông minh, chúng phát hiện ra rằng
+máy đếm số chuồng trâu dựa vào màu lông của chúng. Vì vậy để “lừa" máy đếm tự
+động, những con bò có thể nhuộm đen lông của chúng để trông giống như trâu và
+những con trâu cũng có thể nhuộm vàng lông của chúng để trông giống như bò. Vào
+ngày tổ chức kì thi tin học trẻ, ông Đông được mật báo rằng lũ trâu bò ở hai
+chuồng tại hai ô khác nhau đã tiến hành nhuộm lông chúng theo cách trên, điều
+này khiến cho máy đếm trâu bò của ông hoạt động không được chính xác. Ông Đông
+muốn nhờ các bạn, dựa vào hoạt động của máy và quy tắc phân bố các chuồng ban
+đầu, phát hiện vị trí hai chuồng mà lũ gia súc đã tự ý nhuộm đổi màu lông.
+
+### Thư viện
+
+Chương trình của bạn phải đặt tên là `FARM.pas`/`FARM.cpp` tùy theo ngôn ngữ
+lập trình bạn sử dụng.
+
+Chương trình phải khai báo sử dụng một thư viện đặc biệt được ban giám khảo
+cung cấp để làm bài toán này. Thư viện gồm có các file `detect.pp` (dành cho
+Pascal); `detect.cpp` và `detect.h` (dành cho C++).
+
+Cách khai báo:
+
+    Pascal: uses detect;
+    C++: include "detect.h"
+
+Thư viện detect cung cấp các hàm và thủ tục sau đây mà bạn có thể dùng trong
+chương trình `FARM.pas`/`FARM.cpp`.
+
+    Pascal: function get_n: longint
+    C++: int get_n()
+
+Chương trình của bạn cần phải gọi hàm này để nhận được giá trị `n`. Giá trị `n`
+trả về đảm bảo 2 ≤ `n` ≤ 100000. **Hàm `get_n` này cần phải được gọi trước khi
+gọi bất cứ hàm nào khác của thư viện.**
+
+    Pascal: function buffalo(r1, c1, r2, c2: longint): int64
+    C++: long long buffalo(int r1, int c1, int r2, int c2)
+
+Hàm này trả về số chuồng trâu ở các ô (`i`, `j`) mà `r1` ≤ `i` ≤ `r2` và `c1` ≤
+`j` ≤ `c2`. Bạn cần đảm bảo hàm này được gọi với các giá trị thoả mãn 1 ≤ `r1`
+≤ `r2` ≤ `n` và 1 ≤ `c1` ≤ `c2` ≤ `n`. Nếu các tham số không thoả mãn hàm sẽ
+trả về giá trị -1. Nếu hàm này được gọi quá 1000000 lần, thư viện sẽ tự động
+ngắt chương trình và bạn bị ghi nhận 0 điểm.
+
+    Pascal: procedure answer(x1, y1, x2, y2: longint)
+    C++: void answer(int x1, int y1, int x2, int y2)
+
+Bạn cần gọi hàm này để kết thúc chương trình. Các tham số (`x1` , `y1` ) và
+(`x2` , `y2` ) chỉ ra hai ô mà trâu/bò trong hai chuồng đó tự ý nhuộm đổi màu
+lông.
+
+### Biên dịch
+
+Nếu bạn viết chương trình bằng Pascal, bạn phải khai báo sử dụng thư viện `uses
+detect;` ngay sau dòng tiêu đề chương trình (xem ví dụ cuối bài).
+
+Nếu bạn viết chương trình bằng C/C++, bạn phải khai báo sử dụng thư viện
+`#include “detect.h”` (xem ví dụ cuối bài). Nếu bạn sử dụng Code Blocks hoặc
+DevCpp, bạn nên tạo một Project có chứa cả file bài làm và các files thư viện
+cho tiện lợi trong việc dịch chương trình.
+
+### Thử nghiệm chương trình
+
+Trong quá trình làm bài, bạn được cung cấp:
+
+* Các file thư viện: `detect.pas`, `detect.h` và `detect.cpp`.
+* Các file chương trình mẫu: `sample_FARM.pas` và `sample_FARM.cpp` Các bạn có
+  thể dựa vào hai file chương trình mẫu này để hiểu cách sử dụng thư viện. Lưu
+  ý rằng hai chương trình mẫu này không phải là chương trình tốt.
+
+Ví dụ với `n` = 4, sơ đồ bố trí các chuồng trâu bò của ông Đông như sau (ô đen
+là chuồng trâu):
+
+![](sample_FARM.png)
+
+Chương trình `FARM.pas` có thể như sau:
+
+```pascal
+program FARM;
+
+uses detect;
+
+var
+  n: LongInt;
+
+begin
+  n := get_n;
+
+  if (n = 4) and
+     (buffalo(1, 2, 2, 3) = 1) and
+     (buffalo(2, 1, 3, 2) = 1) and
+     (buffalo(1, 1, 3, 1) = 2) and
+     (buffalo(3, 4, 3, 4) = 1) then
+    answer(2, 2, 3, 4);
+end.
+```
+
+Chương trình `FARM.cpp` có thể như sau:
+
+```cpp
+#include "detect.h"
+int 
+main()
+{
+  int n = get_n();
+
+  if (n == 4
+      && buffalo(1, 2, 2, 3) == 1 && buffalo(2, 1, 3, 2) == 1
+      && buffalo(1, 1, 3, 1) == 2 && buffalo(3, 4, 3, 4) == 1)
+    answer(2, 2, 3, 4);
+
+  return 0;
+}
diff --git a/THT/B/QG-2016/REMAINDER.TXT b/THT/B/QG-2016/REMAINDER.TXT
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/THT/B/QG-2016/REMAINDER.TXT
diff --git a/THT/B/QG-2016/remainder.py b/THT/B/QG-2016/remainder.py
index 45681ca..2c4de2d 100644..100755
--- a/THT/B/QG-2016/remainder.py
+++ b/THT/B/QG-2016/remainder.py
@@ -1,19 +1,44 @@
 #!/usr/bin/env python3
 
-l = [
-        (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)
+TESTS = [
+    [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]
 ]
+
+
+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)
+# y chia m bằng k dư q hay x * (a**n - 1) / (a - 1) = k * m + q
+#                      <=> x * (a**n - 1) = k * (a*m - a) + q * (a - 1)
+#                      <=> q = x * (a**n - 1) % (a*m - a) / (a - 1)
+
+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])
+        f.write(str(case[0] * (p - 1) % case[2] // (a - 1)) + '\n')
diff --git a/THT/B/QG-2016/sample_FARM.png b/THT/B/QG-2016/sample_FARM.png
new file mode 100644
index 0000000..364e7a1
--- /dev/null
+++ b/THT/B/QG-2016/sample_FARM.png
Binary files differdiff --git a/THT/B/QG-2016/trigrid.c b/THT/B/QG-2016/trigrid.c
index 5b8606c..7f5a75f 100644
--- a/THT/B/QG-2016/trigrid.c
+++ b/THT/B/QG-2016/trigrid.c
@@ -1,9 +1,9 @@
 #include <stdio.h>
 
 
-const long long a[] = {4, 3, 5, 6, 111, 222, 3333, 4444, 55555, 666666, 7777777,
-                       88888888, 999999999, 123456789123456789,
-                       1000000000000000000};
+const long long TESTS[] = {4, 3, 5, 6, 111, 222, 3333, 4444, 55555, 666666,
+                           7777777, 88888888, 999999999, 123456789123456789,
+                           1000000000000000000};
 
 long long quadratic(long long x, char a, char b, char c)
 {
@@ -19,8 +19,8 @@ int main()
 	f = fopen("TRIGRID.TXT", "w");
 
 	for (i = 0; i < 15; i++) {
-		q = a[i] % 2016;
-		k = a[i] / 2016 % 2016 * 252 * quadratic(q, 6, 10, 2);
+		q = TESTS[i] % 2016;
+		k = TESTS[i] / 2016 % 2016 * 252 * quadratic(q, 6, 10, 2);
 		fprintf(f, "%d\n", (k + quadratic(q, 2, 5, 2) * q / 8) % 2016);
 	}
 
diff --git a/THT/B/QG-2016/trigrid.py b/THT/B/QG-2016/trigrid.py
index ea33d07..0911ef9 100755
--- a/THT/B/QG-2016/trigrid.py
+++ b/THT/B/QG-2016/trigrid.py
@@ -1,10 +1,11 @@
 #!/usr/bin/env python3
 
-a = (4, 3, 5, 6, 111, 222, 3333, 4444, 55555, 666666, 7777777, 88888888,
-     999999999, 123456789123456789, 1000000000000000000)
+TESTS = (4, 3, 5, 6, 111, 222, 3333, 4444, 55555, 666666, 7777777, 88888888,
+         999999999, 123456789123456789, 1000000000000000000)
 
-t = lambda n: n * (n + 2) * (n * 2 + 1) // 8 % 2016
+# Fomular from http://mathworld.wolfram.com/TriangleTiling.html
+n = lambda a: a * (a + 2) * (a * 2 + 1) // 8 % 2016
 
 with open('TRIGRID.TXT', 'w') as f:
-    for i in a:
-        f.write("{}\n".format(t(i)))
+    for a in TESTS:
+        f.write("{}\n".format(n(a)))