Thi thử 08 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Phương trình (HSG9-2015, Hà Nội)	100 (p)	1.0s	256M
2	Chia nhóm (HSG9-2015, Hà Nội)	100 (p)	1.0s	256M
3	Tạo số (HSG9-2015, Hà Nội)	100 (p)	1.0s	256M
4	Bảng số (HSG9-2015, Hà Nội)	100 (p)	1.0s	256M

1. Phương trình (HSG9-2015, Hà Nội)

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: CAU1.inp Output: CAU1.out

Cho phương trình \(ax + by = c\), với \(a, b, c\) là các số nguyên dương.

Yêu cầu: Tìm số lượng cặp \((x, y)\), với \(x, y\) nguyên dương, là nghiệm của phương trình.

Input

Gồm một dòng duy nhất chứa ba số nguyên dương \(a, b, c\), mỗi số không vượt quá \(10^9\).

Output

In số lượng các cặp nghiệm nguyên dương \((x, y)\) của phương trình.

Example

Test 1

Input

2 4 20

Output

Note

Các cặp nghiệm nguyên dương của phương trình \(2x + 4y = 20\) là: \((2, 4)\), \((4, 3)\), \((6, 2)\), \((8, 1)\).

2. Chia nhóm (HSG9-2015, Hà Nội)

Điểm: 100 (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\) \((n \leq 10^{3})\) và \(h\) \((h \leq 10^{9})\).
Trong \(n\) dòng tiếp theo, dòng thứ \(i\) \((1 \leq i \leq n)\) chứa số nguyên \(a_i\) có giá trị tuyệt đối không vượt quá \(10^{9}\).

Output

In ra số lượng nhóm ít nhất tìm được.

Example

Test 1

Input

Output

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ố (HSG9-2015, Hà Nội)

Điểm: 100 (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 = p_1 \times p_2 \times \ldots \times p_k\), trong đó \(p_i\) \((1 \leq i \leq 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

Gồm 1 dòng duy nhất chứa số nguyên dương \(t\) không vượt quá \(10^{9}\).

Output

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

Example

Test 1

Input

Output

Note

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

4. Bảng số (HSG9-2015, Hà Nội)

Điểm: 100 (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\).