[TFL x Tân Khoa] Contest #2 "Ôn thi Tuyển sinh 10" (TS10 Chuyên Tin 2025)

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Đếm cặp 25 (p) 1.0s 512M
2 "Số năm" 25 (p) 1.0s 512M
3 Deque 25 (p) 1.0s 1G
4 Bồ câu 25 (p) 1.0s 1G

1. Đếm cặp

Điểm: 25 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: DCAP.INP Output: DCAP.OUT

Cho \(n\) điểm trên mặt phẳng tọa độ \(Oxy\). Lấy hai điểm bất kỳ trong số \(n\) điểm này (tạm gọi là \(A\) và \(B\)), ta cần biết liệu trung điểm của đoạn thẳng \(AB\) có phải là một điểm nguyên hay không. Nếu xét tất cả cặp điểm, có bao nhiêu trung điểm như thế?

Nhắc lại, điểm \((x, y)\) là điểm nguyên nếu cả hoành độ \(x\) và tung độ \(y\) đều là số nguyên.

Yêu cầu: Đếm trong \(n\) điểm cho trước, có bao nhiêu cặp tạo ra một đoạn thẳng có trung điểm là điểm nguyên.

Input

  • Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \leq 10^5\)).
  • Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa hai số nguyên \(x_i, y_i\) (\(|x_i|, |y_i| \leq 10^8\)).
  • Dữ liệu vào đảm bảo không có hai điểm nào có cùng tọa độ.

Output

  • Dòng duy nhất chứa một số nguyên dương – kết quả bài toán – số lượng cặp đếm được.

Example

Test 1

Input 
3
0 0
1 1
2 2
Output 
1
Note
  • Cặp điểm \((0, 0)\) và \((1, 1)\) có trung điểm \((0.5, 0.5)\)
  • Cặp điểm \((0, 0)\) và \((2, 2)\) có trung điểm \((1, 1)\)
  • Cặp điểm \((1, 1)\) và \((2, 2)\) có trung điểm \((1.5, 1.5)\)

Trong các trung điểm được tạo ra, chỉ có 1 điểm \((1, 1)\) là điểm nguyên.

Scoring

  • 25% số điểm tương ứng với \(n = 2\).
  • 25% số điểm khác tương ứng với \(n \leq 10^3\).
  • 25% số điểm khác tương ứng với \(n \leq 10^5\) và tất cả các điểm cùng nằm trên một đường thẳng; đường thẳng này song song với một trong hai trục tọa độ.
  • 25% số điểm còn lại không có ràng buộc gì thêm.

2. "Số năm"

Điểm: 25 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: FIVE.INP Output: FIVE.OUT

Số năm (5) được cho là một số đẹp. Số chẵn chia hết cho 5 là số tròn chục. Số 5 xuất hiện trong trò chơi thời thơ ấu "năm, mười, mười lăm, hai mươi, …". Một số nguyên dương \(x\) được gọi là "số năm" nếu tồn tại đúng năm số nguyên dương \(y\) khác nhau mà \(x\) là bội của \(y\).

Yêu cầu: Cho số nguyên dương \(n\). Hãy đếm số lượng "số năm" từ 1 đến \(n\).

Input

  • Gồm một dòng duy nhất chứa số nguyên dương \(n\) \((n \leq 10^{18})\).

Output

  • Dòng duy nhất chứa một số nguyên dương là kết quả của bài toán – số lượng "số năm" từ 1 đến \(n\).

Example

Test 1

Input 
10
Output 
0

Test 2

Input 
20
Output 
1
Note

Đếm được số 16 là một số thỏa mãn, vì 16 là bội của năm số sau: 1, 2, 4, 8, 16.

Scoring

  • 30% số điểm tương ứng với \(n \leq 10^3\).
  • 40% số điểm khác tương ứng với \(n \leq 2 \times 10^6\).
  • 30% số điểm còn lại không có ràng buộc gì thêm.

3. Deque

Điểm: 25 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: DEQUE.INP Output: DEQUE.OUT

Đề bài nằm ở trong bài 1 - intmid.

Tham gia vào kỳ thi ôn tập TS10 2025 - Contest #2 để đọc đề.

4. Bồ câu

Điểm: 25 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: PIGEON.INP Output: PIGEON.OUT

Lưu ý: Số dư của bài này là \(\text{MOD} = 1\mathrm{e}{18}\)

Đề bài nằm ở trong bài 1 - intmid.

Tham gia vào kỳ thi ôn tập TS10 2025 - Contest #2 để đọc đề.