问题 D: Eeny Meeny

问题 D: Eeny Meeny
时间限制: 2 Sec 内存限制: 128 MB

题目描述

“Eeny meeny miny moe” is a well-known nursery rhyme in English, used (among other things) by kids to “randomly” select members of a team. It exists in many variations, one of which goes like this:
Eeny, meeny, miny, moe,
Catch a tiger by the toe.
If he hollers, let him go,
Eeny, meeny, miny, moe.
Similar verses exist in most languages, such as “Ulle dulle dof” in finnish, “Akka bakka bonka rakka” in Norwegian, and “Ole dole doff” in Swedish.
Two teams are to be selected for a game and the rhyme is used to select one kid for a team at a time, alternating between the two teams, until all kids have been selected. The kids are standing in a circle. In each selection round we start counting the kids in clockwise order around the circle, skipping one kid for every word in the rhyme, until the last word. The kid matching the last word is chosen for the current team and then the next round starts. In all rounds but the first, the counting starts at the next remaining kid (in clockwise order) after the one that was selected in the previous round. See figure E.1 for an example.
Given such a rhyme, and a group of kids, can you tell which kids will be in which team?

figure E.1: Illustration of the first three rounds of Sample Input 1. In rounds 1 and 3, Alvar and Rakel get selected for the first team, and in round 2, Lisa is selected for the second team. In round 4 (not shown), only Kalle remains and is selected for the second team.

输入

The first line of input contains the rhyme, consisting of a list of words separated by spaces. The second line of input contains an integer n (1 ≤ n ≤ 100), the number of kids. Then follow the names of the kids, one per line. The kids are given in clockwise order and the first kid listed is the one at which counting starts in the first round.
All words and names consist only of upper and lower case letters ‘ A ’-‘ Z ’ and ‘ a ’-‘ z ’. No input line is empty or longer than 100 characters (excluding the newline character at the end of the line).

输出

Output the two teams, starting with the one whose first member is chosen first. For each team, output the number of kids in the team, followed by the names of the kids in the team, in the same order as they were chosen for the team.

样例输入 Copy

eeny meeny miny
4
Kalle
Lisa
Alvar
Rakel

样例输出 Copy

2
Alvar
Rakel
2
Lisa
Kalle

---

这是一道对约瑟夫环的简单应用，我们需要做的就是将约瑟夫环实现，并且将每一次的第k个人找到，并且放到两个数组内即可。

下面是代码的实现

#include <bits/stdc++.h>

using namespace std;

const int N = 150;

int n;
string str;
string s[N];
queue<int> q;
vector<int> v1, v2;

int main(){
    int k = 0;
    //读入口令，找到单词的个数
    getline(cin, str);
    stringstream ss(str);
    string p;
    while (ss >> p) k ++;
    
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> s[i];
        q.push(i);
    }
    //实现约瑟夫环
    int cnt = 0, f = 0;
    while(q.size()){
        cnt ++;
        if (cnt < k) q.push(q.front()), q.pop();
        else {
            cnt %= k;
            if (1 - f) v1.push_back(q.front()), q.pop(), f = 1 - f;
            else v2.push_back(q.front()), q.pop(), f = 1 - f;
        }
    }
    //cout << k << endl;
    //输出两部分的结果
    printf("%d\n", v1.size());
    for (int i = 0; i < v1.size(); i ++ ) cout << s[v1[i]] << endl;
    printf("%d\n", v2.size());
    for (int i = 0; i < v2.size(); i ++ ) cout << s[v2[i]] << endl;
    
    return 0;
}