And Then There Was One

http://poj.org/problem?id=3517

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 4805		Accepted: 2546

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

Figure 1: An example game

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

 #include"string.h"

 int f[];

 int main()

 {

     int n,k,m,i,j;

     while(scanf("%d%d%d",&n,&k,&m)==&&n)

     {

         f[]=;

         for(i=;i<n;i++)   //重新编号，即编号映射

             f[i]=(f[i-]+k)%i;

         f[n]=(f[n-]+m)%n;

         printf("%d\n",f[n]+);

     }

     return ;

 }

随机推荐

UIDynamic(捕捉行为)
一.简介可以让物体迅速冲到某个位置(捕捉位置),捕捉到位置之后会带有一定的震动 UISnapBehavior的初始化 - (instancetype)initWithItem:(id <UID ...
加密工具类 - CryptoUtils&period;java
加密工具类,包含MD5,BASE64,SHA,CRC32的加密与解密方法. 源码如下:(点击下载 - CryptoUtils.java.commons-io-2.4.jar.commons-code ...
查看SQL Server 备份信息
RESTORE HEADERONLY FROM DISK = N'C:\Program Files\Microsoft SQL Server\MSSQL10_50.SQL2008\MSSQL\Back ...
asp&period;net mvc jqgrid 同一个页面查询不同的表，jqgrid显示不同表的表头和数据并且分页
基于我上一篇文章<a href="http://www.cnblogs.com/alasai/p/4765756.html">asp.net mvc excel导入&l ...
转：Qt项目中遇到的一些小问题汇总
链接:http://blog.csdn.net/yangyunfeizj/article/details/7082001 作者:GoatYangYang 公司让负责qt界面开发,但是接触qt又不 ...
ViewPager实现页卡的最新方法--简洁的TabLayout（谷歌支持包）
效果图: 添加依赖包: compile ‘com.android.support:design:‘ 布局文件: <?xml version="1.0" encoding=&q ...
Junit 测试常见错误
1. java.lang.Exception: No tests found matching Method deleteUser(mybatis.dao.Usertest) from org.jun ...
在idea的maven项目使用el或jstl表达式
必须加上这句: <%@ page isELIgnored="false" %> 否则无法解析el或jstl表达式 <%@ taglib prefix=" ...
英语词汇（2）fall down，fall off和fall over
一.fall down,fall off和fall over都表示"摔倒.跌倒"的意思,但它们各自的含义不同. 1.fall over 落在...之上, 脸朝下跌倒 fall ov ...
OpenCV Mat与UIImage之间的转换
UIImage 转 OpenCV cvMat: - (cv::Mat)cvMatWithImage:(UIImage *)image { CGColorSpaceRef colorSpace = CG ...

秒客网

And Then There Was One

随机推荐

相关文章