# 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.
### Giới hạn
n ≤ 1018.
### Ví dụ
| BIN.INP | BIN.OUT |
| :-----: | :-----: |
| 109 | 1101101 |
## DiffSum
Lập chương trình phân tích số nguyên dương n thành tổng của các số nguyên dương
khác nhau sao cho tích của các số hạng này là lớn nhất có thể.
### Dữ liệu
Tệp `DIFFSUM.INP` gồm một dòng duy nhất ghi số n.
### Kết quả
Tệp `DIFFSUM.OUT` ghi các số hạng của cách phân tích tìm được theo thứ tự tăng
dần trên một dòng.
### Giới hạn
n ≤ 105.
### Ví dụ
| DIFFSUM.INP | DIFFSUM.OUT |
| :---------: | :---------: |
| 5 | 2 3 |
| 10 | 2 3 5 |
## Tìm dãy số nguyên liên tiếp
Cho dãy gồm n số tự nhiên đôi một khác nhau a1, a2, …,
an. Nếu trong dãy đã cho có chứa số 0, bạn được phép thay số 0 bằng
một số nguyên dương bất kì khác.
### Yêu cầu
Hãy chọn trong dãy gồm nhiều nhất các số sao cho các số đã chọn tạo thành một
dãy số tự nhiên liên tiếp.
### Dữ liệu
Tệp `LSEQ.INP`:
* Dòng thứ nhất chứa số nguyên dương n.
* Dòng thứ hai dãy số tự nhiên a1, a2, …, an.
### Kết quả
Tệp `LSEQ.OUT` gồm một dòng duy nhất ghi độ dài lớn nhất của dãy số tự nhiên
liên tiếp chọn được.
### Giới hạn
* n ≤ 106.
* ai ≤ 106 ∀ 1 ≤ i ≤ n.
### Ví dụ
| LSEQ.INP | LSEQ.OUT | Giải thích |
| ------------------ | :------: | ------------------------------------ |
| 5
2 9 3 7 4 | 3 | Chọn dãy 2, 3, 4 |
| 7
1 2 4 7 6 0 8 | 5 | Thay 0 bởi 5, chọn dãy 4, 5, 6, 7, 8 |
## 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,
bi].
### Yêu cầu
Cho một điểm M với toạ độ x. Hãy cho biết M thuộc bao nhiêu đoạn thẳng đã cho ở
trên, và cụ thể là những đoạn nào? Nếu M không thuộc đoạn nào trong các đoạn đã
cho, hãy chỉ ra 1 đoạn dài nhất chứa điểm M và không có điểm trong chung với
bất kì đoạn nào trong N đoạn đã cho (không có điểm chung ngoài hai điểm đầu
mút).
### Dữ liệu
Tệp `INTERVAL.INP`:
* 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.
### Kết quả
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:
* Nếu K dương, ghi K số là số thứ tự của K đoạn chứa M.
* 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 |
| ----------------------------------- | ------------ |
| 4 20 2
1 3
2 4
7 10
0 1 | 2
1 2 |
| 3 10 5
1 2
-4 4
6 9 | 0
4 6 |
## Phân tích số
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.
### 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 |
## Vòng xoắn số nguyên
Cho số nguyên dương n. Viết các số từ 1 đến n theo hình xoắn trôn ốc chữ nhật
nằm ngang vuông nhất có thể.
### Dữ liệu
Tệp `SPIRAL.INP` gồm một dòng duy nhất ghi số nguyên dương n.
### Kết quả
Tệp `SPIRAL.OUT` ghi vòng xoắn trôn ốc.
### Giới hạn
n ≤ 106.
### Ví dụ
| SPIRAL.INP | SPIRAL.OUT |
| ---------- | -------------------------------- |
| 12 | 1 2 3 4
10 11 12 5
9 8 7 6 |
## 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`.
## Hình chữ nhật
Cho tọa độ 3 điểm trên mặt phẳng, tìm 1 điểm còn lại để 4 điểm tạo thành 1 hình
chữ nhật.
### Dữ liệu
Gồm 3 dòng, mỗi dòng gồm 2 số nguyên x, y (-100 ≤ x, y ≤ 100) là là toạ độ của
1 điểm.
### Kết quả
2 số nguyên là toạ độ hai điểm còn lại của hình chữ nhật.
### Ví dụ
| hcn.inp | hcn.out |
| :---------------: | :-----: |
| 2 1
2 4
3 1 | 3 4 |
| 2 5
5 1
1 3 | 6 3 |
## Lấy bi
Cho 3 lọ đựng bi, mỗi lọ đựng 1 số viên bi. Có quy tắc lấy bi là: lấy ở 2 lọ
bất kì, mỗi lọ 1 viên bi, và cho vào lọ còn lại. Hỏi cách lấy bi nào sao cho
tất cả bi đều ở trong 1 lọ, 2 lọ còn lại không có viên bi nào.
### Dữ liệu
1 dòng duy nhất gồm 3 số a, b, c (0 ≤ a, b, c ≤ 109).
### Kết quả
`YES` nếu có cách chuyển bi để tất cả bi đều ở trong 1 lọ, nếu không `NO`.
### Ví dụ
| laybi.inp | laybi.out |
| :-------: | :-------: |
| 2 3 3 | YES |
| 2 4 6 | NO |
## Biến đổi số
Cho 2 số nguyên x, y và 2 phép biến đổi là phép tăng lên a đơn vị b đơn vị. Hỏi
có thể biến đổi x thành y được không?
### Dữ liệu
1 dòng duy nhất gồm 4 số x, y, a, b (0 ≤ x < y ≤ 2x109; 0 ≤ a, b ≤
109).
### Kết quả
1 số duy nhất là số phép biến đổi ít nhất để x thành y. Nếu không biến đổi
được thì in ra `-1`.
| biendoiso.inp | biendoiso.inp |
| :-----------: | :-----------: |
| 3 20 2 3 | 6 |
| 5 30 6 4 | -1 |
## Số cách đi của thỏ
Một con thỏ cần băng qua một đoạn đường dài n mét, thỏ có ba cách nhảy với các
độ dài bước nhảy là 3 mét, 2 mét, 1 mét. Một cách đi đúng của thỏ là dãy các
bước nhảy của nó có tổng độ dài bằng n và bước nhảy liền sau không dài hơn bước
nhảy liền trước trong dãy bước nhảy của nó.
### Yêu cầu
Cho biết số nguyên dương n, hãy tính số cách đi đúng khác nhau của thỏ để đi
hết đoạn đường n mét. Số cách đi có thể rất lớn nên kết quả in ra được viết
dưới dạng số dư của phép chia kết quả cho 1000000.
### Dữ liệu
Gồm một dòng chứa số nguyên n.
### Kết quả
In ra số nguyên duy nhất là số cách đi đúng của thỏ viết dưới dạng số dư của
kết quả chia cho 1000000.
### Hạn chế
* 40% test đầu tiên có n ≤ 1000.
* 30% test tiếp theo có 1000 < n ≤ 109.
* 30% test cuối cùng có 109 < n ≤ 1015.
### Ví dụ
| bunny.inp | bunny.out |
| :-------: | :-------: |
| 6 | 7 |
#### Giải thích
Với n = 6, thỏ có 7 cách đi như sau: 3+3, 3+2+1, 3+1+1+1, 2+2+2, 2+2+1+1,
2+1+1+1+1, 1+1+1+1+1+1.
## Biểu thức nhân, cộng
Cho n số nguyên dương ai, i=1..n. Bạn phải đặt giữa n số này 2 phép
nhân và n - 3 phép cộng sao cho kết quả biểu thức là lớn nhất.
Chú ý: Không được thay đổi thứ tự xuất hiện các số nguyên dương của trong biểu
thức thu được.
### Dữ liệu
* Dòng 1 chứa số nguyên dương n (4 ≤ n ≤ 1000).
* n dòng tiếp theo, dòng thứ i + 1 chứa số nguyên dương ai ≤ 10000.
### Kết quả
Số nguyên dương lớn nhất là giá trị biểu thức thu được.
### Ví dụ
| express.inp | express.out | Giải thích |
| -------------- | :---------: | ----------------- |
| 5
4 7 1 5 3 | 44 | 4 * 7 + 1 + 5 * 3 |
## Ước số
Cho đoạn [a; b] \(a, b là số nguyên dương), tính các giá trị:
* min: Số nhỏ nhất và có nhiều ước số nhất trong đoạn này.
* cmin: Số lượng ước của min.
* count: Số lượng số trong đoạn có số ước là cmin.
### Dữ liệu
Hai số nguyên dương a và b (a ≤ b ≤ 109; b - a ≤ 10000).
### Kết quả
Ba số nguyên dương theo thứ tự min, cmin, count
### Ví dụ
| uocso.inp | uocso.out |
| --------- | --------- |
| 2 10 | 6 4 3 |
| 200 200 | 200 12 1 |