Bedao Regular Contest 22 - Độc lập chính phương
Xem dạng PDF
Gửi bài giải
Điểm:
0,01 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Một dãy ~b~ được định nghĩa là độc lập chính phương nếu như không tồn tại bất kì dãy con khác rỗng nào của ~b~ có tích là một số chính phương.
Cho dãy ~a~ gồm ~n~ phần tử nguyên dương, hãy tìm dãy con dài nhất của ~a~ sao cho nó độc lập chính phương.
Input
Dòng đầu tiên gồm một số nguyên ~n~ (~1 \le n \le 1000~)— độ dài của dãy ~a~.
Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, a_3, \dots ,a_n~ (~1 \le a_i \le 10^4~).
Output
- In ra độ dài của dãy con dài nhất của ~a~ sao cho dãy này độc lập chính phương.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| ~1~ | ~15\%~ | ~n \le 10~ |
| ~2~ | ~15\%~ | ~a_i~ là lũy thừa của 1 số chính phương |
| ~3~ | ~30\%~ | ~a_i \le 75~ |
| ~4~ | ~25\%~ | ~n \le 400, a_i \le 1000~ |
| ~5~ | ~15\%~ | Không có ràng buộc gì thêm |
Sample Input 1
4
5 6 4 30
Sample Output 1
2
Bình luận