BÀI TẬP Ở NHÀ

https://www.baitaponha.com

Xóa số | Đề HSG Tin 12 Nghệ An | Năm 2013-2014

Đây là một bài thi khá hay, học sinh rất dễ bị mắc lừa khi suy nghĩ rằng có thể tính tổng cả dãy, rồi duyệt tìm 2 số sao cho tổng dãy trừ đi tổng hai số là số chắn. Tuy nhiên làm như vậy thuât không tối ưu, sẽ khó chạy hết test và nếu làm như vậy thì độ phức tạp của thuật toán là O(N2). Bài này để tối ưu thuật toán, ta sử dụng kiến thức toán nhiều hơn và độ phức tạp của thuật toàn còn là O(N). 
Xóa số

Đề ra

Bài 3. (5 điểm) XÓA SỐ.
            Cho dãy số nguyên không âm a1, ...., an. Người ta muốn chọn 2 chỉ số i, j sao cho 1< i < j <N và xóa khỏi dãy 2 số ai, aj để tổng giá trị các số còn lại trong dãy là số chẵn.
Yêu cầu: Hãy đếm số lượng cách chọn 2 chỉ số i, j thỏa mãn. Hai cách chọn khác nhau nếu tồn tại một chỉ số khác nhau.
Dữ liệu: Vào từ file văn bản XOASO.INP
- Dòng 1 chứa số nguyên dương N ( N < 106).
- Dòng 2 chứa n số nguyên không âm a1, ..., an (ai < 103)
Kết quả: Ghi ra file văn bản XOASO.OUT
- Chỉ một dòng duy nhất chứa một số nguyên là số cách chọn 2 chỉ số thỏa mãn.
Ví dụ:

XOASO.INP XOASO.OUT
5
1 2 3 4 5		 6

Lưu ý: Có 50% số test có n < 1000.
 Giải thích test ví dụ: có 6 cách chọn 2 chỉ số i, j là:
            i =1; j = 2   tổng còn lại a3 + a4 + a5 = 3 + 4 + 5= 12 là số chẵn
Tương tự: i=1; j = 4 và i=2; j = 3; và  i=2; j=5 và i=3; j = 4 và i=4; j=5.

Hướng dẫn giải bằng pascal

- le     : là biến chứa số phần tử lẻ của dãy.
- chan: là biến chứa số phần tử chẵn của dãy.
Nhận xét:
- Nếu biến le là một số lẻ thì mỗi cách xóa cần xóa một phần tử chẵn và một phần tử lẻ thì ta sẽ thu được tổng các phần tử còn lại là một số chẵn. Khi đó số cách xóa sẽ là: le*chan.
- Nếu biến le là một số chẵn thì mỗi cách xóa cần xóa cả 2 phần tử lẻ hoặc cả 2 phần tử chẵn thì tổng các phần tử còn lại sẽ là một số chẵn. Khi đó số cách xóa sẽ là: (le*(le-1) div 2 + chan*(chan-1) div 2)

 

Code mẫu bằng Pascal

Code mẫu Pascal và các test đã có ở link tải file dưới bài viết, các bạn tải về tham khảo nhé.

 

Code giải bằng Python

with open('XOASO.INP', 'r') as f_in:
    n = int(f_in.readline())
    a = list(map(int, f_in.readline().split()))

chan = sum(1 for x in a if x % 2 == 0)
le = n - chan

if le % 2 == 0: # Nếu số các số lẻ là chẵn
    cach_chon = (le*(le-1))//2 + (chan*(chan-1))//2
else:
    cach_chon = le*chan

with open('XOASO.OUT', 'w') as f_out:
    f_out.write(str(cach_chon))


 


 

Tác giả: admin

Bạn đã không sử dụng Site, Bấm vào đây để duy trì trạng thái đăng nhập. Thời gian chờ: 60 giây