Omenat |
| Time limit: | 2.00 s |
| Memory limit: | 128 MB |
|
Aikaraja: 2 s
Maahan on pudonnut omenoita, ja Uolevi aikoo poimia niitä. Tiedät jokaisesta omenasta, kuinka painava se on.
Uolevi haluaa saada mahdollisimman monta omenaa, mutta hänellä on yksi lisäehto: omenoiden yhteispaino tulee olla 3:lla jaollinen.
Tehtäväsi on laskea, kuinka monta omenaa Uolevi voi poimia.
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku $n$: omenoiden määrä.
Seuraavalla rivillä on $n$ kokonaislukua $p_1,p_2,\ldots,p_n$: kunkin omenan paino.
Tuloste
Ohjelmasi tulee tulostaa yksi kokonaisluku: montako omenaa Uolevi pystyy poimimaan enintään.
Esimerkki
Syöte:
5
6 7 6 2 1
Tuloste:
4
Selitys: Yksi ratkaisu on, että Uolevi poimii kaikki omenat paitsi 7:n painoisen. Niiden yhteispaino on 15, joka on 3:lla jaollinen.
Osatehtävä 1 (17 pistettä)
- $1 \le n \le 20$
- $1 \le p_k \le 100$
Osatehtävä 2 (30 pistettä)
- $1 \le n \le 100$
- $1 \le p_k \le 100$
Osatehtävä 3 (53 pistettä)
- $1 \le n \le 10^5$
- $1 \le p_k \le 10^9$
