Problem Description

有n个人被从1到n进行了编号,然后这n个按编号以顺时针方向围成一个圈。现在从第s号人员开始从1开始按顺时针方向报数,当某人报到m时,此人从圈中出列,排在他下面的人重新开始这一报数过程,…,直到这个圈中只剩下一个人为止。现在请你计算一下最后的那个人的编号是多少?

Input

输入的第一行有一个整数K,表示测试样例的个数。
接下来有K行,每行包含三个整数n,s,m分别为题中含义的具体数值,1<=s,m<=n<=1000。

Output

输出K行,每行一个整数为对应的测试样例中数据所求得的结果。

Sample Input

1
5 3 4

Sample Output

3

代码:

#include <iostream>
#include <string>

using namespace std;

class Node
{
public:
    Node *next;
    Node *pre;
    int value;
};

int main()
{
    string anw = "";

    int K = 0;
    cin >> K;

    for (int i = 0; i < K; i++)
    {
        int n = 5, s = 3, m = 4;

        cin >> n >> s >> m;

        Node *beginNode = new Node();
        beginNode->value = 1;

        Node *preNode;
        preNode = beginNode;

        for (int i = 2; i <= n; i++)
        {
            Node *node = new Node();
            node->value = i;
            node->pre = preNode;
            preNode->next = node;
            preNode = node;
        }

        preNode->next = beginNode;
        beginNode->pre = preNode;

        Node *pointerNode;
        pointerNode = beginNode;

        for (int i = 1; i < s; i++)
        {
            pointerNode = pointerNode->next;
        }

        while (pointerNode->next != pointerNode)
        {
            for (int i = 1; i < m; i++)
            {
                pointerNode = pointerNode->next;
            }

            pointerNode->pre->next = pointerNode->next;
            pointerNode->next->pre = pointerNode->pre;
            pointerNode = pointerNode->next;
        }

        anw.append(to_string(pointerNode->value));

        if (i + 1 != K)
        {
            anw.append("\n");
        }
    }

    cout << anw << endl;
}
分类: 未分类

发表评论

电子邮件地址不会被公开。