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
Declare a Vector<Pair>, where each element from the 0th position to the (N-1)th position represents each person, and Pair stores the indices of the person's previous and next positions. When kicking out a person, update the indices of their previous and next positions, with the next position of the previous person becoming the next position of the kicked person, and the previous position of the next person becoming the previous position of the kicked person. Declare a Map, where when kicking out a person, increment the value of the kicked person's index in the Map by 1. After kicking out (N-1) people, iterate over the Map using a for loop (auto it), and when it.second == 0, it means it.first has not been kicked out, so output it.first. Note that the Map needs to be initialized with values 0 for indices 0 to (N-1).
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