1674 - 年终大奖
ACM俱乐部又要发年终大奖了！这次获大奖的人从n名会员中按以下规则选出：
首先,让会员们围成一个大圈，按0,1,2...n-1编号。然后,随机抽取一个数m,让编号为0的会员开始报数。每次喊到m的那个会员出列,不再回到圈中,从他的下一个人开始,继续1...m报数....这样下去....直到剩下最后一个会员为止。这名会员就能获得大奖了。
题目输入
输入有多组数据。
每组数据一行,包含2个整数n(1<=n<=100,000),m(1<=m<=100,000),n,m分别表示会员的人数(编号0,1,2...n-1)和数m(如上文所述)。
题目输出
对应每组数据,输出最后拿到大奖的会员编号。
输入/输出样例
题目输入
5 7 7 8 43 18
题目输出
3 3 18
C语言解答
/* * ===================================================================================== * * Filename: 902-2.c * * Description: hahahhaha * * Version: 1.0 * Created: 2013/9/3 0:12:15 * Revision: none * Compiler: gcc * * Author: mdk-vim.cpp-c (mdk), mengdaikun@gmail.com * Company: cjluacm-vim-mdk * * ===================================================================================== */ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> int main() { //freopen("a.in","r",stdin); int n,m; int i; while(~scanf("%d %d",&n,&m)) { int s = 0; for(i = 2 ; i <= n ;i++) { s = (s+m) % i; } printf("%d\n",s); } return 0; }
C++解答
#include <stdio.h> /////////////////////////////////////////////////////////////////////// // n integers (0, 1, ... n - 1) form a circle. Remove the mth from // the circle at every time. Find the last number remaining // Input: n - the number of integers in the circle initially // m - remove the mth number at every time // Output: the last number remaining when the input is valid, // otherwise -1 /////////////////////////////////////////////////////////////////////// int LastRemaining_Solution2(int n, unsigned int m) { // invalid input if(n <= 0 || m < 0) return -1; // if there are only one integer in the circle initially, // of course the last remaining one is 0 int lastinteger = 0; // find the last remaining one in the circle with n integers for (int i = 2; i <= n; i ++) lastinteger = (lastinteger + m) % i; return lastinteger; } int main() { int a,b; while(scanf("%d%d",&a,&b)!=EOF) printf("%d\n",LastRemaining_Solution2(a,b)); return 0; }