From dbeda825d396deff88ac6754b20c084bd77510b7 Mon Sep 17 00:00:00 2001
From: Raphael McSinyx <vn.mcsinyx@gmail.com>
Date: Mon, 14 Aug 2017 20:55:39 +0700
Subject: Add others/other/{chonso1.pas,khaosat.py}

---
 others/other/README.md   | 53 ++++++++++++++++++++++++++++++++++++++++++
 others/other/chonso1.pas | 60 ++++++++++++++++++++++++++++++++++++++++++++++++
 others/other/khaosat.py  |  9 ++++++++
 3 files changed, 122 insertions(+)
 create mode 100644 others/other/chonso1.pas
 create mode 100755 others/other/khaosat.py

diff --git a/others/other/README.md b/others/other/README.md
index fc88fd4..a44e555 100644
--- a/others/other/README.md
+++ b/others/other/README.md
@@ -855,3 +855,56 @@ trị là phần dư khi chia cho 111539786.
 |     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     |
diff --git a/others/other/chonso1.pas b/others/other/chonso1.pas
new file mode 100644
index 0000000..7e10400
--- /dev/null
+++ b/others/other/chonso1.pas
@@ -0,0 +1,60 @@
+var
+  f: text;
+  n, k, i, j: uint8;
+  max, count: uint64;
+  a: array[1..10, 1..10] of uint64;
+  avail: array[1..10] of boolean = (true, true, true, true, true,
+                                    true, true, true, true, true);
+
+
+procedure chonso1(
+  depth, len: uint8;
+  sum: uint64
+);
+
+  var
+    i: uint8;
+
+  begin
+    if len = k then
+      begin
+        if sum > max then
+          begin
+            max := sum;
+            count := 1
+          end
+        else if sum = max then
+          inc(count);
+        exit
+      end;
+
+    for i := 1 to n do
+      if avail[i] then
+        begin
+          avail[i] := false;
+          chonso1(depth + 1, len + 1, sum + a[depth, i]);
+          avail[i] := true
+        end;
+
+    if k - len <= n - depth then
+      chonso1(depth + 1, len, sum);
+  end;
+
+
+begin
+  assign(f, 'CHONSO1.INP');
+  reset(f);
+  readln(f, n, k);
+  for i := 1 to n do
+    for j := 1 to n do
+      read(f, a[i, j]);
+  close(f);
+
+  max := 0;
+  chonso1(1, 0, 0);
+
+  assign(f, 'CHONSO1.OUT');
+  rewrite(f);
+  writeln(f, max, ' ', count);
+  close(f)
+end.
diff --git a/others/other/khaosat.py b/others/other/khaosat.py
new file mode 100755
index 0000000..861d6f5
--- /dev/null
+++ b/others/other/khaosat.py
@@ -0,0 +1,9 @@
+#!/usr/bin/env python3
+DIRECTIONS = {'E': (1, 0), 'W': (-1, 0), 'S': (0, -1), 'N': (0, 1)}
+
+current, memory = (0, 0), {(0, 0): 0}
+with open('KHAOSAT.INP') as fi, open('KHAOSAT.OUT', 'w') as fo:
+    for c in fi.read().rstrip():
+        prev, current = current, tuple(map(sum, zip(current, DIRECTIONS[c])))
+        memory.setdefault(current, memory[prev] + 1)
+    print(memory[current], file=fo)
-- 
cgit 1.4.1