HSG THCS Hà Nội 2015

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Phương trình Diophantine 6 (p) 1.0s 256M
2 Chia nhóm 5 (p) 1.0s 256M
3 Tạo số 5 (p) 1.0s 256M
4 Bảng số 4 (p) 1.0s 256M

1. Phương trình Diophantine

Điểm: 6 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho ba số nguyên dương \(a, b, c\). Xét phương trình: \(a.x + b.y = c\). Hãy tìm số lượng cặp (\(x, y\)) là nghiệm của phương trình trên, với \(x, y\) là hai số nguyên dương.

Input

  • Gồm một dòng chứa ba số nguyên dương \(a, b, c \le 10^9\) cách nhau bởi dấu cách.

Output

  • Ghi ra một số nguyên duy nhất là số cặp nghiệm nguyên dương của phương trình.

Example

Test 1

Input 
2 4 20
Output 
4
Note

Giải thích: Trong ví dụ trên, 4 cặp nghiệm là \((2, 4), (4, 3), (6, 2)\) và \((8, 1)\).

2. Chia nhóm

Điểm: 5 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: CAU2.INP Output: CAU2.OUT

Cho \(n\) số nguyên \(a_1, a_2, \ldots, a_n\). Người ta muốn chia \(n\) số nguyên này thành các nhóm, trong mỗi nhóm hiệu của số lớn nhất và số nhỏ nhất không vượt quá số nguyên dương \(h\) cho trước.
Yêu cầu: Xác định số lượng nhóm ít nhất khi chia nhóm \(n\) số nguyên đã cho thỏa mãn điều kiện trên.

Input

  • Dòng đầu chứa hai số nguyên dương \(n\) và \(h\), \(n \leq 10^{3}\), \(h \leq 10^{9}\).
  • Trong \(n\) dòng tiếp theo, dòng thứ i (1 ≤ i ≤ \(n\)) chứa số nguyên \(a_i\) có giá trị tuyệt đối không vượt quá \(10^{9}\).

Output

  • Số lượng nhóm ít nhất tìm được.

Example

Test 1

Input 
6 3
-7
27
-5
26
28
-6
Output 
2
Note

Có thể chia 6 số đã cho thành hai nhóm. Nhóm thứ nhất gồm các số thứ 1, thứ 3, thứ 6 và nhóm thứ hai là các số còn lại. Hai nhóm này đều có hiệu của số lớn nhất và số nhỏ nhất là 2, nhỏ hơn 3.

3. Tạo số

Điểm: 5 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: CAU3.INP Output: CAU3.OUT

Cho trước số nguyên dương \(t\). Người ta tạo một số nguyên dương \(x\) bằng cách sau: Trước hết, biểu diễn số \(t\) dưới dạng \(t = p_1 \cdot p_2 \cdot \ldots \cdot p_k\), trong đó \(p_i\) \((1 ≤ i ≤ k)\) là các số nguyên tố (\(k\) có thể bằng 1); tiếp theo viết các số \(p_1, p_2, \ldots, p_k\) theo một thứ tự nào đó liên tiếp nhau để nhận được số nguyên dương \(x\).
Yêu cầu: Tìm giá trị lớn nhất của \(x\).

Input

  • Chứa một số nguyên dương \(t\), không vượt quá \(10^9\).

Output

  • Giá trị \(x\) lớn nhất tìm được.

Example

Test 1

Input 
476
Output 
72217
Note

Có 476 = 2 · 2 · 7 · 17 nên số \(x\) lớn nhất là 72217.

4. Bảng số

Điểm: 4 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: CAU4.INP Output: CAU4.OUT

Cho trước bảng số A gồm \(m\) hàng, \(n\) cột. Mỗi ô trong bảng số chứa một số nguyên dương gọi là giá trị của ô. Tất cả các ô (ít nhất là 2 ô) có cùng giá trị, kề cạnh hoặc kề đỉnh tạo thành một vùng số. Số lượng ô trong một vùng số gọi là diện tích của vùng số đó.
Yêu cầu: Tính số lượng vùng số có trong bảng A và diện tích của vùng số lớn nhất.

Input

  • Dòng đầu chứa hai số nguyên dương \(m\), \(n\), mỗi số không vượt quá 100;
  • Trong \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên dương, mỗi số không vượt quá 100.

Output

  • Dòng đầu ghi số lượng các vùng số có trong bảng A;
  • Dòng thứ hai ghi diện tích của vùng số lớn nhất.

Example

Test 1

Input 
5 6
1 2 1 4 5 4
1 3 1 4 5 4
3 1 2 3 3 4
2 2 4 5 3 3
2 2 3 2 1 1
Output 
8
5
Note

Có 8 vùng số gồm: 2 vùng số 1; 1 vùng số 2; 2 vùng số 3; 2 vùng số 4; 1 vùng số 5. Trong 8 vùng số trên, diện tích vùng số lớn nhất là 5.