[others] Move other/colorec.* to mHoang and add other/{defrac,lang}.py

5 files changed, 136 insertions, 121 deletions

diff --git a/others/other/README.md b/others/other/README.md
index 4aaac34..eb632cd 100644
--- a/others/other/README.md
+++ b/others/other/README.md
@@ -563,45 +563,6 @@ Các số trong input không vượt quá 100.
 | :-----------------------------------------------------: | :-----------: |
 | 2<br>3 3 1<br>3 3 1<br>3 3 1<br>3 3 1<br>3 3 1<br>3 2 2 | TRUE<br>FALSE |
 
-## Hình chữ nhật bốn màu
-
-Trên mặt phẳng toạ độ Đề các vuông góc Oxy cho *n* điểm phân biệt
-*A<sub>i</sub>*(*x<sub>i</sub>*, *y<sub>i</sub>*), *i* = 1, 2, …, *n*. Mỗi điểm
-*A<sub>i</sub>* được tô bởi màu *c<sub>i</sub>* ∈ {1,2,3,4}. Ta gọi hình chữ
-nhật bốn màu là hình chữ nhật thoả mãn hai điều kiện sau:
-
-* Bốn đỉnh của hình chữ nhật là bốn điểm trong *n* điểm đã cho và được tô bởi
-  bốn màu khác nhau.
-* Các cạnh của hình chữ nhật song song với một trong hai trục toạ độ.
-
-### Yêu cầu
-
-Cho biết toạ độ và màu của *n* điểm, hãy đếm số lượng hình chữ nhật bốn màu.
-
-### Dữ liệu
-
-* Dòng đầu tiên chứa số nguyên dương *n* là số lượng điểm trên mặt phẳng.
-* Dòng thứ *i* trong *n* dòng tiếp theo chứa ba số nguyên *x<sub>i</sub>*,
-  *y<sub>i</sub>*, *c<sub>i</sub>* là thông tin về toạ độ và màu của điểm thứ 
-  *i*, *i* = 1, 2, …, *n*.
-
-*Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.*
-
-### Kết quả
-
-Một dòng chứa số lượng hình chữ nhật đếm được.
-
-### Giới hạn
-
-* 4 ≤ *n* ≤ 100000.
-* |*x<sub>i</sub>*|, |*y<sub>i</sub>*| ≤ 200.
-
-### Ví dụ
-
-|                              COLOREC.INP                              | COLOREC.OUT |
-| --------------------------------------------------------------------- | :---------: |
-| 7<br>0 0 1<br>0 1 4<br>2 1 2<br>2 -1 3<br>0 -1 1<br>-1 -1 4<br>-1 1 1 |      2      |
-
 ## Đếm gà và chó
 
 Hiện nay dịch cúm gia cầm đang lây lan nhưng ý thức những người buôn gia cầm
@@ -652,3 +613,83 @@ In ra T dòng, mỗi dòng gồm một số nguyên là kết quả của mỗi
 | Sample Input | Sample Output |
 | ------------ | ------------- |
 | 2<br>1<br>10 |    1<br>25    |
