Problem of The Day 31 December — Superheroes and villains

Superheroes and villains

In a world of superheroes each person is either a superhero or a villain. It is well known that every superhero has a name ending with either “man” or “woman”, for example “chefman”, “prettywoman” are Superheroes. All other persons are villains, for example “hacker” and “unclejohn”.

Currently a big fight between the superheroes and the villains is going to happen. Initially there is only one superhero fighting one villain. Then total of N persons joined the fight one after another. If at point of time, there are two more superheroes than villains in the fight, superheroes will win the fight immediately, as they can overwhelm villains with their powers. On the other hand, if there are 3 more villains than superheroes at any time, they will win, because they use dirty tricks to defeat the superheroes. If over all all the fights, none of these cases happen, then the fight is declared to be a draw. For a given list of people joining the fight in the given order, decide which groups wins the fight or whether the fight is ended with a draw.

Input

In the first line there is a single integer T denoting the number of test cases to handle. After that the description of T test cases follow.

Description of each test cases starts with a line containing a single integer N denoting the number of people joining the fight.

The i-th of the following N lines contains the name of person joining the fight at time i.

Output

For each test cases, output either “superheroes” if superheroes win the fight, “villains” if villains win or a “draw” if the fight ends with a draw. All of these strings should be outputted without quotes.

Constraints

• 1 ≤ T ≤ 10
• Every person’s name consists only of English lowercase letters (i.e. from ‘a’ to ‘z’) and it is no longer than 15 characters.
• No two persons have the same name.

Subtasks

Subtask #1: (30 points)

• 1 ≤ N ≤ 500

Subtask #2: (70 points)

• 1 ≤ N ≤ 105

Example

Input:
3  
2   
kittywoman  
wingman  
6  
hacker  
beautywoman  
blackjack  
noname  
watersnake  
strongman  
4  
famousman  
redsnake  
tallwoman  
tinythief
Output:
superheroes
villains
draw
Explanation
Example case 1. As you know that initially a superhero is fighting with a villain. After that, superhero "kittywoman" joins the fight. At this point, there are two superheros and one villain. After that "wingman" joins the fight too. As this point of time, there are three superheros and one villain, so the number of superheros are two more than number of villains, so superheros will win the fight.
Example case 2. Other than first two peoople, six more people join the fight. The moment when the fight is decided is after watersnake joins the fight, because there are two superheroes fighting five villains, so villains will win.
Example case 3. Other than initial two people, four more people join the fight, and there is no moment at which the fight can be decided, so it ends with a draw.
Problem Link: Superheroes and villains
Solution will be posted tomorrow.
SOLUTION
Search for the "man" in the string at last. And keep count of superheroes and villains and check according to the condition  If at point of time, there are two more superheroes than villains in the fight, superheroes will win the fight immediately, as they can overwhelm villains with their powers. On the other hand, if there are 3 more villains than superheroes at any time, they will win, because they use dirty tricks to defeat the superheroes. If over all all the fights, none of these cases happen, then the fight is declared to be a draw. For a given list of people joining the fight in the given order, decide which groups wins the fight or whether the fight is ended with a draw.

CODE

#include<iostream>
#include<cstring>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define long int ll;
int main()
{
  ll T; cin>>T;
  while(T--)
  {
    ll N,superheroes,villains,len;
    bool ansPrinted = false;
    cin>>N;
    
    superheroes = 0;
    villains = 0;
char str[16];
    
    for(ll i=0; i<N; i++)
    {
      scanf("%s",str);
      len = strlen(str);
      
      if(str[len-1]=='n' && str[len-2]=='a' && str[len-3]=='m')
      {
        superheroes++;
      }
      else
      {
        villains++;
      }
      if(ansPrinted==false)
      {
        if(superheroes==(villains+2))
        {
          ansPrinted = true;
          cout<<"superheroes"<<endl;
        }
        else if(villains==(superheroes+3))
        {
          ansPrinted = true;
          cout<<"villains"<<endl;
        }
      }
    }
    if(ansPrinted == false)
    {
       cout<<"draw"<<endl;
    }
  }
}