Bảng số
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 1Output
8
5Note
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.
Tạo số
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
476Output
72217Note
Có 476 = 2 · 2 · 7 · 17 nên số \(x\) lớn nhất là 72217.
Chia nhóm
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
-6Output
2Note
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.
Phương trình
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
- 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
- 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 20Output
4Note
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)\).