9703. Biodiversity

Alicia has a huge garden, which is the habitat of many animals that she really cares about. After listening to a podcast about biodiversity, she becomes very concerned about the balance between species in her garden. She wants to know if there is a species that could overtake the others. To do so, she decides to carry out a census of all the animals in the garden, writing down the species of each of them. Can you help her check if there are strictly more animals from one species than there are from all the other species together?

Input. The first line contains the number of animals n (1 ≤ n ≤ 2 * 10⁵);

Each of the next n lines contains an animal as a string of length at most 20, containing only ASCII alphanumeric characters.

Output. Print a string that appears a number of times that is greater than the sum of the others, if there is any, or the string “NONE” otherwise.

Sample input 1	Sample output 1
3 frog fish frog	Frog
Sample input 2	Sample output 2
4 cat mouse mouse cat	NONE

SOLUTION

data structures - stack

Algorithm analysis

In this problem you must find the majority element. That is, you should find a word that occurs more than times, where n is a number of the given words.

Algorithm realization

Declare the used data. Animal species are stored in an array of strings v.

Simulate a stack with two variables:

· maj – majority element;

· cnt – how many times maj appears in the stack;

vector<string> v;

string maj;

int cnt;

Read the input data.

cin >> n;

v.resize(n);

for (i = 0; i < n; i++)

cin >> v[i];

Initially set the stack to be empty.

maj = ""; cnt = 0;

Process the input lines, simulate the stack.

for (i = 0; i < n; i++)

{

If stack is empty (cnt = 0), push v[i] into it.

if (cnt == 0) { maj = v[i]; cnt++; }

If the current element v[i] is the same as the top of the stack maj, then push v[i] into the stack.

else if (v[i] == maj) cnt++;

Otherwise, pop the element from the stack..

else cnt--;

}

Count in the cnt variable the number of times the number maj occurs in the array v.

cnt = 0;

for (i = 0; i < n; i++)

if (v[i] == maj) cnt++;

If cnt > , the majority element exists. Otherwise no (assign “NONE” to res).

if (2 * cnt > n) res = maj; else res = "NONE";

Print the answer.

cout << res << endl;