From 9e28e4c7b67c54229df11d355047ac8a88ea1817 Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sun, 15 Dec 2019 15:09:13 +0700 Subject: Normalize pathname --- tht/B/QG-2014/DIC.DAT | 8 + tht/B/QG-2014/GIAODIEM.TXT | 10 ++ tht/B/QG-2014/README.md | 188 +++++++++++++++++++++++ tht/B/QG-2014/XEPHINH1.TXT | 6 + tht/B/QG-2014/XEPHINH2.TXT | 8 + tht/B/QG-2014/XEPHINH3.TXT | 7 + tht/B/QG-2014/XEPHINH4.TXT | 15 ++ tht/B/QG-2014/XEPHINH5.TXT | 15 ++ tht/B/QG-2014/dic.pp | 96 ++++++++++++ tht/B/QG-2014/giaodiem.c | 29 ++++ tht/B/QG-2014/giaodiem_img/example.png | Bin 0 -> 19933 bytes tht/B/QG-2014/giaodiem_img/piece1.png | Bin 0 -> 28315 bytes tht/B/QG-2014/giaodiem_img/piece2.png | Bin 0 -> 28719 bytes tht/B/QG-2014/giaodiem_img/piece3.png | Bin 0 -> 26048 bytes tht/B/QG-2014/guess.pas | 106 +++++++++++++ tht/B/QG-2014/sample.pas | 21 +++ tht/B/QG-2014/xephinh.pas | 270 +++++++++++++++++++++++++++++++++ tht/B/QG-2016/README.md | 234 ++++++++++++++++++++++++++++ tht/B/QG-2016/REMAINDER.TXT | 15 ++ tht/B/QG-2016/TRIGRID.TXT | 15 ++ tht/B/QG-2016/remainder.py | 31 ++++ tht/B/QG-2016/remainder.scm | 19 +++ tht/B/QG-2016/sample_FARM.png | Bin 0 -> 18545 bytes tht/B/QG-2016/trigrid.c | 29 ++++ tht/B/QG-2016/trigrid.py | 11 ++ tht/B/QG-2016/trigrid.scm | 6 + 26 files changed, 1139 insertions(+) create mode 100644 tht/B/QG-2014/DIC.DAT create mode 100644 tht/B/QG-2014/GIAODIEM.TXT create mode 100644 tht/B/QG-2014/README.md create mode 100644 tht/B/QG-2014/XEPHINH1.TXT create mode 100644 tht/B/QG-2014/XEPHINH2.TXT create mode 100644 tht/B/QG-2014/XEPHINH3.TXT create mode 100644 tht/B/QG-2014/XEPHINH4.TXT create mode 100644 tht/B/QG-2014/XEPHINH5.TXT create mode 100644 tht/B/QG-2014/dic.pp create mode 100644 tht/B/QG-2014/giaodiem.c create mode 100644 tht/B/QG-2014/giaodiem_img/example.png create mode 100644 tht/B/QG-2014/giaodiem_img/piece1.png create mode 100644 tht/B/QG-2014/giaodiem_img/piece2.png create mode 100644 tht/B/QG-2014/giaodiem_img/piece3.png create mode 100644 tht/B/QG-2014/guess.pas create mode 100644 tht/B/QG-2014/sample.pas create mode 100644 tht/B/QG-2014/xephinh.pas create mode 100644 tht/B/QG-2016/README.md create mode 100644 tht/B/QG-2016/REMAINDER.TXT create mode 100644 tht/B/QG-2016/TRIGRID.TXT create mode 100755 tht/B/QG-2016/remainder.py create mode 100644 tht/B/QG-2016/remainder.scm create mode 100644 tht/B/QG-2016/sample_FARM.png create mode 100644 tht/B/QG-2016/trigrid.c create mode 100644 tht/B/QG-2016/trigrid.py create mode 100644 tht/B/QG-2016/trigrid.scm (limited to 'tht/B') diff --git a/tht/B/QG-2014/DIC.DAT b/tht/B/QG-2014/DIC.DAT new file mode 100644 index 0000000..af9c850 --- /dev/null +++ b/tht/B/QG-2014/DIC.DAT @@ -0,0 +1,8 @@ +cat +can +mic +man +tiger +tac +hello +world diff --git a/tht/B/QG-2014/GIAODIEM.TXT b/tht/B/QG-2014/GIAODIEM.TXT new file mode 100644 index 0000000..ba0199e --- /dev/null +++ b/tht/B/QG-2014/GIAODIEM.TXT @@ -0,0 +1,10 @@ +1 +35 +210 +330 +1744 +210 +358 +1001 +1312 +1007 diff --git a/tht/B/QG-2014/README.md b/tht/B/QG-2014/README.md new file mode 100644 index 0000000..567e309 --- /dev/null +++ b/tht/B/QG-2014/README.md @@ -0,0 +1,188 @@ +# ĐỀ THI BẢNG B – TRUNG HỌC CƠ SỞ + +HỘI THI TIN HỌC TRẺ TOÀN QUỐC LẦN THỨ XX – 2016 + +Thời gian làm bài 150 phút, không kể thời gian phát đề + +## Tổng quan bài thi + +| Tên bài | Giới hạn thời gian | Số điểm | +| --------- | :----------------: | :-----: | +| Giao điểm | Không có | 20 | +| Xếp hình | Không có | 40 | +| Từ điển | 2 giây | 40 | + +## Giao điểm + +Mùa hè 2014, những người ngoài hành tinh đã có một chuyến viếng thăm trái đất. +Họ đến bằng đĩa bay và đã chọn một cánh đồng của Việt Nam để hạ cánh. Đĩa bay +có dạng hình tròn với N chân đế nên mỗi đĩa bay đã để lại trên cánh đồng một +đường tròn với có N điểm trên đường tròn đó. Khi đĩa bay hạ xuống, các chân đế +của một đĩa bay đã phát tia lazer để kết nối với nhau để lại các đường cháy +trên cánh đồng. Ngay sáng hôm sau các nhà khoa học đã đến và dự đinh sẽ cắm tại +mỗi giao điểm của các đường cháy bên trong mỗi đường tròn một lá cờ. Họ cũng +phát hiện ra rằng, trong mỗi đường tròn không có 3 đường cháy nào cắt nhau tại +cùng một điểm (trừ các điểm chân đế của đĩa bay). Vấn đề đặt ra là với mỗi +đường tròn, họ đã phải sử dụng bao nhiêu lá cờ. Các bạn hãy tính giúp các nhà +khoa học nhé, đó chính là một con số quan trọng trong quá trình nghiên cứu sự +hiện diện của người ngoài trái đất tại Việt Nam. + +Ví dụ, với hình dưới là đĩa bay có 5 chân đế tương ứng với N=5. Các đường cháy +để lại giao nhau tại 5 điểm. + +![](http://www.bryanray.name/wordpress/wp-content/uploads/pentacle.png) + +Các bạn sẽ nhận được một báo cáo gồm có 10 dòng tương ứng với 10 số N khác nhau +là số lượng chân đế trên 10 chiếc đĩa bay khác nhau. Bạn cần tạo file +`GIAODIEM.TXT` gồm 10 dòng, mỗi dòng ghi một số nguyên duy nhất là kết quả tìm +được, chính là số lá cờ cần sử dụng để cắm tại các giao điểm bên trong hình +tròn. Vì số lá cờ sẽ là rất lớn nên các nhà khoa học chỉ cần các bạn đưa ra +phần dư của số lượng lá cờ cho 2014. + +| Test | N | +| ---- | ---------------: | +| 1 | 4 | +| 2 | 7 | +| 3 | 10 | +| 4 | 11 | +| 5 | 7777 | +| 6 | 88888 | +| 7 | 1234567890 | +| 8 | 9999999999 | +| 9 | 12345678912345 | +| 10 | 2014201420142014 | + +## Xếp hình + +Trong quá trình nghiên cứu trên cánh đồng, các nhà khoa học còn phát hiện ra +một điều thú vị khác. Người ngoài hành tinh đã để lại một số hộp quà. Mỗi hộp +quà chứa một bộ ghép hình với một bảng nền có kích thước M×N ô vuông 1×1. Trong +hộp có một số miếng ghép thuộc ba loại dưới đây với số lượng khác nhau: + +![](giaodiem_img/piece1.png) +![](giaodiem_img/piece2.png) +![](giaodiem_img/piece3.png) + +Người ngoài hành tinh để lại lời nhắn rằng họ sẽ trở lại nếu các bạn xếp được +các miếng ghép không chồng lên nhau và phủ kín bảng nền. Các bạn có thể xoay +hoặc lật mặt các miếng ghép. Các bạn trong hội thi năm nay hãy giúp các nhà +nghiên cứu nhé. + +Các bạn sẽ nhận được các số M, N, A, B, C của 5 hộp quà trong bảng sau: + +| Hộp quà | M | N | A | B | C | +| :-----: | --- | --- | --- | --- | --- | +| 1 | 6 | 5 | 4 | 2 | 2 | +| 2 | 8 | 12 | 8 | 18 | 0 | +| 3 | 7 | 13 | 12 | 5 | 7 | +| 4 | 15 | 10 | 20 | 10 | 10 | +| 5 | 15 | 30 | 0 | 50 | 50 | + +Các số trên một dòng tương ứng là kích thước M×N của hình chữ nhật , A là số +miếng ghép loại 1, B là số miếng ghép loại 2 và C là số miếng ghép loại 3 của +các hộp quà. Các bạn cần đưa ra 5 file output tương ứng với từng hộp quà là +`XEPHINH1.TXT`, `XEPHINH2.TXT`, `XEPHINH3.TXT`, `XEPHINH4.TXT`, `XEPHINH5.TXT`. +Ở mỗi file output các bạn cần mô tả 1 cách xếp hình là một ma trận 2 chiều M×N +trên M dòng, mỗi dòng N số nguyên dương, các số trên một dòng cách nhau bởi một +dấu cách. Mỗi miếng ghép khi được sử dụng cần được đánh số thứ tự khác nhau sao +cho không có 2 miếng ghép nào có cùng một số thứ tự. Số ở dòng i cột j là một +số nguyên dương mô tả số thứ tự của hình phủ nó. + +Ví dụ: ta có bảng nền kích thước 3× 7 và 3 miếng ghép loại 1, 3 miếng ghép loại +2, 0 miếng ghép loại 3 thì ta có thể ghép như sau: + +![](giaodiem_img/example.png) + +Có thể mô tả lại bằng ma trận ở file output tương ứng với hình bên phải như sau: + + 1 2 3 4 4 4 6 + 1 2 3 3 3 4 6 + 1 2 5 5 5 6 6 + +Hoặc cách đánh số thứ tự vùng khác như sau: + + 6 4 1 2 2 2 5 + 6 4 1 1 1 2 5 + 4 6 3 3 3 5 5 + +Cả 2 cách trên đều được chấp nhận. + +## Từ điển + +Biết được việc các thí sinh thi Tin học trẻ giải được bài `XEPHINH`, người +ngoài hành tinh rất yêu quý đất nước Việt Nam. Họ quyết định trở lại để đến +thăm chúng ta. Tuy nhiên vì ngôn ngữ bất đồng nên các em không hiểu những người +ngoài hành tinh muốn nói gì. Vì vậy các em phải mang theo từ điển của mình ra +để cho họ xem. Sau đó các em sẽ đoán xem là họ muốn nói đến từ nào trong từ +điển. Từ điển cũng chỉ gồm 26 chữ cái thường từ *a* đến *z*. Tuy nhiên vì không +thể giải thích được với nhau nên hiện tại bước đầu giao tiếp vẫn là đoán từ và +các câu hỏi để đoán từ phải vô cùng đơn giản. + +Người ngoài hành tinh chỉ có thể hiểu các câu hỏi sau: + +1. Có bao nhiêu kí tự C trong từ đó? +2. Kí tự tại vị trí X là kí tự gì? + +Nhiệm vụ của các bạn là viết một chương trình `GUESS.PAS`, sử dụng các hàm +trong thư viện `DIC.PP` để thực hiện khảo sát từ điển trong file dữ liệu vào +`DIC.DAT` và đưa ra từ mà người ngoài hành tinh muốn nói là từ gì. File +`DIC.DAT` được cung cấp cho các bạn mô tả từ điển chỉ gồm danh sách các từ đôi +một khác nhau. Trong đó mỗi từ nằm trên một dòng và chỉ gồm các chữ cái in +thường từ *a* đến *z*. Số lượng từ trong file `DIC.DAT` tối đa là +106 từ và mỗi từ dài tối đa 50 kí tự. + +Chương trình `GUESS.PAS` của bạn phải khai báo sử dụng thư viện `DIC.PP` bằng cú pháp: + + Uses dic; + +Các hàm và thủ tục được cung cấp trong thư viện `DIC.PP`: + +* `function count_char(C: char): longint;` + * Trả về số lượng kí tự C trong từ cần tìm. + * Chi phí sử dụng hàm `count_char()` 1 lần là 1 đơn vị. + +* `function get_char_at_pos(X: longint): char;` + * Trả về kí tự tại vị trí X trong từ cần tìm. + * Nếu X lớn hơn độ dài của từ, hàm sẽ trả về kí tự *#*. + * Chi phí sử dụng hàm `get_char_at_pos()` 1 lần là 10 đơn vị. +* `Procedure answer(s:string);` + * Thủ tục `answer()` được dùng để trả về kết quả - là từ mà em đã xác định + được. + * Chi phí sử dụng thủ tục `answer()` là 0 đơn vị. + * Chương trình bắt buộc phải gọi thủ tục `answer()` một lần duy nhất, nếu + không sẽ bị 0 điểm. Thủ tục này khi được gọi sẽ tự động thoát chương + trình bằng câu lệnh `halt`. + +Với mỗi test, nếu chương trình của bạn gọi thủ tục `answer()` với đáp án không +chính xác, chạy quá thời gian quy định, sử dụng quá 1000 đơn vị hoặc gặp các +lỗi dẫn tới dừng chương trình, bài làm sẽ nhận 0 điểm cho test đó. + +Số điểm cho mỗi test sẽ giảm dần khi chi phí bạn sử dụng tăng lên. + +### Ví dụ + +Bộ từ điển có các từ sau: + + cat + can + mic + man + tiger + hello + world + +Từ người ngoài hành tinh muốn nói là *cat*. + +| Các thủ tục được gọi | Giá trị trả về | Giải thích | +| -------------------- | :------------: | ----------------------------------- | +| `get_char_at_pos(4)` | # | 4 vượt quá độ dài của từ *cat* là 3 | +| `count_char('c')` | 1 | Trong từ *cat* có 1 kí tự *c* | +| `count_char('a')` | 1 | Trong từ *cat* có 1 kí tự *a* | +| `count_char('n')` | 0 | Trong từ *cat* không có kí tự *n* | +| `answer('cat')` | | Bạn trả lời đúng với chi phí là 13 | + +### Ghi chú + +Trên máy làm bài của các bạn đã được cung cấp 3 file: `DIC.PP`, `DIC.DAT` và +`SAMPLE.PAS`. Bạn có thể tham khảo cách sử dụng `DIC.PP` và `DIC.DAT` trong +file `SAMPLE.PAS`. File `DIC.DAT` bạn nhận được là từ điển ví dụ. diff --git a/tht/B/QG-2014/XEPHINH1.TXT b/tht/B/QG-2014/XEPHINH1.TXT new file mode 100644 index 0000000..0b884be --- /dev/null +++ b/tht/B/QG-2014/XEPHINH1.TXT @@ -0,0 +1,6 @@ +1 2 3 3 3 +1 2 4 4 4 +1 2 5 5 4 +6 7 7 5 8 +6 7 5 5 8 +6 7 7 8 8 diff --git a/tht/B/QG-2014/XEPHINH2.TXT b/tht/B/QG-2014/XEPHINH2.TXT new file mode 100644 index 0000000..8dc8e6a --- /dev/null +++ b/tht/B/QG-2014/XEPHINH2.TXT @@ -0,0 +1,8 @@ +1 2 3 4 5 6 7 8 9 9 10 10 +1 2 3 4 5 6 7 8 9 11 10 12 +1 2 3 4 5 6 7 8 9 11 10 12 +13 13 14 15 15 15 16 16 11 11 12 12 +13 17 14 14 14 15 16 18 19 19 19 20 +13 17 17 17 21 21 16 18 18 18 19 20 +22 23 23 23 21 24 25 25 25 26 20 20 +22 22 22 23 21 24 24 24 25 26 26 26 diff --git a/tht/B/QG-2014/XEPHINH3.TXT b/tht/B/QG-2014/XEPHINH3.TXT new file mode 100644 index 0000000..bdf97ba --- /dev/null +++ b/tht/B/QG-2014/XEPHINH3.TXT @@ -0,0 +1,7 @@ +1 2 3 4 5 6 7 8 9 10 11 11 11 +1 2 3 4 5 6 7 8 9 10 12 12 11 +1 2 3 4 5 6 7 8 9 10 12 13 13 +14 14 14 15 15 15 16 16 17 17 12 12 13 +14 18 18 18 19 20 20 16 17 21 21 21 13 +22 18 22 18 19 20 16 16 17 21 23 21 23 +22 22 22 19 19 20 20 24 24 24 23 23 23 diff --git a/tht/B/QG-2014/XEPHINH4.TXT b/tht/B/QG-2014/XEPHINH4.TXT new file mode 100644 index 0000000..497341c --- /dev/null +++ b/tht/B/QG-2014/XEPHINH4.TXT @@ -0,0 +1,15 @@ +1 2 3 4 5 5 6 6 6 7 +1 2 3 4 5 8 6 8 6 7 +1 2 3 4 5 8 8 8 7 7 +9 10 11 12 13 13 14 14 14 15 +9 10 11 12 13 16 14 16 14 15 +9 10 11 12 13 16 16 16 15 15 +17 18 19 20 21 21 22 22 22 23 +17 18 19 20 21 24 22 24 22 23 +17 18 19 20 21 24 24 24 23 23 +25 26 27 28 29 29 30 30 30 31 +25 26 27 28 29 32 30 32 30 31 +25 26 27 28 29 32 32 32 31 31 +33 34 35 36 37 37 38 38 38 39 +33 34 35 36 37 40 38 40 38 39 +33 34 35 36 37 40 40 40 39 39 diff --git a/tht/B/QG-2014/XEPHINH5.TXT b/tht/B/QG-2014/XEPHINH5.TXT new file mode 100644 index 0000000..550e630 --- /dev/null +++ b/tht/B/QG-2014/XEPHINH5.TXT @@ -0,0 +1,15 @@ +1 1 2 2 3 3 21 21 22 22 23 23 41 41 42 42 43 43 61 61 62 62 63 63 81 81 82 82 83 83 +1 4 2 5 5 3 21 24 22 25 25 23 41 44 42 45 45 43 61 64 62 65 65 63 81 84 82 85 85 83 +1 4 2 2 5 3 21 24 22 22 25 23 41 44 42 42 45 43 61 64 62 62 65 63 81 84 82 82 85 83 +4 4 6 7 5 7 24 24 26 27 25 27 44 44 46 47 45 47 64 64 66 67 65 67 84 84 86 87 85 87 +8 8 6 7 7 7 28 28 26 27 27 27 48 48 46 47 47 47 68 68 66 67 67 67 88 88 86 87 87 87 +8 6 6 9 9 9 28 26 26 29 29 29 48 46 46 49 49 49 68 66 66 69 69 69 88 86 86 89 89 89 +8 8 10 10 10 9 28 28 30 30 30 29 48 48 50 50 50 49 68 68 70 70 70 69 88 88 90 90 90 89 +11 11 10 12 10 12 31 31 30 32 30 32 51 51 50 52 50 52 71 71 70 72 70 72 91 91 90 92 90 92 +11 13 13 12 12 12 31 33 33 32 32 32 51 53 53 52 52 52 71 73 73 72 72 72 91 93 93 92 92 92 +11 11 13 14 14 14 31 31 33 34 34 34 51 51 53 54 54 54 71 71 73 74 74 74 91 91 93 94 94 94 +15 15 13 16 16 14 35 35 33 36 36 34 55 55 53 56 56 54 75 75 73 76 76 74 95 95 93 96 96 94 +15 17 17 16 18 18 35 37 37 36 38 38 55 57 57 56 58 58 75 77 77 76 78 78 95 97 97 96 98 98 +15 15 17 16 16 18 35 35 37 36 36 38 55 55 57 56 56 58 75 75 77 76 76 78 95 95 97 96 96 98 +19 17 17 20 18 18 39 37 37 40 38 38 59 57 57 60 58 58 79 77 77 80 78 78 99 97 97 100 98 98 +19 19 19 20 20 20 39 39 39 40 40 40 59 59 59 60 60 60 79 79 79 80 80 80 99 99 99 100 100 100 diff --git a/tht/B/QG-2014/dic.pp b/tht/B/QG-2014/dic.pp new file mode 100644 index 0000000..716249d --- /dev/null +++ b/tht/B/QG-2014/dic.pp @@ -0,0 +1,96 @@ +unit dic; +interface + function count_char(c: char): longint; + function get_char_at_pos(x: longint): char; + procedure answer(s: string); + +implementation +var + secret_word: string; + words: array [1..1000000] of string; + total_cost, n: longint; + +procedure answer(s: string); +begin + if s = secret_word then + begin + writeln('Chuc mung ban da tim ra dap an chinh xac la "', s, '"'); + writeln('Chi phi ban da su dung la ', total_cost); + end + else + begin + writeln('Dap an ban dua ra la "', s, '"'); + writeln('Dap an chinh xac la "', secret_word, '"'); + end; + halt; +end; + +procedure cost_limit_exceed; +begin + writeln('Chi phi ban da su dung vuot qua chi phi toi da cho phep'); + halt; +end; + +function count_char(c: char): longint; +var + i, res: longint; +begin + total_cost := total_cost + 1; + if (total_cost > 1000) then + cost_limit_exceed; + res := 0; + for i := 1 to length(secret_word) do + if secret_word[i] = c then + inc(res); + exit(res); +end; + +function get_char_at_pos(x: longint): char; +begin + total_cost := total_cost + 10; + if (total_cost > 1000) then + cost_limit_exceed; + if (x < 1) or (x > length(secret_word)) then + exit('#'); + exit(secret_word[x]); +end; + +procedure check_secret_word; +var + f: text; + i: longint; + ok: boolean; +begin + assign(f, 'DIC.DAT'); + reset(f); + while not seekeof(f) do + begin + inc(n); + readln(f, words[n]); + end; + close(f); + ok := false; + for i := 1 to n do + if words[i] = secret_word then ok := true; + if not ok then + begin + writeln('Du lieu duoc khoi tao khong chinh xac. Dap an can tim khong nam trong tu dien'); + halt; + end; +end; + +procedure init; +begin + writeln; + writeln(' TU DIEN '); + writeln('*****************'); + writeln; + + secret_word := 'cat'; + total_cost := 0; + check_secret_word; +end; + +initialization + init; +end. diff --git a/tht/B/QG-2014/giaodiem.c b/tht/B/QG-2014/giaodiem.c new file mode 100644 index 0000000..78ca9b2 --- /dev/null +++ b/tht/B/QG-2014/giaodiem.c @@ -0,0 +1,29 @@ +#include + +const long long TESTS[] = {4, 7, 10, 11, 7777, 8888888, 1234567890, 9999999999, + 12345678912345, 2014201420142014}; + +int main() +{ + char i, j, k, divisor; + long long n, p; + FILE *f = fopen("GIAODIEM.TXT", "w"); + + for (i = 0; i < 10; i++) { + divisor = 24; + p = 1; + for (j = 0; j < 4; j++) { + n = TESTS[i] - j; + for (k = 2; k < 4; k++) { + while (!(n % k + divisor % k)) { + n /= k; + divisor /= k; + } + } + p *= n % 2014; + } + fprintf(f, "%d\n", p % 2014); + } + fclose(f); + return 0; +} diff --git a/tht/B/QG-2014/giaodiem_img/example.png b/tht/B/QG-2014/giaodiem_img/example.png new file mode 100644 index 0000000..2af578f Binary files /dev/null and b/tht/B/QG-2014/giaodiem_img/example.png differ diff --git a/tht/B/QG-2014/giaodiem_img/piece1.png b/tht/B/QG-2014/giaodiem_img/piece1.png new file mode 100644 index 0000000..a658789 Binary files /dev/null and b/tht/B/QG-2014/giaodiem_img/piece1.png differ diff --git a/tht/B/QG-2014/giaodiem_img/piece2.png b/tht/B/QG-2014/giaodiem_img/piece2.png new file mode 100644 index 0000000..7d467ac Binary files /dev/null and b/tht/B/QG-2014/giaodiem_img/piece2.png differ diff --git a/tht/B/QG-2014/giaodiem_img/piece3.png b/tht/B/QG-2014/giaodiem_img/piece3.png new file mode 100644 index 0000000..2aa00a0 Binary files /dev/null and b/tht/B/QG-2014/giaodiem_img/piece3.png differ diff --git a/tht/B/QG-2014/guess.pas b/tht/B/QG-2014/guess.pas new file mode 100644 index 0000000..af39434 --- /dev/null +++ b/tht/B/QG-2014/guess.pas @@ -0,0 +1,106 @@ +uses dic; + +type + dic_t = array of string; + coun_t = array['a'..'z'] of byte; + +var + f: text; + dict, new_dict: array[0..999999] of string; + chars: array of coun_t; + count: coun_t; + enum: array of record i, n: byte end; + len, new_len: longint; + i, j: byte; + c: char; + + +procedure swapbyte(var x, y: byte); + var + tmp: byte; + + begin + tmp := x; + x := y; + y := tmp + end; + + + +begin + len := 0; + assign(f, 'DIC.DAT'); + reset(f); + while not eof(f) do + begin + readln(f, dict[len]); + inc(len) + end; + close(f); + + setlength(chars, len); + for i := 0 to len - 1 do + begin + for c := 'a' to 'z' do + chars[i][c] := 0; + for c in dict[i] do + inc(chars[i][c]) + end; + for c := 'a' to 'z' do + count[c] := count_char(c); + + new_len := 0; + for i := 0 to len - 1 do + begin + for c := 'a' to '{' do + if chars[i][c] <> count[c] then + break; + if c = '{' then + begin + new_dict[new_len] := dict[i]; + inc(new_len) + end + end; + + setlength(enum, length(new_dict[0])); + for i := 0 to length(enum) - 1 do + begin + enum[i].i := i + 1; + enum[i].n := 0; + for c := 'a' to 'z' do + count[c] := 0; + for j := 0 to new_len - 1 do + inc(count[new_dict[j][i + 1]]); + for c := 'a' to 'z' do + if count[c] > 0 then + inc(enum[i].n) + end; + + for i := 0 to length(enum) - 2 do + for j := i + 1 to length(enum) - 1 do + if enum[i].n < enum[j].n then + begin + swapbyte(enum[i].n, enum[j].n); + swapbyte(enum[i].i, enum[j].i) + end; + + j := 0; + while new_len > 1 do + begin + len := new_len; + for i := 0 to len - 1 do + dict[i] := new_dict[i]; + + c := get_char_at_pos(enum[j].i); + new_len := 0; + for i := 0 to len - 1 do + if dict[i][enum[j].i] = c then + begin + new_dict[new_len] := dict[i]; + inc(new_len) + end; + inc(j) + end; + + answer(new_dict[0]) +end. diff --git a/tht/B/QG-2014/sample.pas b/tht/B/QG-2014/sample.pas new file mode 100644 index 0000000..c8b5e17 --- /dev/null +++ b/tht/B/QG-2014/sample.pas @@ -0,0 +1,21 @@ +uses dic; + +var + answer1: char; + answer2, answer3, answer4: longint; + +begin + answer1 := get_char_at_pos(4); + writeln('Vi tri thu 4 cua xau can tim la: ', answer1); + + answer2 := count_char('c'); + writeln('So luong ki tu c trong tu can tim la: ', answer2); + + answer3 := count_char('a'); + writeln('So luong ki tu a trong tu can tim la: ', answer3); + + answer4 := count_char('n'); + writeln('So luong ki tu n trong tu can tim la: ', answer4); + + answer('can'); +end. diff --git a/tht/B/QG-2014/xephinh.pas b/tht/B/QG-2014/xephinh.pas new file mode 100644 index 0000000..d428302 --- /dev/null +++ b/tht/B/QG-2014/xephinh.pas @@ -0,0 +1,270 @@ +uses math; + +type + gift_t = record + filename: string; + m, n, a, b, c: byte + end; + piece_t = array[1..3, 1..3] of boolean; + board_t = array[1..15, 1..30] of byte; + +const + gifts: array[1..5] of gift_t = ( + (filename: 'XEPHINH1.TXT'; m: 6; n: 5; a: 4; b: 2; c: 2), + (filename: 'XEPHINH2.TXT'; m: 8; n: 12; a: 8; b: 18; c: 0), + (filename: 'XEPHINH3.TXT'; m: 7; n: 13; a: 12; b: 5; c: 7), + (filename: 'XEPHINH4.TXT'; m: 3; n: 10; a: 4; b: 2; c: 2), + (filename: 'XEPHINH5.TXT'; m: 15; n: 6; a: 0; b: 10; c: 10) + ); + pieces: array[1..3] of piece_t = ( + ((false, true, false), (false, true, false), (false, true, false)), + ((false, true, true), (false, true, false), (false, true, false)), + ((false, true, true), (false, true, false), (false, true, true)) + ); + +var + f: text; + i, m, n, a, b, c: byte; + init_board: board_t; + done: boolean; + + +function divide(dividend, divisor: smallint): smallint; + begin + if dividend mod divisor = 0 then + exit(dividend div divisor); + divide := dividend div divisor + 1 + end; + + +function modulo(dividend, divisor: smallint): smallint; + begin + if dividend mod divisor = 0 then + exit(divisor); + modulo := dividend mod divisor + end; + + +function rotate( + piece: piece_t; + quarter: byte +): piece_t; + + var + i, j: byte; + + begin + if quarter = 0 then + exit(piece); + for i := 1 to 3 do + for j := 1 to 3 do + rotate[i][j] := piece[j][4 - i]; + exit(rotate(rotate, pred(quarter))) + end; + + +function flip(piece: piece_t): piece_t; + var + i, j: byte; + + begin + for i := 1 to 3 do + for j := 1 to 3 do + flip[i][j] := piece[4 - i][j] + end; + + +function putable( + board: board_t; + y, x: byte; + piece: piece_t +): boolean; + + var + yoff, xoff, i, j: byte; + + begin + if not piece[1][1] then + if piece[1][2] then + begin + yoff := 1; + xoff := 2 + end + else + begin + yoff := 2; + xoff := 1 + end + else + begin + yoff := 1; + xoff := 1 + end; + + for i := 1 to 3 do + for j := 1 to 3 do + if not piece[i][j] then + continue + else if not inrange(y + i - yoff, 1, m) or + not inrange(x + j - xoff, 1, n) or + (board[y + i - yoff][x + j - xoff] > 0) then + exit(false); + putable := true + end; + + +function put( + board: board_t; + y, x: byte; + piece: piece_t; + no: byte +): board_t; + + var + yoff, xoff, i, j: byte; + + begin + if not piece[1][1] then + if piece[1][2] then + begin + yoff := 1; + xoff := 2 + end + else + begin + yoff := 2; + xoff := 1 + end + else + begin + yoff := 1; + xoff := 1 + end; + + for i := 1 to 3 do + for j := 1 to 3 do + if piece[i][j] then + board[y + i - yoff][x + j - xoff] := no; + exit(board) + end; + + +procedure solve( + board: board_t; + position: smallint; + no: byte +); + + var + y, x: smallint; + i: byte; + + begin + if done then + exit; + while (board[divide(position, n)][modulo(position, n)] > 0) and + (position <= m * n) do + inc(position); + if position > m * n then + begin + for y := 1 to m do + begin + for x := 1 to n - 1 do + write(f, board[y][x], ' '); + writeln(f, board[y][n]) + end; + done := true; + exit + end; + + y := divide(position, n); + x := modulo(position, n); + for i := 0 to 1 do + if (a > 0) and + putable(board, y, x, rotate(pieces[1], i)) then + begin + dec(a); + solve(put(board, y, x, rotate(pieces[1], i), no), position, no + 1); + inc(a) + end; + for i := 0 to 3 do + if (b > 0) and + putable(board, y, x, rotate(pieces[2], i)) then + begin + dec(b); + solve(put(board, y, x, rotate(pieces[2], i), no), position, no + 1); + inc(b) + end; + for i := 1 to 3 do + if (b > 0) and + putable(board, y, x, rotate(flip(pieces[2]), i)) then + begin + dec(b); + solve(put(board, y, x, rotate(flip(pieces[2]), i), no), position, no + 1); + inc(b) + end; + for i := 0 to 3 do + if (c > 0) and + putable(board, y, x, rotate(pieces[3], i)) then + begin + dec(c); + solve(put(board, y, x, rotate(pieces[3], i), no), position, no + 1); + inc(c) + end; + end; + + +begin + for i := 1 to 5 do + begin + assign(f, gifts[i].filename); + rewrite(f); + m := gifts[i].m; + n := gifts[i].n; + for a := 1 to m do + for b := 1 to n do + init_board[a][b] := 0; + a := gifts[i].a; + b := gifts[i].b; + c := gifts[i].c; + done := false; + solve(init_board, 1, 1); + close(f) + end; + + assign(f, 'XEPHINH4.TXT'); + reset(f); + for m := 1 to 3 do + for n := 1 to 10 do + read(f, init_board[m][n]); + close(f); + assign(f, 'XEPHINH4.TXT'); + rewrite(f); + for a := 0 to 4 do + for m := 1 to 3 do + begin + for n := 1 to 9 do + write(f, init_board[m][n] + a * 8, ' '); + writeln(f, init_board[m][10] + a * 8) + end; + close(f); + + assign(f, 'XEPHINH5.TXT'); + reset(f); + for m := 1 to 15 do + for n := 1 to 6 do + read(f, init_board[m][n]); + close(f); + assign(f, 'XEPHINH5.TXT'); + rewrite(f); + for m := 1 to 15 do + begin + for a := 0 to 3 do + for n := 1 to 6 do + write(f, init_board[m][n] + a * 20, ' '); + for n := 1 to 5 do + write(f, init_board[m][n] + 80, ' '); + writeln(f, init_board[m][6] + 80); + end; + close(f); +end. diff --git a/tht/B/QG-2016/README.md b/tht/B/QG-2016/README.md new file mode 100644 index 0000000..f2293a8 --- /dev/null +++ b/tht/B/QG-2016/README.md @@ -0,0 +1,234 @@ +# ĐỀ 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..f7c3ff9 --- /dev/null +++ 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/TRIGRID.TXT b/tht/B/QG-2016/TRIGRID.TXT new file mode 100644 index 0000000..c44f939 --- /dev/null +++ b/tht/B/QG-2016/TRIGRID.TXT @@ -0,0 +1,15 @@ +27 +13 +48 +78 +868 +168 +400 +1233 +685 +819 +1693 +342 +1504 +1252 +576 diff --git a/tht/B/QG-2016/remainder.py b/tht/B/QG-2016/remainder.py new file mode 100755 index 0000000..6cef9df --- /dev/null +++ b/tht/B/QG-2016/remainder.py @@ -0,0 +1,31 @@ +#!/usr/bin/env python3 +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]] + +# 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 x, n, m in TESTS: + a = 10 ** len(str(x)) + m *= a - 1 + p = pow(a, n, m) + print(x * (p - 1) % m // (a - 1), file=f) diff --git a/tht/B/QG-2016/remainder.scm b/tht/B/QG-2016/remainder.scm new file mode 100644 index 0000000..8360da1 --- /dev/null +++ b/tht/B/QG-2016/remainder.scm @@ -0,0 +1,19 @@ +(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/sample_FARM.png b/tht/B/QG-2016/sample_FARM.png new file mode 100644 index 0000000..364e7a1 Binary files /dev/null and b/tht/B/QG-2016/sample_FARM.png differ diff --git a/tht/B/QG-2016/trigrid.c b/tht/B/QG-2016/trigrid.c new file mode 100644 index 0000000..15ad552 --- /dev/null +++ b/tht/B/QG-2016/trigrid.c @@ -0,0 +1,29 @@ +#include + +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) +{ + return a * x * x + b * x + c; +} + +int main() +{ + char i; + long long k, q; + FILE *f; + + f = fopen("TRIGRID.TXT", "w"); + + for (i = 0; i < 15; i++) { + 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); + } + + fclose(f); + + return 0; +} diff --git a/tht/B/QG-2016/trigrid.py b/tht/B/QG-2016/trigrid.py new file mode 100644 index 0000000..0911ef9 --- /dev/null +++ b/tht/B/QG-2016/trigrid.py @@ -0,0 +1,11 @@ +#!/usr/bin/env python3 + +TESTS = (4, 3, 5, 6, 111, 222, 3333, 4444, 55555, 666666, 7777777, 88888888, + 999999999, 123456789123456789, 1000000000000000000) + +# 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 a in TESTS: + f.write("{}\n".format(n(a))) 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)))) -- cgit 1.4.1