From 7c9b47ab9149d292d5493c865dfb8742a7450472 Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Tue, 10 Jan 2017 21:30:06 +0700 Subject: others/other: Add {bin,game}.pas and move others/dict here --- others/dict/README.md | 53 ------------------ others/dict/dict.c | 53 ------------------ others/dict/dict.py | 17 ------ others/other/README.md | 147 ++++++++++++++++++++++++++++++++++++++++++++++--- others/other/bin.pas | 24 ++++++++ others/other/dict.c | 53 ++++++++++++++++++ others/other/dict.py | 17 ++++++ others/other/game.pas | 62 +++++++++++++++++++++ 8 files changed, 296 insertions(+), 130 deletions(-) delete mode 100644 others/dict/README.md delete mode 100644 others/dict/dict.c delete mode 100755 others/dict/dict.py create mode 100644 others/other/bin.pas create mode 100644 others/other/dict.c create mode 100755 others/other/dict.py create mode 100644 others/other/game.pas diff --git a/others/dict/README.md b/others/dict/README.md deleted file mode 100644 index 50ff841..0000000 --- a/others/dict/README.md +++ /dev/null @@ -1,53 +0,0 @@ -# Từ điển - -Cho một từ điển, là một danh sách gồm `n` từ `w`. Cho `q` truy vấn, mỗi truy vấn đưa ra -một xâu `s`, yêu cầu đếm xem có bao nhiêu từ có tiền tố là `s`. - -## Input - -`dict.inp` gồm `n` + `q` + 2 dòng: - -* Dòng 1: Gồm một số nguyên là số `n`, số lượng từ của từ điển. -* Dòng 2 đến `n` + 1: Mỗi dòng gồm một xâu kí tự `w` là một từ thuộc từ điển. -* Dòng `n` + 2: Gồm một số nguyên là số `q`, số lượng truy vấn. -* Dòng `n` + 3 đến `n` + `q` + 2: Mỗi dòng gồm một xâu kí tự `s` mô tả một tiền - tố cần đếm. - -## Output - -`dict.out` gồm `q` dòng, mỗi dòng gồm một số nguyên là câu trả lời cho -truy vấn tương ứng. - -## Giới hạn - -* 1 ≤ `n`, `q` ≤ 20000. -* 1 ≤ Độ dài `w`, `s` ≤ 20. -* Các xâu `w`, `s` gồm các chữ cái in thường (từ `a` đến `z`). - -## Ví dụ - -`dict.inp`: - - 4 - banana - ban - baconsoi - alibaba - 4 - ban - ba - ali - baba - -`dict.out`: - - 2 - 3 - 1 - 0 - -Giải thích: - -* 2 từ có tiền tố `ban` là: `banana`, `ban`. -* 3 từ có tiền tố `ba` là: `banana`, `ban`, `baconsoi`. -* 2 từ có tiền tố `ali` là: `alibaba`. diff --git a/others/dict/dict.c b/others/dict/dict.c deleted file mode 100644 index 9821828..0000000 --- a/others/dict/dict.c +++ /dev/null @@ -1,53 +0,0 @@ -#include -#include -#include - -int cmpstr(const void *s1, const void *s2) -{ - return strcmp((char *) s1, (char *) s2); -} - -short bistr(char (*a)[21], char *x, short hi) -{ - short lo = 0, mid; - - while (lo < hi) { - mid = (lo + hi) / 2; - if (strcmp(a[mid], x) < 0) - lo = mid + 1; - else - hi = mid; - } - - return lo; -} - -int main() -{ - FILE *fi = fopen("dict.inp", "r"), *fo = fopen("dict.out", "w"); - short n, q, i, idx, count; - char (*words)[21], s[21]; - - fscanf(fi, "%hd", &n); - - words = malloc(n * 21); - for (i = 0; i < n; i++) - fscanf(fi, "%s", words[i]); - qsort(words, n, 21, cmpstr); - - fscanf(fi, "%hd", &q); - - for (i = 0; i < q; i++) { - fscanf(fi, "%s", s); - idx = bistr(words, s, n); - count = idx; - while (count < n && !strncmp(words[count], s, strlen(s))) - count++; - fprintf(fo, "%hd\n", count - idx); - } - - fclose(fi); - fclose(fo); - - return 0; -} diff --git a/others/dict/dict.py b/others/dict/dict.py deleted file mode 100755 index 76b8414..0000000 --- a/others/dict/dict.py +++ /dev/null @@ -1,17 +0,0 @@ -#!/usr/bin/env python3 - -from itertools import islice -from bisect import bisect_left as bisect - - -with open('dict.inp') as fi, open('dict.out', 'w') as fo: - words = list(islice(fi, int(fi.readline()))) - words.sort() - - for _ in range(int(fi.readline())): - s = fi.readline().strip() - i = bisect(words, s) - count = 0 - while i + count < len(words) and words[i + count].startswith(s): - count += 1 - fo.write("{}\n".format(count)) diff --git a/others/other/README.md b/others/other/README.md index dade74b..1426c71 100644 --- a/others/other/README.md +++ b/others/other/README.md @@ -1,5 +1,75 @@ # Các bài tập khác +## Biểu diễn nhị phân + +Cho số nguyên dương n, hãy chuyển đổi n về dạng nhị phân. + +### Dữ liệu + +Tệp `BIN.INP` gồm một dòng duy nhất ghi số n. + +### Kết quả + +Tệp `BIN.OUT` gồm một dòng ghi biểu diễn nhị phân của n. + +### Ví dụ + +| BIN.INP | BIN.OUT | +| :-----: | :-----: | +| 109 | 1101101 | + +### Giới hạn + +n ≤ 1018. + +## Trò chơi với dãy số + +Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây: + +* Mỗi bạn chọn trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất + chọn là (b1, b2, …, bn) còn dãy số bạn thứ + hai chọn là (c1, c2, …, cn). +* Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ + nhất đưa ra số hạng bi, còn bạn thứ hai đưa ra số hạng + cj thì giá của lượt chơi đó sẽ là |bi + cj|. + +### Yêu cầu + +Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể. + +### Dữ liệu + +Tệp `GAME.INP` gồm ba dòng: + +* Dòng đầu tiên chứa số nguyên dương n. +* Dòng thứ hai chứa dãy số nguyên b1, b2, …, + bn. +* Dòng thứ ba chứa dãy số nguyên c1, c2, …, + cn. + +### Kết quả + +Tệp `GAME.OUT` gồm một dòng ghi giá nhỏ nhất tìm được. + +### Giới hạn + +* n ≤ 105. +* |bi|, |cj| < 263 ∀ 1 ≤ i, j ≤ n. + +### Ví dụ + +| GAME.INP | GAME.OUT | +| ---------------- | :------: | +| 2
1 -2
2 3 | 0 | + +#### Giải thích + +Dãy số bạn thứ nhất chọn là (1, −2) còn dãy số mà bạn thứ hai chọn là (2,3). + +Khi đó các khả năng có thể của một lượt chơi là (1,2), (1,3), (−2,2), (−2,3). +Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 +tương ứng với giá của lượt chơi (−2,2). + ## Tìm đoạn thẳng v2 Trên 1 đoạn trục số [−c, c], cho N đoạn thẳng, đoạn thứ i là [ai, @@ -17,14 +87,13 @@ mút). Tệp `INTERVAL.INP`: -* Dòng thứ nhất ghi ba số nguyên N, c và x (1 ≤ N ≤ 105; |x| ≤ c ≤ - 109). +* Dòng thứ nhất ghi ba số nguyên N, c và x. * N dòng tiếp theo, dòng thứ i + 1 ghi hai số nguyên ai, - bi (1 ≤ i ≤ N; |ai|, |bi| ≤ c). + bi. ### Kết quả -Tệp `INTERVAL.OUT`: +Tệp `INTERVAL.OUT` gồm hai dòng: * Dòng thứ nhất ghi số tự nhiên K là số đoạn chứa điểm M. * Dòng thứ hai: @@ -32,6 +101,12 @@ Tệp `INTERVAL.OUT`: * Nếu K = 0, ghi hai số nguyên là toạ độ hai đầu mút của đoạn thẳng dài nhất chứa M và không có điểm trong chung với N đoạn đã cho. +### Giới hạn + +* 1 ≤ N ≤ 105. +* |x| ≤ c ≤ 109. +* |ai|, |bi| ≤ c ∀ 1 ≤ i ≤ N. + ### Ví dụ | INTERVAL.INP | INTERVAL.OUT | @@ -41,22 +116,80 @@ Tệp `INTERVAL.OUT`: ## Phân tích số -Lập chương trình nhập vào 2 số nguyên dương n và m. +Cho hai số nguyên dương n và m. Tìm số tự nhiên k lớn nhất sao cho n! chia hết cho mk. ### Dữ liệu -Tệp `FDP.INP` gồm một dòng ghi hai số nguyên dương n và m (n ≤ 1018; -2 ≤ m ≤ 1012). +Tệp `FDP.INP` gồm một dòng ghi hai số nguyên dương n và m. ### Kết quả Tệp `FDP.OUT` gồm một dòng duy nhất ghi số tự nhiên k. +### Giới hạn + +* n ≤ 1018. +* 2 ≤ m ≤ 1012. + ### Ví dụ | FDP.INP | FDP.OUT | | :-----: | :-----: | | 10 10 | 2 | | 100 15 | 24 | + +## Từ điển + +Cho một từ điển gồm n từ w. Với q truy vấn, mỗi truy vấn đưa ra một xâu s, đếm +xem có bao nhiêu từ có tiền tố là s. + +### Dữ liệu + +Tệp `DICT.INP` gồm n + q + 2 dòng: + +* Dòng thứ nhất ghi một số nguyên n, số lượng từ của từ điển. +* Dòng 2 đến n + 1: Mỗi dòng gồm một xâu kí tự w là một từ thuộc từ điển. +* Dòng n + 2: Gồm một số nguyên là số q, số lượng truy vấn. +* Dòng n + 3 đến n + q + 2: Mỗi dòng gồm một xâu kí tự s mô tả một tiền tố cần + đếm. + +### Kết quả + +Tệp `DICT.OUT` gồm q dòng, mỗi dòng gồm một số nguyên là câu trả lời cho truy +vấn tương ứng. + +## Giới hạn + +* 1 ≤ n, q ≤ 20000. +* 1 ≤ Độ dài w, s ≤ 20. +* Các xâu w, s gồm các chữ cái in thường (từ `a` đến `z`). + +### Ví dụ + +`DICT.INP`: + + 4 + banana + ban + baconsoi + alibaba + 4 + ban + ba + ali + baba + +`DICT.OUT`: + + 2 + 3 + 1 + 0 + +#### Giải thích: + +* 2 từ có tiền tố `ban` là: `banana`, `ban`. +* 3 từ có tiền tố `ba` là: `banana`, `ban`, `baconsoi`. +* 2 từ có tiền tố `ali` là: `alibaba`. diff --git a/others/other/bin.pas b/others/other/bin.pas new file mode 100644 index 0000000..8543eda --- /dev/null +++ b/others/other/bin.pas @@ -0,0 +1,24 @@ +var + f: text; + n: int64; + s: string = ''; + +begin + assign(f, 'BIN.INP'); + reset(f); + readln(f, n); + close(f); + + while n > 0 do + begin + s := chr(n mod 2 + 48) + s; + n := n shr 1 + end; + + writeln(s); + + assign(f, 'BIN.OUT'); + rewrite(f); + writeln(f, s); + close(f) +end. diff --git a/others/other/dict.c b/others/other/dict.c new file mode 100644 index 0000000..9821828 --- /dev/null +++ b/others/other/dict.c @@ -0,0 +1,53 @@ +#include +#include +#include + +int cmpstr(const void *s1, const void *s2) +{ + return strcmp((char *) s1, (char *) s2); +} + +short bistr(char (*a)[21], char *x, short hi) +{ + short lo = 0, mid; + + while (lo < hi) { + mid = (lo + hi) / 2; + if (strcmp(a[mid], x) < 0) + lo = mid + 1; + else + hi = mid; + } + + return lo; +} + +int main() +{ + FILE *fi = fopen("dict.inp", "r"), *fo = fopen("dict.out", "w"); + short n, q, i, idx, count; + char (*words)[21], s[21]; + + fscanf(fi, "%hd", &n); + + words = malloc(n * 21); + for (i = 0; i < n; i++) + fscanf(fi, "%s", words[i]); + qsort(words, n, 21, cmpstr); + + fscanf(fi, "%hd", &q); + + for (i = 0; i < q; i++) { + fscanf(fi, "%s", s); + idx = bistr(words, s, n); + count = idx; + while (count < n && !strncmp(words[count], s, strlen(s))) + count++; + fprintf(fo, "%hd\n", count - idx); + } + + fclose(fi); + fclose(fo); + + return 0; +} diff --git a/others/other/dict.py b/others/other/dict.py new file mode 100755 index 0000000..76b8414 --- /dev/null +++ b/others/other/dict.py @@ -0,0 +1,17 @@ +#!/usr/bin/env python3 + +from itertools import islice +from bisect import bisect_left as bisect + + +with open('dict.inp') as fi, open('dict.out', 'w') as fo: + words = list(islice(fi, int(fi.readline()))) + words.sort() + + for _ in range(int(fi.readline())): + s = fi.readline().strip() + i = bisect(words, s) + count = 0 + while i + count < len(words) and words[i + count].startswith(s): + count += 1 + fo.write("{}\n".format(count)) diff --git a/others/other/game.pas b/others/other/game.pas new file mode 100644 index 0000000..5be1da2 --- /dev/null +++ b/others/other/game.pas @@ -0,0 +1,62 @@ +uses + sortnfind; + +var + f: text; + n, i, j: smallint; + b: array of int64; + c: int64; + a: qword = 0; + + +function sign(x: int64): shortint; + begin + if x < 0 then + exit(-1); + exit(1) + end; + + +function min( + x: qword; + y, z: int64 +): qword; + + var + tmp: qword; + + begin + if sign(y) = sign(z) then + tmp := abs(y) + abs(z) + else if abs(y) < abs(z) then + tmp := abs(z) - abs(y) + else + tmp := abs(y) - abs(z); + + if tmp < x then + exit(tmp); + exit(x) + end; + + +begin + assign(f, 'GAME.INP'); + reset(f); + readln(f, n); + setlength(b, n); + for i := 0 to n - 1 do + read(f, b[i]); + qsort(b); + for i := 0 to n - 1 do + begin + read(f, c); + for j := 0 to n - 1 do + a := min(a, b[j], c) + end; + close(f); + + assign(f, 'GAME.OUT'); + rewrite(f); + writeln(f, a); + close(f) +end. -- cgit 1.4.1