Algorithm

C. Lucky Tickets
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem Link- https://codeforces.com/problemset/problem/43/C
input
standard input
output
standard output

Vasya thinks that lucky tickets are the tickets whose numbers are divisible by 3. He gathered quite a large collection of such tickets but one day his younger brother Leonid was having a sulk and decided to destroy the collection. First he tore every ticket exactly in two, but he didn’t think it was enough and Leonid also threw part of the pieces away. Having seen this, Vasya got terrified but still tried to restore the collection. He chose several piece pairs and glued each pair together so that each pair formed a lucky ticket. The rest of the pieces Vasya threw away reluctantly. Thus, after the gluing of the 2t pieces he ended up with t tickets, each of which was lucky.

When Leonid tore the tickets in two pieces, one piece contained the first several letters of his number and the second piece contained the rest.

Vasya can glue every pair of pieces in any way he likes, but it is important that he gets a lucky ticket in the end. For example, pieces 123 and 99 can be glued in two ways: 12399 and 99123.

What maximum number of tickets could Vasya get after that?

Input

The first line contains integer n (1 ≤ n ≤ 104) — the number of pieces. The second line contains n space-separated numbers ai (1 ≤ ai ≤ 108) — the numbers on the pieces. Vasya can only glue the pieces in pairs. Even if the number of a piece is already lucky, Vasya should glue the piece with some other one for it to count as lucky. Vasya does not have to use all the pieces. The numbers on the pieces an on the resulting tickets may coincide.

Output

Print the single number — the maximum number of lucky tickets that will be able to be restored. Don't forget that every lucky ticket is made of exactly two pieces glued together.

Examples
input
Copy
3
123 123 99
output
Copy
1
input
Copy
6
1 1 1 23 10 3
output
Copy
1



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <cstdio>

int main(){

    long n; scanf("%ld\n", &n);
    long zeros(0), ones(0), twos(0);

    while(n--){
        long t; scanf("%ld", &t);
        if(t % 3 == 0){++zeros;}
        else if(t % 3 == 1){++ones;}
        else if(t % 3 == 2){++twos;}
    }

    long total = (zeros / 2) + (ones < twos ? ones : twos);
    printf("%ld\n", total>;

    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
123 123 99

Output

x
–
+
cmd
1
Advertisements

Demonstration

Codeforces Solution-C. Lucky Tickets-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+