Translate others/other/nuoc.py to C++

2 files changed, 265 insertions, 0 deletions

diff --git a/others/other/README.md b/others/other/README.md
index 49e71e9..86d49f8 100644
--- a/others/other/README.md
+++ b/others/other/README.md
@@ -717,6 +717,198 @@ Số *m* tìm được.
 | :--------: | :--------: |
 |    7 3     |     2      |
 
+## Chữ số
+
+Cho xâu M lập thành từ tập H = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}
+và không bắt đầu bằng ký tự 0; xâu S giá trị ban đầu là xâu M.
+
+Người ta thực hiện L lần biến đổi theo các bước sau:
+
+* Đếm số lần xuất hiện các ký tự i thuộc tập H, đặt là K<sub>i</sub>.
+* Nếu K<sub>i</sub> > 0 người ta viết liên tiếp xâu biểu diễn K<sub>i</sub>
+  trong cơ số 16 và ký tự i, thu được giá trị mới của M.
+* Viết tiếp M vào cuối xâu S.
+
+### Yêu cầu
+
+Cho xâu M, số lần biến đổi L và X là một ký tự từ tập H. Hãy đếm số lần xuất
+hiện X trong S thu được sau L lần biến đổi.
+
+### Dữ liệu
+
+* Dòng thứ nhất chứa xâu M;
+* Dòng thứ hai chứa số tự nhiên L;
+* Dòng thứ ba chứa kí tự X.
+
+### Kết quả
+
+Một số nguyên là số lần xuất hiện của X trong S sau L lần biến đổi.
+
+### Giới hạn
+
+* M có độ dài không vượt quá 127 kí tự;
+* L ≤ 10<sup>7</sup>.
+
+### Ví dụ
+
+|   DIGIT.INP    | DIGIT.OUT |
+| -------------- | :-------: |
+| 150A<br>3<br>2 |     1     |
+
+#### Giải thích
+
+| Lần biến đổi |    M     |              S               |
+| :----------: | -------- | ---------------------------- |
+|       0      | 150A     | 150A                         |
+|       1      | 1011151A | 150A1011151A                 |
+|       2      | 1051151A | 150A1011151A1051151A         |
+|       3      | 1041251A | 150A1011151A1051151A1041251A |
+
+## Nguyên tố tương đương
+
+Hai số tự nhiên được gọi là *Nguyên tố tương đương* nếu chúng có chung các ước
+số nguyên tố. Ví dụ các số 75 và 15 là nguyên tố tương đương vì cùng có các
+ước nguyên tố là 3 và 5.
+
+### Yêu cầu
+
+Xét các số từ *a* đến *b*, hãy đếm xem có bao nhiêu cặp số (*x*, *y*) mà *x* <
+*y* và *x*, *y* là nguyên tố tương đương.
+
+### Dữ liệu
+
+* Dòng đầu chứa số nguyên *T* là số bộ dữ liệu;
+* *T* dòng sau, mỗi dòng chứa hai số nguyên dương *a*, *b*.
+
+### Kết quả
+
+Gồm *T* dòng, mỗi dòng là số cặp số nguyên tố tương đương tương ứng với bộ dữ
+liệu.
+
+### Giới hạn
+
+* *T* ≤ 10;
+* *a* ≤ *b* ≤ 10<sub>6</sub>.
+
+### Ví dụ
+
+|      EP.INP      | EP.OUT |
+| ---------------- | :----: |
+| 2<br>1 5<br>1 10 | 1<br>4 |
+
+## Số dư
+
+Cho *n* số nguyên dương *a<sub>1</sub>*, *a<sub>2</sub>*, …, *a<sub>n</sub>*,
+trong đó tồn tại ít nhất một cặp sô khác nhau. Hãy tìm số nguyên dương *d* lớn
+nhất để *a<sub>1</sub>* mod *d* = *a<sub>2</sub>* mod *d* = … = *a<sub>n</sub>*.
+
+### Dữ liệu
+
+* Dòng đầu chứa số nguyên dương *n*;
+* Dòng thứ hai chứa *n* số nguyên dương *a<sub>1</sub>*, *a<sub>2</sub>*, …,
+  *a<sub>n</sub>*;
+
+### Kết quả
+
+Gồm một dòng chứa số nguyên dương *d* lớn nhất thỏa mãn điều kiện đề bài.
+
+### Giới hạn
+
+* *n* ≤ 100;
+* *a<sub>i</sub>* ≤ 10<sup>16</sup>.
+
+### Ví dụ
+
+| remain.inp | remain.out |
+| ---------- | :--------: |
+| 3<br>3 7 9 |      2     |
+
+## LCM
+
+Trong số học, bội số chung nhỏ nhất (tiếng Anh: *Least Common Multiple* hoặc
+*Lowest Common Multiple* (LCM)) của hai số nguyên *x* và *y* là số nguyên dương
+nhỏ nhất chia hết cho cả x và y.
+
+### Yêu cầu
+
+Cho hai số nguyên dương *a* và *b* (*a* ≤ *b*), hãy đếm số cặp số nguyên dương
+*x*, *y* sao cho LCM(*x*, *y*) = *a* × (*a*+1) × … × *b*.
+
+### Dữ liệu
+
+* Dòng đầu chứa số nguyên *T* là số bộ dữ liệu;
+* *T* dòng sau, mỗi dòng chứa hai số nguyên dương *a*, *b*.
+
+### Kết quả
+
+Gồm *T* dòng, mỗi dòng tương ứng với *a*, *b* của bộ dữ liệu vào là số cặp số
+nguyên dương thoả mãn yêu cầu đề bài. Vì kết quả có thể rất lớn, hãy đưa ra giá
+trị là phần dư khi chia cho 111539786.
+
+### Giới hạn
+
+* *T* ≤ 10;
+* *a* ≤ *b* ≤ 10<sup>6</sup>.
+
+### Ví dụ
+
+|     LCM.INP     | LCM.OUT |
+| --------------- | :-----: |
+| 2<br>2 3<br>5 5 | 9<br>3  |
+
+## Khảo sát hang động ngầm
+
+Một nhóm chuyên gia có nhiệm vụ khảo sát một hang động ngầm mới được phát hiện.
+Nhiệm vụ của họ là vẽ sơ đồ hang, tìm hiểu về cấu trúc địa tầng, các hình thái
+của sự sống ở sâu trong lòng hang… Để đánh dấu đường đi, người ta dùng công cụ
+duy nhất là la bàn. Khi khởi hành và sau mỗi đơn vị khoảng cách, người phụ
+trách nhật ký của đoàn ghi lại hướng đi bằng một trong các chữ cái E, W, S, N
+tương ứng với việc đi theo các hướng Đông, Tây, Nam, Bắc (trong 1 đơn vị khoảng
+cách hướng đi không thay đổi). Một đoạn đường có thể đi lại khảo sát nhiều lần.
+Thông tin về đường đi được đưa vào máy tính sách tay để vẽ sơ đồ của hang đồng
+thời được dùng để tìm đường ra ngắn nhất theo lộ trình đã ghi nhận.
+
+### Yêu cầu
+
+Tìm độ dài đường ra ngắn nhất cho đoàn ra khỏi hang dựa theo đường ghi trong
+nhật ký.
+
+### Dữ liệu
+
+Gồm một số dòng các ký tự E, W, S, N, ghi liên tiếp nhau. Số ký tự không quá
+5000.
+
+### Kết quả
+
+Độ dài đường đi ngắn nhất tìm được.
+
+### Ví dụ
+
+|   KHAOSAT.INP    | KHAOSAT.OUT |                Giải thích                 |
+| ---------------- | :---------: | ----------------------------------------- |
+| EEENNWSEENWSSSWW |      6      | Đường đi ra theo chỉ dẫn của xâu `EENWWW` |
+
+## Chọn số
+
+Cho mảng A có kích thước NxN gồm các số nguyên không âm. Hãy chọn ra k số sao
+cho chọn một dòng có nhiều nhất 1 số được chọn, mỗi cột có nhiều nhất 1 số được
+chọn để tổng K số là lớn nhất.
+
+### Dữ liệu
+
+* Dòng đầu gồm 2 số N và K (K ≤ N ≤ 10);
+* N dòng tiếp theo là mảng A.
+
+### Kết quả
+
+Tổng lớn nhất chọn được và số cách chọn.
+
+### Ví dụ
+
+|          CHONSO1.INP           | CHONSO1.OUT |
+| ------------------------------ | :---------: |
+| 3 2<br>1 2 3<br>2 3 1<br>3 1 2 |     6 3     |
+
 ## Tính nước đọng
 
 Nền phẳng của 1 công trình xây dựng được chia thành lưới ô vuông đơn vị kích
