Xóa dãy số
Đề bài
Mô tả
Cho một dãy gồm số nguyên dương xếp từ trái sang phải. Bạn được thực hiện các thao tác sau:
- Thao tác 1: Nếu hai số đầu tiên của dãy hiện tại nguyên tố cùng nhau, hoặc một trong hai số là bội của số còn lại, xóa cả hai số đó.
- Thao tác 2: Nếu không thể áp dụng Thao tác 1 cho hai số đầu tiên, chọn một số nguyên , tăng số đầu tiên thêm (tức là ) và thêm vào cuối dãy.
Mục tiêu của bạn là làm cho dãy trở thành rỗng (xóa cả các số ban đầu lẫn mọi số được thêm vào) với số thao tác ít nhất.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên : số bộ dữ liệu. Mỗi bộ dữ liệu gồm:
- Dòng đầu tiên chứa số nguyên ().
- Dòng thứ hai chứa số nguyên ().
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một số nguyên: số thao tác ít nhất cần để xóa toàn bộ dãy.
Ràng buộc
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 28 30 1 30 |
4 2 |
Bộ thứ nhất: một cách tối ưu là , dùng thao tác. Bộ thứ hai: . |
| 3 3 6 3 10 4 4 6 9 15 5 2 4 6 9 7 |
3 5 4 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: xóa vì là bội của , còn lại cần thao tác. |
Bình luận