Skip to content

14268: 【原4268】助教吃火锅

题目

题目描述

author: Lei Zheng 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4268

Description

由于数据结构课程太火爆,开了好多的班级,每个班级都有至少有一个助教。有一天 N 个助教坐在一个大圆桌前面吃火锅,但是他们由于人数太多导致饭不太够吃了。于是他们决定用一种古老的方法每次选择一个助教出去继续做饭,只有等最后一个坐在桌子上的助教也参与做饭之后他们才能再回来。他们每人按座位顺序领了一个编号贴在自己的座位上,然后从 1 号座位的助教开始按顺序报数,报到 M 的人出局, 然后下一个人重新从 1 开始报数。参与这样一个游戏,当然是吃到最后才能吃的最好,那么问题来了,如果是参与这样一个聚会,怎么才能吃到最后呢,帮你们的助教选个座位吧~

Input Format

每行输入一个 N, 一个 M

Output Format

输出一个座位编号

Sample Input

3 2

Sample Output

3

ligongzzz's solution

#include <iostream>
#include <vector>
using namespace std;

int f(int n, int m) {
    if (n == 1)
        return 0;
    return (f(n - 1, m) + m) % n;
}

int main() {
    int n, m;
    cin >> n >> m;

    cout << f(n, m) + 1;

    return 0;
}

victrid's solution

#include <iostream>
using namespace std;
int next(bool table[], int total, int start, int step);
int main()
{
    int N;
    int M;
    int start = 0;
    cin >> N >> M;
    bool *table = new bool[N];
    for (int n = 0; n < N; n++)
        table[n] = true;
    start = 0;
    for (int i = 1; i <= N; i++)
    {
        start = next(table, N, start, M);
        table[start] = false;
    }
    cout << start + 1;
    return 0;
}
int next(bool table[], int total, int start, int step)
{
    while (step != 0)
    {
        if (table[start])
            step--;
        if (step == 0)
            return start;
        ++start;
        if (start == total)
            start = 0;
    }
}

Zsi-r's solution

#include <iostream>

using namespace std;

//single

class sLinkList
{
private:
    struct node
    {
        int data;
        node *next;

        node(const int &x, node *N=NULL){
            data = x; next = N;
        }
        node ():next(NULL){};
        ~node(){};
    };

    node *head;
    int currentLength;

    node *move(int i)const;

public:
    sLinkList();
    ~sLinkList(){delete head;}

    int length()const {return currentLength;}
    void insert(int i,int x);
    int eat(int N, int M);
};

typename sLinkList::node *sLinkList::move(int i)const
{
    node *p = head;
    while(i-->=0)p = p->next;
    return p;
}

sLinkList::sLinkList()
{
    head = new node;
    currentLength = 0;
}


void sLinkList::insert(int i,int x)
{
    node *pos;

    pos = move(i -1 );
    pos->next=new node(x,pos->next);
    ++currentLength;
}



int sLinkList::eat(int N, int M)
{
    node *p = head->next, *tmp;
    int length = N;

    tmp = move(N - 1);
    tmp->next = head->next;

    node *q = tmp ;

    while(length!=1)
    {   
        if (M > 1)
        {   
            for (int i = 0; i < M-1;i++)
            {
                q = p;
                p = p->next;
            }
        }
        q->next = p->next;
        delete p;
        length--;
        p = q->next;
    }
    head->next = p;
    return p->data;
}

int main()
{
    int N, M;
    cin >> N >> M;

    sLinkList mylist;

    for (int i = 0; i < N;i++)
    {
        mylist.insert(i, i + 1);
    }
    cout << mylist.eat(N, M);
}