ZOJ 3492 Kagome Kagome

Kagome kagome, kago no naka no tori wa

Itsu itsu deyaru? Yoake no ban ni

Tsuru to kame to subetta.

Ushiro no shoumen daare?

Translation:

Kagome kagome, the bird in the cage,

when will you come out?

In the evening of the dawn,

the crane and turtle slipped.

Who stands right behind you now?

Kagome Kagome is a Japanese children's game. One child is chosen as the oni (literally demon or ogre, but similar to the concept of "it" in tag) and sits blindfolded (or with their eyes covered). The other children join hands and walk in circles around the oni while singing the song for the game. When the song stops, the oni speaks aloud the name of the person behind him, and if he is correct, the person behind will exchange places with the oni.

Higurashi Tewi is playing Kagome Kagome with her n (n is even) friends as the oni now. She peeps to know who is right in front of her. Knowing the order of the children in circle and assuming that they keep distance evenly, it's easy to derive who is right behind her.

Input

There are multiple test cases. The first line of input is an integer T

The first line of each test case starts with an even number 1 ≤ n ≤ 100, followed by the name of the child who is right in front of Higurashi Tewi. The second line contains exactly n

Output

For each test case, output the name of the child who is right behind Higurashi Tewi.      

Sample Input

3

2 Alice

Alice Bob

4 inu

inu neko usagi kizune

4 cat

dog cat rabbit fox

Sample Output

Bob

usagi

fox

References

• ​​http://en.wikipedia.org/wiki/Kagome_Kagome​​

簡單題，讀懂題意就行了

#include<map>
#include<cmath>    
#include<queue> 
#include<string>
#include<vector>
#include<cstdio>    
#include<cstring>  
#include<iostream>
#include<algorithm>    
using namespace std;
#define ms(x,y) memset(x,y,sizeof(x))    
#define rep(i,j,k) for(int i=j;i<=k;i++)    
#define per(i,j,k) for(int i=j;i>=k;i--)    
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])    
#define inone(x) scanf("%d",&x)    
#define intwo(x,y) scanf("%d%d",&x,&y)    
#define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z)    
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int T, n;
string s, a[N];

int main()
{
  for (inone(T); T--;)
  {
    inone(n); cin >> s;
    int k = 0;
    rep(i, 0, n - 1)
    {
      cin >> a[i];
      if (a[i] == s) k = i;
    }
    cout << a[(k + n / 2) % n] << endl;
  }
  return 0;
}