레이팅 미적용농부 존은 또다시 자신의 소 \(N\)마리(\(2 \leq N \leq 1000\))의 사진을 찍으려 하고 있다.
각 소에게는 \(1 \ldots 100\) 범위의 정수 "품종 ID" 번호가 있다. 농부 존은 사진에 대해 매우 독특한 생각을 갖고 있다. 그는 모든 소를 서로소인 그룹들로 분할한 다음(다시 말해 각 소를 정확히 하나의 그룹에 넣은 다음), 첫 번째 그룹에 속한 소들의 품종 ID 합이 짝수, 두 번째 그룹의 ID 합이 홀수가 되도록, 즉 짝수와 홀수가 번갈아 나오도록 그룹들을 일렬로 세우고 싶어 한다.
농부 존이 만들 수 있는 그룹의 최대 개수는 얼마인가?
문제 제공: Nick Wu
문제 제공: Nick Wu
첫째 줄에 \(N\)이 주어진다. 다음 줄에 소 \(N\)마리의 품종 ID를 나타내는 공백으로 구분된 \(N\)개의 정수가 주어진다.
농부 존의 사진에서 가능한 그룹의 최대 개수를 출력한다. 가능한 그룹 분할이 적어도 하나 존재함을 보일 수 있다.
7
1 3 5 7 9 11 133In this example, one way to form the maximum number of three groups is as
follows. Place 1 and 3 in the first group, 5, 7, and 9 in the second group, and
11 and 13 in the third group.
7
11 2 17 13 1 15 35In this example, one way to form the maximum number of five groups is as
follows. Place 2 in the first group, 11 in the second group, 13 and 1 in the
third group, 15 in the fourth group, and 17 and 3 in the fifth group.
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > January > Bronze