ITSA 202404 #2: Names

A club wants to play a game where N students are lined up in a row. Starting from 1, they count to K, and the Kth student is marked as "PASS" and leaves the queue. The counting then resumes from the next student (the last student's next is the first one), and the process continues. The last student remaining will showcase their talent. Given the known values, which student initially stood in the position of the talent performer?

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The input begins with an integer T (1 < T < 10), indicating the number of test cases.
Each set of test data consists of 2 lines. The first line contains a positive integer N, indicating the number of students participating in the game (0 < N < 100). The second line contains a positive integer K, indicating that every Kth student is passed (K < N).		The output for each set of test data is a positive integer P representing the position of the student who must perform the talent show. There must be a newline character at the end.
2
15
4
85
2		13
43

Thought Process

宣告一個 Vector<Pair<int, int>>，從第 0 個位置到第 N-1 個位置分別為所有人，Pair 分別存取每一個人的上一位和下一位是誰 (Index)。當將某一個人踢出時，更新這個人的上一位和下一位，上一位的下一位變成被踢掉的人的下一位，下一位的上一位變成被踢掉的人的上一位。宣告一個 Map<int, int>，當踢掉人的時候就將這個人的 Index 值 的 Map +1。當踢掉 N-1 個人之後，跑 for (auto it:Map)，當 it.second == 0 時，代表 it.first 沒有被踢掉，輸出 it.first。需要注意的是 Map 需要先將 0 到 N-1 都初始化為 0。

Sample Code－ITSA 202404 #2: Names

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 0; i<T; i++)
    {
        int N, K;
        cin >> N >> K;
        vector<pair<int, int>>num;
        map<int, int>MAP;
        for (int j = 0; j<N; j++)
        {
            pair<int, int>tmp;
            tmp.first = j-1;
            tmp.second = j+1;
            if (j == 0) tmp.first = N-1;
            if (j == N-1) tmp.second = 0;
            num.push_back(tmp);
            MAP[j] = 0;
        }
        int count = 0, kill = 0;
        while (kill != N-1)
        {
            for (int j = 0; j<K-1; j++)
            {
                count = num[count].second;
            }
            int next = num[count].second;
            num[num[count].first].second = next;
            num[num[count].second].first = num[count].first;
            kill++;
            MAP[count]++;
            count = next;
        }
        for (auto it:MAP)
        {
            if (it.second == 0)
            {
                cout << it.first+1 << "\n";
                break;
            }
        }
    }
}

//ITSA 202404 #2
//Dr. SeanXD
Tags

Related Posts

Comments