Contest này tính rating, mình không ngờ là tính rating nên solve xong 2 bài + 1 task bài 3 mãn nguyện đi ngủ, tỉnh dậy tụt 23 điểm raitng chui ngược xuống 2* :(
Mà thôi, solution đây:
Bài này chỉ là tìm phần tử max của một dãy N phần tử cho trước.
Bài này yêu cầu đếm số cặp trong N số cho trước. Dễ ăn được 60 điểm bằng 2 vòng lặp, nhưng đến test 3 N quá lớn nên phải có cách tiếp cận khác. Phương pháp tiếp cận này lại thuần về toán, đòi hỏi chút kiến thức đại số và xác suất thống kê:
Giả sử ta có 2 số a và b là 2 số nguyên dương, 1 <= a, b <= 1000000 theo yêu cầu của đề bài, x, y là số nguyên dương >= 1 tùy ý:
- Nếu a có dạng 2x (a là số chẵn) và b có dạng 2y + 1 (b là số lẻ), khi đó a + b = 2x + 2y + 1 = 2(x + y) + 1 => kết quả a + b là một số nguyên lẻ. Kết quả tương tự với b là số chẵn và a là số lẻ, vì phép cộng có tính giao hoán.
- Nếu a có dạng 2x (a là số chẵn) và b có dạng 2y (b cũng là số chẵn), khi đó a + b = 2x + 2y = 2(x + y) => kết quả a + b là một số nguyên chẵn.
- Nếu a có dạng 2x + 1 (a là số lẻ) và b có dạng 2y + 1 (b cũng là số lẻ), khi đó a + b = 2x + 1 + 2y + 1 = 2(x + y + 1) => kết quả a + b là một số nguyên chẵn.
Từ đó ta có thể kết luận, một cặp số phù hợp với yêu cầu đề bài là một cặp số gồm 1 số chẵn và 1 số lẻ. Trong dãy N số cho trước ở đề bài, giả sử ta có a số chẵn và b số lẻ. Khi đó, tổng số cặp 1 chẵn 1 lẻ có thể tạo thành là a * b cặp.
Vậy, để AC được task cuối: đếm trong số N số có bao nhiêu số chẵn và bao nhiêu số lẻ, nhân lại sẽ ra kết quả.
(Chú ý phải để kiểu dữ liệu long trong C mới đủ cho test bài này).
Happy coding!
No comments:
Post a Comment