diff options
| -rw-r--r-- | others/other/README.md | 194 | ||||
| -rwxr-xr-x | others/other/nuoc.py | 27 |
2 files changed, 43 insertions, 178 deletions
diff --git a/others/other/README.md b/others/other/README.md index a44e555..49e71e9 100644 --- a/others/other/README.md +++ b/others/other/README.md @@ -717,194 +717,32 @@ Số *m* tìm được. | :--------: | :--------: | | 7 3 | 2 | -## Chữ số +## Tính nước đọng -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. +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 +thước MxN ô (*M*, *N* ≤ 100). Trên mỗi ô (*i*, *j*) của lưới, người ta dựng 1 +cột bê tông hình hộp có đáy là ô (*i*, *j*) và chiều cao là *h*[*i*, *j*] đơn +vị (1 ≤ *H*[*i*,*j*] ≤ 1000). Sau khi dựng xong thì trời đổ mưa to và đủ lâu. +Nhà thầu xây dựng muốn tính lượng nước đọng lại giữa các cột để có kế hoạch thi +công tiếp theo. Giả thiết, nước ko thẩm thấu qua các cột bê tông cũng như không +rò rỉ qua các đường ghép giữa chúng. ### 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. +Bạn hãy giúp nhà thầu tính toán lượng nước đọng lại giữa các cộ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. +* Dòng đầu tiên ghi 2 số nguyên dương *M* và *N*; +* Dòng thứ *i* trong *M* dòng tiếp theo, ghi *N* số nguyên dương *h*[*i*, 1], + *h*[*i*, 2]…, *h*[*i*, *N*]. ### Kết quả -Tổng lớn nhất chọn được và số cách chọn. +Một dòng duy nhất chứa số đơn vị khối nước đọng lại. ### Ví dụ -| CHONSO1.INP | CHONSO1.OUT | -| ------------------------------ | :---------: | -| 3 2<br>1 2 3<br>2 3 1<br>3 1 2 | 6 3 | +| NUOC.INP | NUOC.OUT | +| -------------------------------------------------------------------- | :------: | +| 5 5<br>9 9 9 9 9<br>9 2 2 2 9<br>9 2 5 2 9<br>9 2 2 2 9<br>9 9 9 9 9 | 60 | diff --git a/others/other/nuoc.py b/others/other/nuoc.py new file mode 100755 index 0000000..9fcff54 --- /dev/null +++ b/others/other/nuoc.py @@ -0,0 +1,27 @@ +#!/usr/bin/env python3 +from heapq import heapify, heappop, heappush + + +with open('NUOC.INP') as f: + m, n = map(int, f.readline().split()) + height = [[int(i) for i in line.split()] for line in f] + +queue = ([(h, 0, i) for i, h in enumerate(height[0])] + + [(h, m - 1, i) for i, h in enumerate(height[-1])] + + [(height[i][0], i, 0) for i in range(m)] + + [(height[i][-1], i, n - 1) for i in range(m)]) +heapify(queue) +visited = ([[True] * n] + + [[True] + [False] * (n - 2) + [True] for _ in range(m - 2)] + + [[True] * n]) +result = 0 + +while queue: + h, i, j = heappop(queue) + for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1): + if 0 <= x < m and 0 <= y < n and not visited[x][y]: + result += max(0, h - height[x][y]) + heappush(queue, (max(height[x][y], h), x, y)) + visited[x][y] = True + +with open('NUOC.OUT', 'w') as f: print(result, file=f) |