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/other/README.md | 147 ++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 140 insertions(+), 7 deletions(-) (limited to 'others/other/README.md') 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`. -- cgit 1.4.1