Nội dung Bài tập
- Mã:
- MaximumSplitting
- Tên:
- Phân chia tối đa
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- 4901104009
Bạn được đưa một số truy vấn. Trong truy vấn thứ i, bạn được đưa ra một số nguyên dương ni duy nhất. Bạn phải biểu diễn ni dưới dạng tổng của số lượng lớn nhất có thể có của các tổng hợp và in ra số lớn nhất này hoặc in ra -1 nếu không có phép chia nào như vậy.
Một số nguyên lớn hơn 1 là hợp số nếu nó không phải là số nguyên tố, tức là nếu nó có các ước số dương không bằng 1 và chính là số nguyên đó.
Input
- Dòng đầu tiên chứa một số nguyên q (1 ≤ q ≤ 105) — số lượng truy vấn.
- q dòng tiếp theo. Dòng thứ (i + 1) chứa một số nguyên ni (1 ≤ ni ≤ 109) — truy vấn thứ i.
Output
- Đối với mỗi truy vấn, hãy in ra số lượng tổng hợp tối đa có thể có trong phép chia hợp lệ thành tổng hợp, hoặc -1, nếu không có phép chia nào như vậy (chia thành nhiều hợp số nhất có thể).
Ví dụ 1 :
Input
Output
1
12
3
Ví dụ 2 :
Input
Output
2
6
8
1
2
Ví dụ 3 :
Input
Output
3
1
2
3
-1
-1
-1
Giải thích :
12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12, nhưng phép chia đầu tiên có số lượng tổng hợp tối đa có thể.
8 = 4 + 4, 6 không thể chia thành nhiều tổng hợp.
1, 2, 3 nhỏ hơn bất kỳ số hợp nào, vì vậy chúng không có phép chia hợp lệ.
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
Luyện tập LTNC cuối tuần