---
# System prepended metadata

title: ÔN LUYỆN THI QUỐC GIA - SỐ 1

---

# ÔN LUYỆN THI QUỐC GIA - SỐ 1
Thời gian làm bài: 200 phút

---
## Bài 1. BOOMERANG
:::info
:::spoiler Thông số bài tập
Tác giả: **leduclv**
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1024MB
Điểm: 300
:::
Boomerang là công cụ đi săn bằng đá hoặc gỗ của thổ sân Úc. Nếu ném một cách thích hợp, boomerang sẽ bay tới đích rồi lượn về tay người ném. Để đáp ứng nhu cầu thể thao, rèn luyện kỹ năng sử dụng boomerang, một công ty quyết định chế tạo boomerang bằng nhựa. Mỗi khi được ném một lực nào đó về phía trước, boomerang sẽ bay theo một quỹ đạo nhất định và không nhất thiết quay về vị trí ban đầu. Theo thiết kế, mỗi boomerang được gắn với một xâu $S$ không quá $250$ ký tự chỉ bao gồm $2$ ký tự `F`,`R`. Quỹ đạo bay của mỗi cách ném boomerang dọc theo đường thẳng đều có thể mô tả được bởi một xâu ký tự nhận được bằng cách xóa bớt một số ký tự của xâu $S$ gắn với nó, trong đó mỗi ký tự cho biết boomerang bay qua một khoảng độ dài $1$ về hướng nào:
- `F` - boomerang bay về phía trước;
- `R` - boomerang bay ngược trở lại.

Một cách ném boomerang dọc theo đường thẳng được gọi là an toàn nếu thỏa mãn 2 điều kiện:
- Điều kiện boomerang: vị trí ban đầu và kết thúc của quỹ đạo bay là trùng nhau.
- Điều kiện an toàn: Nếu vị trí ban đầu xuất hiện trên quỹ đạo bay và quá trình bay còn chưa kết thúc thì hướng bay phải là `F`.

Hai cách ném được gọi là khác nhau nếu 2 xâu mô tả quỹ đạo bay của chúng là khác nhau. Với mỗi boomerang, có thể có nhiều cách ném an toàn khác nhau. Ví dụ với $S =$ `FFFRRRRRF` ta có 3 cách ném an toàn, `FR`, `FFRR`, `FFFRRR`.
Lưu ý là trong quỹ đạo bay của boomerang vị trí ban đầu có thể xuất hiện nhiều lần.
**Yêu cầu:** Cho xâu $S$, hãy xác định số cách ném an toàn khác nhau có thể thực hiện.
**Dữ liệu**: Xâu $S$.
**Kết quả:** Một số nguyên là số lượng cách nèm an toàn có thể thực hiện.
**Sample Input:**
```
FFFRRRRRF
```
**Sample Output:**
```
3
```
---
## Bài 2. DISTSUM
:::info
:::spoiler Thông số bài tập
Tác giả: **leduclv**
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256MB
Điểm: 300
:::
Cho $N$ điểm trên mặt phẳng tọa độ $Oxy$, điểm thứ $i$ có tọa độ $(x_i,y_i)$. Ta định nghĩa khoảng cách Manhattan giữa hai điểm $i$ và $j$ là $|x_i - x_j| + |y_i - y_j|$. Hãy tính tổng khoảng cách Manhattan giữa tất cả mọi cặp điểm.
**Dữ liệu:**
- Dòng đầu tiên ghi số nguyên dương $N$ không quá $10^5$ - số lượng điểm.
- $N$ dòng tiếp theo, dòng thứ $i$ gồm hai số nguyên $x_i$ và $y_i$ $(−10^8 ≤ x_i, y_i ≤ 10^8)$ - tọa độ của điểm thứ $i$.

**Kết quả:**
- In ra tổng Manhattan cần tìm.

![](https://i.imgur.com/OqntZ7D.png)

---
## Bài 3. BINARY
:::info
:::spoiler
Tác giả: **leduclv**
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256MB
Điểm: 300
:::
Cho một dãy nhị phân $a$ gồm $N$ bit và một dãy nhị phân $b$ gồm $M$ bit. Bạn phải tính giá trị của biểu thức:
![](https://i.imgur.com/l2HMnkL.png)
**Dữ liệu:**
- Dòng đầu ghi $2$ số $N$ và $M$ không quá $100000$.
- Dòng hai gồm $N$ phần tử của dãy $a$, mỗi số có giá trị $0$ hoặc $1$, phân cách với nhau bởi dấu cách.
- Dòng cuối gồm $M$ phần tử của dãy $b$, mỗi số có giá trị $0$ hoặc $1$, phân cách với nhau bởi dấu cách.

**Kết quả:**
- In ra giá trị của biểu thức cần tính.

**Sample Input**
```
10 6
1 1 0 1 0 0 0 1 0 1
0 0 1 1 0 1
```
**Sample Output**
```
2
```