From 5cfeec0f11dbcff922fe5b1a1a17bccf4812852e Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Thu, 3 Aug 2017 03:06:23 +0700 Subject: [others] Move other/colorec.* to mHoang and add other/{defrac,lang}.py --- others/mHoang/README.md | 39 +++++++++++++++ others/mHoang/colorec.pas | 54 +++++++++++++++++++++ others/mHoang/colorec.py | 28 +++++++++++ others/other/README.md | 119 +++++++++++++++++++++++++++++++--------------- others/other/colorec.pas | 54 --------------------- others/other/colorec.py | 28 ----------- others/other/defrag.py | 32 +++++++++++++ others/other/lang.py | 24 ++++++++++ 8 files changed, 257 insertions(+), 121 deletions(-) create mode 100644 others/mHoang/colorec.pas create mode 100755 others/mHoang/colorec.py delete mode 100644 others/other/colorec.pas delete mode 100755 others/other/colorec.py create mode 100755 others/other/defrag.py create mode 100755 others/other/lang.py diff --git a/others/mHoang/README.md b/others/mHoang/README.md index 05aa6bc..44574f8 100644 --- a/others/mHoang/README.md +++ b/others/mHoang/README.md @@ -73,3 +73,42 @@ Ghi ra thiết bị xuất chuẩn số đèn xanh sau lần bấm công tắc t | Sample Input | Sample Output | | :----------: | :-----------: | | 6 | 2 | + +## 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 +*Ai*(*xi*, *yi*), *i* = 1, 2, …, *n*. Mỗi điểm +*Ai* được tô bởi màu *ci* ∈ {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 *xi*, + *yi*, *ci* 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. +* |*xi*|, |*yi*| ≤ 200. + +### Ví dụ + +| COLOREC.INP | COLOREC.OUT | +| --------------------------------------------------------------------- | :---------: | +| 7
0 0 1
0 1 4
2 1 2
2 -1 3
0 -1 1
-1 -1 4
-1 1 1 | 2 | diff --git a/others/mHoang/colorec.pas b/others/mHoang/colorec.pas new file mode 100644 index 0000000..a6931aa --- /dev/null +++ b/others/mHoang/colorec.pas @@ -0,0 +1,54 @@ +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/mHoang/colorec.py b/others/mHoang/colorec.py new file mode 100755 index 0000000..d55ac7f --- /dev/null +++ b/others/mHoang/colorec.py @@ -0,0 +1,28 @@ +#!/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/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
3 3 1
3 3 1
3 3 1
3 3 1
3 3 1
3 2 2 | TRUE
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 -*Ai*(*xi*, *yi*), *i* = 1, 2, …, *n*. Mỗi điểm -*Ai* được tô bởi màu *ci* ∈ {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 *xi*, - *yi*, *ci* 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. -* |*xi*|, |*yi*| ≤ 200. - -### Ví dụ - -| COLOREC.INP | COLOREC.OUT | -| --------------------------------------------------------------------- | :---------: | -| 7
0 0 1
0 1 4
2 1 2
2 -1 3
0 -1 1
-1 -1 4
-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
1
10 | 1
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ỉ (a1 , +b1), (a2, b2), …, (aN, +bN). Các khối này được sắp xếp theo địa chỉ và không giao nhau, +nghĩa là 0 ≤ aj ≤ bj < aj+1 < 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 (a1 , b1), (a2, + b2), …, (aN, bN). + +### 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 ≤ 230. + +### Ví dụ + +| DEFRAC.INP | DEFRAC.OUT | +| ----------------- | :--------: | +| 10 2 4
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
JUMP 4 or 6
NEXT
JUMP 3
NEXT
JUMP 8
NEXT
NEXT | 2
5
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) -- cgit 1.4.1