diff --git a/others/other/nuoc.cpp b/others/other/nuoc.cpp
new file mode 100644
index 0000000..4b5ccf7
--- /dev/null
+++ b/others/other/nuoc.cpp
@@ -0,0 +1,73 @@
+#include <functional>
+#include <queue>
+#include <vector>
+#include <iostream>
+#include <fstream>
+
+#define MAX(a, b) (((a) < (b)) ? (b) : (a))
+#define ENC(h, x, y) (((h) << 14) + ((x) << 7) + (y))
+#define DEC_H(e) ((e) >> 14)
+#define DEC_X(e) ((e) >> 7 & 127)
+#define DEC_Y(e) ((e) & 127)
+
+using namespace std;
+
+int
+main()
+{
+  ifstream infile;
+  long m, n, i, j, height[100][100];
+  infile.open("NUOC.INP");
+  infile >> m >> n;
+  for (i = 0; i < m; i++)
+    for (j = 0; j < n; j++)
+      infile >> height[i][j];
+  infile.close();
+
+  priority_queue<long, vector<long>, greater<long>> heap;
+  bool visited[100][100] = {};
+  for (i = 0; i < m; i++)
+    {
+      heap.push(ENC(height[i][0], i, 0));
+      visited[i][0] = true;
+      heap.push(ENC(height[i][n - 1], i, n - 1));
+      visited[i][n - 1] = true;
+    }
+  for (i = 0; i < n; i++)
+    {
+      heap.push(ENC(height[0][i], 0, i));
+      visited[0][i] = true;
+      heap.push(ENC(height[m - 1][i], m - 1, i));
+      visited[m - 1][i] = true;
+    }
+
+  long h, x, y;
+  long result = 0, tmp;
+  while (!heap.empty())
+    {
+      tmp = heap.top();
+      heap.pop();
+      h = DEC_H(tmp);
+      i = DEC_X(tmp);
+      j = DEC_Y(tmp);
+      long adjacents[4][2] = {{i + 1, j}, {i, j + 1}, {i - 1, j}, {i, j + 1}};
+      for (auto a: adjacents)
+        {
+          x = a[0];
+          y = a[1];
+          if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y])
+            {
+              result += MAX(0, h - height[x][y]);
+              heap.push(ENC(MAX(height[x][y], h), x, y));
+              visited[x][y] = true;
+            }
+        }
+    }
+
+  ofstream outfile;
+  outfile.open("NUOC.OUT");
+  outfile << result << endl;
+  outfile.close();
+
+  return 0;
+}