Editorial for Bedao Mini Contest 08 - BOILEGG
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Nhận xét
- Số lần lật quả trứng thứ ~n~ sẽ bằng số ước của ~n~
- Vì trạng thái ban đầu của quả trứng là ngửa, nên nếu số lần lật là lẻ, quả trứng sẽ ở trạng thái úp xuống. Ngược lại, quả trứng sẽ ở trạng thái ngửa.
- Chỉ các số chính phương mới có số ước là số lẻ. Các số không phải số chính phương có số ước là số chẵn.
Cách làm
- Subtask 1: Vì ~n~ khá nhỏ nên ta sinh một mảng ~a[n]~ có các giá trị ban đầu bằng 0. Với các giá trị từ ~1~ đến ~n~, phần tử nào trong mảng chia hết cho ~n~ thì biến đổi phần tử đó. Độ phức tạp ~\mathcal{O}(n^2)~
- Subtask 2: Dùng 1 vòng
for
để đếm số ước của ~n~. Nếu số ước là số chẵn thì quả trứng thứ ~n~ sẽ ở trạng thái ngửa và ngược lại. Độ phức tạp: ~\mathcal{O}(\sqrt{n})~ - Subtask 3: Chúng ta sẽ cải tiến subtask 2. Xét ~n~ có phải số chính phương hay không. Nếu ~n~ là số chính phương thì quả trứng thứ ~n~ sẽ ở trạng thái ngửa và ngược lại. Độ phức tạp: ~\mathcal{O}(1)~
Comments