diff options
Diffstat (limited to 'others/other')
| -rw-r--r-- | others/other/README.md | 147 | ||||
| -rw-r--r-- | others/other/bin.pas | 24 | ||||
| -rw-r--r-- | others/other/dict.c | 53 | ||||
| -rwxr-xr-x | others/other/dict.py | 17 | ||||
| -rw-r--r-- | others/other/game.pas | 62 |
5 files changed, 296 insertions, 7 deletions
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 ≤ 10<sup>18</sup>. + +## 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à (b<sub>1</sub>, b<sub>2</sub>, …, b<sub>n</sub>) còn dãy số bạn thứ + hai chọn là (c<sub>1</sub>, c<sub>2</sub>, …, c<sub>n</sub>). +* 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 b<sub>i</sub>, còn bạn thứ hai đưa ra số hạng + c<sub>j</sub> thì giá của lượt chơi đó sẽ là |b<sub>i</sub> + c<sub>j</sub>|. + +### 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 b<sub>1</sub>, b<sub>2</sub>, …, + b<sub>n</sub>. +* Dòng thứ ba chứa dãy số nguyên c<sub>1</sub>, c<sub>2</sub>, …, + c<sub>n</sub>. + +### 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 ≤ 10<sup>5</sup>. +* |b<sub>i</sub>|, |c<sub>j</sub>| < 2<sup>63</sup> ∀ 1 ≤ i, j ≤ n. + +### Ví dụ + +| GAME.INP | GAME.OUT | +| ---------------- | :------: | +| 2<br>1 -2<br>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à [a<sub>i</sub>, @@ -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 ≤ 10<sup>5</sup>; |x| ≤ c ≤ - 10<sup>9</sup>). +* 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 a<sub>i</sub>, - b<sub>i</sub> (1 ≤ i ≤ N; |a<sub>i</sub>|, |b<sub>i</sub>| ≤ c). + b<sub>i</sub>. ### 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 ≤ 10<sup>5</sup>. +* |x| ≤ c ≤ 10<sup>9</sup>. +* |a<sub>i</sub>|, |b<sub>i</sub>| ≤ 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 m<sup>k</sup>. ### Dữ liệu -Tệp `FDP.INP` gồm một dòng ghi hai số nguyên dương n và m (n ≤ 10<sup>18</sup>; -2 ≤ m ≤ 10<sup>12</sup>). +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 ≤ 10<sup>18</sup>. +* 2 ≤ m ≤ 10<sup>12</sup>. + ### 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 <stdio.h> +#include <stdlib.h> +#include <string.h> + +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. |