USACO 2021 - Even More Odd Photos
Xem PDFFarmer John lại đang cố chụp ảnh \(N\) con bò của mình (\(2\le N\le 1000\)).
Mỗi con bò có một số nguyên "mã giống" trong đoạn \(1\ldots100\). Farmer John có một ý tưởng rất đặc biệt cho bức ảnh: ông muốn chia tất cả các con bò thành những nhóm rời nhau, tức mỗi con thuộc đúng một nhóm, rồi xếp các nhóm sao cho tổng mã giống của các con trong nhóm đầu tiên là số chẵn, tổng trong nhóm thứ hai là số lẻ, và cứ thế xen kẽ chẵn, lẻ.
Số nhóm lớn nhất Farmer John có thể tạo là bao nhiêu?
Dữ liệu vào
Dòng đầu tiên chứa \(N\). Dòng tiếp theo chứa \(N\) số nguyên, cách nhau bởi dấu cách, là mã giống của \(N\) con bò.
Dữ liệu ra
In số nhóm lớn nhất có thể có trong bức ảnh của Farmer John. Có thể chứng minh rằng luôn tồn tại ít nhất một cách chia hợp lệ.
Phân nhóm
Tất cả các test tuân theo các ràng buộc đã nêu.
Ví dụ
Ví dụ 1
Input
7
1 3 5 7 9 11 13Output
3Giải thích
Một cách tạo số lượng tối đa là ba nhóm: đặt \(1\) và \(3\) vào nhóm đầu tiên; \(5\), \(7\) và \(9\) vào nhóm thứ hai; \(11\) và \(13\) vào nhóm thứ ba.
Ví dụ 2
Input
7
11 2 17 13 1 15 3Output
5Giải thích
Một cách tạo số lượng tối đa là năm nhóm: đặt \(2\) vào nhóm đầu tiên; \(11\) vào nhóm thứ hai; \(13\) và \(1\) vào nhóm thứ ba; \(15\) vào nhóm thứ tư; \(17\) và \(3\) vào nhóm thứ năm.
Nguồn
USACO 2021 January Contest, Bronze - Even More Odd Photos: https://usaco.org/index.php?page=viewproblem2&cpid=1084
Tác giả: Nick Wu.
Kỳ thi:
- USACO 2021 - Tháng 1 - Hạng Đồng (1 Tháng 1., 2021)
Bình luận