## Algorithm

Problem Name: 2 AD-HOC - beecrowd | 1090

# Set

By Fábio Dias Moreira Brazil

Timelimit: 1

Set is a game of cards in which each card may have one, two or three figures. All figures in one given card are equal. Figures may be circles, squares or triangles. Each card, therefore, has two characteristics: the number of figures and the type of figure. A set is a group of three cards such that, for each characteristic (number and figure), either the three cards are equal or the three cards are different.

For example, in the figure below, (a) is a valid set, since all cards have the same figure type and all of them have a different number of figures. In the example (b), both the type of figures and the number of figures are different, making also a valid set. On the other hand, (c) is not a valid set, as the last two cards have the same figure, which is different from the figure in the first card. The objective of the game is to form the largest number of sets with the cards that are on the table. Once a set is formed, the three cards are removed from the game.

When there are few cards on the table, it is easy to determine the largest number of sets that can be formed; however, when there are many cards on the table the number of combinations is too high. A friend wants to practice for the Set World Championship, and has asked you to write a program to calculate the largest number of sets that may be formed with a given group of cards.

## Input

The input contains several test cases. The first line of a test case contains an integer N (3 ≤ N ≤ 3 x 104), indicating the number of cards on the table. Each of the next N lines contains the description of one card.

The description of one card is given by two words, separated by one space. The first word is:

• "um" (means one in Portuguese); or
• "dois" (means two in Portuguese); or
• "tres" (means three in Portuguese)

indicating the number of figures in the card. The second word is

• "circulo" or "circulos" (means circle in Portuguese); or
• "triangulo" or "triangulos" (means triangle in Portuguese)

indicating the type of figure in the card. The end of input is indicated by a line containing only one zero.

## Output

For each test case in the input, your program must print a single line, containing one integer, indicating the largest number of sets that can be formed with the given cards.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include<bits/stdc++.h>
#define ll              long long
#define ull             unsigned long long
#define pb              push_back
using namespace std;
int main()
{
//freopen("input.txt","r", stdin);
//freopen("output.txt","w", stdout);

ll n,k,a,b;
cin >> n >> k;
for(ll i = 0; i < n; i++){
cin >> a[i];
}
for(ll i = 0; i < n; i++){
b[i] = 1;
}
ll j = 0;
for(ll i = 1; i < n; i++){
if(a[i] != a[i-1]){
b[j]++;
}
else{
j++;
}
}
sort(b,b+n,greater());
ll ans = b;
cout << ans << endl;

return 0;
}
``````
Copy The Code &