+
+## Dọn dẹp bộ nhớ
+
+Bộ nhớ của máy tính có dung lượng V byte được đánh số từ 0 đến V-1. Các khối bộ
+nhớ đã được phân phối được xác định bởi dãy các địa chỉ (a<sub>1 ,
+b<sub>1</sub>), (a<sub>2</sub>, b<sub>2</sub>), …, (a<sub>N</sub>,
+b<sub>N</sub>).  Các khối này được sắp xếp theo địa chỉ và không giao nhau,
+nghĩa là 0 ≤ a<sub>j</sub> ≤ b<sub>j</sub> < a<sub>j+1</sub> < V. Hệ điều hành
+cần cung cấp một khối gồm M byte cho một yêu cầu mới xuất hiện. Nếu như không
+gian nhớ tự do với dung lượng như vậy không còn, thì hệ điều hành cần dịch
+chuyển một khối nào đó để giải phóng được một đoạn nhớ liên tục có độ dài đòi
+hỏi.
+
+### Yêu cầu
+
+Tìm cách chọn khối bộ nhớ với dung lượng nhỏ nhất cần dịch chuyển để đáp ứng
+yêu cầu đặt ra. Trong trường hợp có nhiều cách lựa chọn, hãy đưa ra khối với
+địa chỉ đầu nhỏ nhất.
+
+### Dữ liệu
+
+* Dòng đầu là các số nguyên V N M.
+* Dòng tiếp theo là 2N cặp số nguyên (a<sub>1 , b<sub>1</sub>), (a<sub>2</sub>,
+  b<sub>2</sub>), …, (a<sub>N</sub>, b<sub>N</sub>).
+
+### Kết quả
+
+Một dòng chứa một số nguyên là:
+
+* -1, nếu không có cách di chuyển (không thể giải phóng không gian nhớ yêu
+  cầu), hoặc
+* 0 nếu không cần di chuyển, hoặc
+* chỉ số của khối cần di chuyển.
+
+### Giới hạn
+
+* 0 ≤ N ≤ 100000.
+* 1 ≤ V ≤ 2<sup>30</sup>.
+
+### Ví dụ
+
+|    DEFRAC.INP     | DEFRAC.OUT |
+| ----------------- | :--------: |
+| 10 2 4<br>1 5 7 7 |      2     |
+
+## Phân tích chương trình
+
+Trong việc phân tích chương trình, cần phát hiện xem đoạn mã nguồn của chương
+trình có chứa các câu lệnh mà không khi nào được thực hiện hay không (những
+lệnh như vậy để ngắn gọn ta gọi là lệnh thừa). Sự có mặt của các câu lệnh thừa
+thường mách bảo là chương trình còn lỗi. Do đó trong chương trình dịch của tất
+cả các ngôn ngữ lập trình luôn có môđun kiểm tra sự có mặt của các câu lệnh
+thừa.
+
+### Yêu cầu
+
+Bạn cần viết chương trình thực hiện công việc của môđun này.
+
+### Dữ liệu
+
+Gồm không quá 10000 dòng chứa dãy lệnh là kết quả của việc phân tích ngữ nghĩa
+của một đoạn mã nguồn. Mỗi dòng chứa một câu lệnh có một trong ba dạng sau:
+
+* `NEXT`: thực hiện câu lệnh kế tiếp nó;
+* `JUMP n` với n là số nguyên dương: thực hiện câu lệnh với chỉ số n (các câu
+  lệnh trong dãy lệnh được đánh số bắt đầu từ 1);
+* `JUMP n OR m` với n và m là các số nguyên dương: thực hiện một trong hai câu
+  lệnh với chỉ số n hoặc m.
+
+### Kết quả
+
+* Dòng đầu tiên ghi số nguyên k là số lượng câu lệnh thừa trong dãy lệnh đã cho.
+* Nếu k > 0 thì mỗi dòng trong số k dòng tiếp theo chứa chỉ số của một câu lệnh
+  thừa. Các chỉ số được đưa ra theo thứ tự tăng dần.
+
+### Ví dụ
+
+|                                LANG.INP                                 |  LANG.OUT   |
+| ----------------------------------------------------------------------- | :---------: |
+| NEXT<br>JUMP 4 or 6<br>NEXT<br>JUMP 3<br>NEXT<br>JUMP 8<br>NEXT<br>NEXT | 2<br>5<br>7 |
diff --git a/others/other/colorec.pas b/others/other/colorec.pas
deleted file mode 100644
index a6931aa..0000000
--- a/others/other/colorec.pas
+++ /dev/null
@@ -1,54 +0,0 @@
-type
-  pointtype = record
-    x, y: int16
-  end;
-
-var
-  f: text;
-  n, i, j: int32;
-  count: int32 = 0;
-  c, k: int8;
-  color: array[-200..200, -200..200] of int8;
-  points: array[1..4, 1..100000] of pointtype;
-  len: array[1..4] of int16 = (0, 0, 0, 0);
-
-function colorec(var a, b: pointtype): boolean;
-  begin
-    colorec := [color[a.x, b.y], color[b.x, a.y],
-                color[a.x, a.y], color[b.x, b.y]] = [1, 2, 3, 4]
-  end;
-
-begin
-  for i := -200 to 200 do
-    for j := -200 to 200 do
-      color[i, j] := 0;
-  assign(f, 'COLOREC.INP');
-  reset(f);
-  readln(f, n);
-  repeat
-    readln(f, i, j, c);
-    color[i, j] := c;
-    inc(len[c]);
-    points[c, len[c]].x := i;
-    points[c, len[c]].y := j
-  until eof(f);
-  close(f);
-
-  for k := 1 to 4 do
-    if len[k] <= n then
-      begin
-        c := k;
-        n := len[c]
-      end;
-  for i := 1 to n do
-    for k := 1 to 4 do
-      if k <> c then
-        for j := 1 to len[k] do
-          if colorec(points[c, i], points[k, j]) then
-            inc(count);
-
-  assign(f, 'COLOREC.OUT');
-  rewrite(f);
-  writeln(f, count);
-  close(f)
-end.
diff --git a/others/other/colorec.py b/others/other/colorec.py
deleted file mode 100755
index d55ac7f..0000000
--- a/others/other/colorec.py
+++ /dev/null
@@ -1,28 +0,0 @@
-#!/usr/bin/env python3
-from itertools import combinations
-
-COLORS = {1, 2, 3, 4}
-
-with open('COLOREC.INP') as f:
-    f.readline()
-    color, exes, eyes, count = {}, {}, {}, 0
-    for line in f:
-        x, y, c = map(int, line.split())
-        color[x, y] = c
-        exes.setdefault(y, [])
-        exes[y].append(x)
-        eyes.setdefault(x, [])
-        eyes[x].append(y)
-
-for v in eyes.values(): v.sort()
-for y0, l in exes.items():
-    for x0, x1 in combinations(l, 2):
-        s = COLORS - {color[x0, y0], color[x1, y0]}
-        if len(s) > 2: continue
-        for y1 in eyes[x0][y0:]:
-            try:
-                count += not s - {color[x0, y1], color[x1, y1]}
-            except:
-                continue
-
-with open('COLOREC.OUT', 'w') as f: print(count, file=f)
diff --git a/others/other/defrag.py b/others/other/defrag.py
new file mode 100755
index 0000000..df0e273
--- /dev/null
+++ b/others/other/defrag.py
@@ -0,0 +1,32 @@
+#!/usr/bin/env python3
+with open('DEFRAC.INP') as f:
+    v, n, m = map(int, f.readline().split())
+    t, l, b = tuple(map(int, f.readline().split())), [], -1
+
+for i in range(n):
+    a, b, p = t[i * 2], t[i*2 + 1], b
+    tmp = a - p - 1
+    if i: l[-1].extend([tmp, l[-1][1] + tmp >= m])
+    l.append([b - a + 1, tmp])
+tmp = v - b - 1
+l[-1].extend([tmp, l[-1][1] + tmp >= m])
+s = sorted(l, key=(lambda i: i[1]), reverse=True)
+
+with open('DEFRAC.OUT', 'w') as f:
+    if s[0][1] >= m:
+        f.write('0\n')
+    else:
+        best = None
+        for i, v in enumerate(l):
+            if best is None or v < best:
+                if v[-1]:
+                    best = v[0], i
+                elif sum(v[:3]) >= m:
+                    for j in s:
+                        if j is not v and j[1] >= v[0]:
+                            best = v[0], i
+                            break
+        if best is None:
+            f.write('-1\n')
+        else:
+            print(best[1] + 1, file=f)
diff --git a/others/other/lang.py b/others/other/lang.py
new file mode 100755
index 0000000..9c9f144
--- /dev/null
+++ b/others/other/lang.py
@@ -0,0 +1,24 @@
+#!/usr/bin/env python3
+def lang(index):
+    global unused
+    if index < len(unused) and unused[index]:
+        unused[index] = False
+        for i in commands[index]: lang(i)
+
+
+commands = []
+with open('LANG.INP') as f:
+    for index, line in enumerate(f):
+        l = line.split()
+        if l[0] == 'NEXT':
+            commands.append((index + 1,))
+        elif len(l) == 2:
+            commands.append((int(l[1]) - 1,))
+        else:
+            commands.append((int(l[1]) - 1, int(l[3]) - 1))
+
+unused = [True] * len(commands)
+lang(0)
+with open('LANG.OUT', 'w') as f:
+    print(sum(unused), file=f)
+    print(*(i + 1 for i, b in enumerate(unused) if b), sep='\n', file=f)