Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 4509 | Accepted: 2384 |
Description
Let’s play a stone removing game.
Initially, n stones are arranged on a circle and numbered 1, …, n clockwise (Figure 1). You are also given two numbers k and m. From this state, remove stones one by one following the rules explained below, until only one remains. In step 1, remove stone m. In step 2, locate the k-th next stone clockwise from m and remove it. In subsequent steps, start from the slot of the stone removed in the last step, make k hops clockwise on the remaining stones and remove the one you reach. In other words, skip (k − 1) remaining stones clockwise and remove the next one. Repeat this until only one stone is left and answer its number. For example, the answer for the case n = 8, k = 5, m = 3 is 1, as shown in Figure 1.
Initial state |
Step 1 |
Step 2 |
Step 3 |
Step 4 |
Step 5 |
Step 6 |
Step 7 |
Final state |
Initial state: Eight stones are arranged on a circle.
Step 1: Stone 3 is removed since m = 3.
Step 2: You start from the slot that was occupied by stone 3. You skip four stones 4, 5, 6 and 7 (since k = 5), and remove the next one, which is 8.
Step 3: You skip stones 1, 2, 4 and 5, and thus remove 6. Note that you only count stones that are still on the circle and ignore those already removed. Stone 3 is ignored in this case.
Steps 4–7: You continue until only one stone is left. Notice that in later steps when only a few stones remain, the same stone may be skipped multiple times. For example, stones 1 and 4 are skipped twice in step 7.
Final State: Finally, only one stone, 1, is on the circle. This is the final state, so the answer is 1.
Input
The input consists of multiple datasets each of which is formatted as follows.
n k m
The last dataset is followed by a line containing three zeros. Numbers in a line are separated by a single space. A dataset satisfies the following conditions.
2 ≤ n ≤ 10000, 1 ≤ k ≤ 10000, 1 ≤ m ≤ n
The number of datasets is less than 100.
Output
For each dataset, output a line containing the stone number left in the final state. No extra characters such as spaces should appear in the output.
Sample Input
8 5 3 100 9999 98 10000 10000 10000 0 0 0
Sample Output
1 93 2019
题意:
给出 N(2 ~ 10000),K(1 ~ 10000),M(1 ~ N)。代表有 1 ~ N 个数,每隔 K 个数就删除一个数,从 M 这个数开始数(M 这个数第一删除)。输出最后一个输出的数是什么。属于多组输入。
思路:
递推。DP。
假设K = 5(不考虑第一个数被删除):
N = 2 时,即 1, 2 => 从1 开始数,1,2,1,2,1,删除1,故最后删除的是 2,表示当 N = 2 时,最后将会删除第二个数;
N = 3 时,即 1,2,3 => 从 1 开始数,1,2,3,1,2,删除2,还剩两个数 N = 2,由上面的情况可得知,最后将会删除接下来数的顺序的第二个数,故最后会删去第一个数;
由此递推下去,可得知推知结果。
与此考虑不同只是第一删除的会是 M 这个元素,故不考虑该元素,从下个元素开始即可。
AC:
#include<stdio.h> int fin[10005]; int main() { int n,k,m; while(~scanf("%d%d%d",&n,&k,&m) && (n + k + m)) { int num; fin[2] = (k % 2) ? 2 : 1; for(int i = 3;i <= n - 1;i++) { int ans; if(i < k) ans = k % i; else ans = k; fin[i] = (ans + fin[i - 1]) % i; if(!fin[i]) fin[i] = i; } if(n > 2) { num = (fin[n - 1] + m) % n; if(!num) num = n; } else { if(m == 1) num = 2; if(m == 2) num = 1; } printf("%d\n",num); } return 0; }
相关推荐
在这篇文章中,我将讨论利用 Function 接口提供的两个组合函数—— compose 和 andThen 来实现函数的组合。 什么是函数组合? 首先需要创建一些小的可重用函数,然后将这些小函数组合为新函数。 现在,我们...
This book first covers fundamental mathematics for Big-O analysis and then lays out the basic JavaScript foundations, such as primitive objects and types. Then, this book covers implementations and ...
Iterative decoding was originally devised by Gallager in 1960 in his remarkable thesis and then long forgotten. It was rediscovered by Berrou, Glavieux, and hitimajshima in 1993 in the form of turbo ...
Then, there was a change of project and I was thrown headlong into writing code using the multithreaded paradigm. The language was C or C++, which I loved deeply; however, to my surprise I found that ...
Lets you type in text and then recall it by using the write/input function.
Opens a recordset and then uses the Printer object to print each record to the default printer.
1960s, there was the work of Btichi on automata on infinite strings and the second order theory of one successor, then Rabin's 1968 result on automata on infinite trees and the second order theory of ...
2013年九年级英语下册 Module 3 Now and then短语 外研版
First there was the BlackBerry, then there was the iPhone, and now … there’s Google, with its Android Mobile Software Development Kit (SDK) and platform, and its hardware partners in the Open ...
And then there is the issue of the database management system. Where does the processed data get stored? Who designs the database and its tables? Who administers it? How does the information get from...
Then, following the main results, the channel and source coding theorems, there is a study of specific coding schemes which can be used for channel and source coding. This volume can be used either ...
One needs to look at specific metrics such as the growth of leverage, and the borrowers' ability to service debt if there is a disruption to income or rise in interest rates. MGI found that ...
2013年九年级英语下册 Module 3 Now and then模块测试题 外研版
2013年九年级英语下册 Module 3 Now and then单元精品教案 外研版
operating system every possible tip, trick, hint, and hack there is—and then squeezes some more to reveal a substantial number of hidden and secret tips. The first edition of Mac Kung Fu was hugely ...
There was some response, which was incorporated from its many sources, and it is presented here in entirety, enhanced a bit. There have been some interesting changes in the world since then. We now ...
Then how are we supposed to write our models and controllers? Do we even have those anymore? Googling only takes you so far... There aren't many good tutorials that show how everything works together...
There was no team but me, a lot of pizzas, an unknown number of cans of Red Bull, and many sleepless nights. The result is The DevOps 2.0 Toolkit: Automating the Continuous Deployment Pipeline with ...
Since then he has supported his brother David in refining and expanding the scope of this popular linear algebra text, including writing most of Chapters 8 and 9. Steven is also the author of three ...
2013年九年级英语下册 Module 3 Now and then Unit 1 People are healthier today.课件 外研版