#NC22227. 约瑟夫环

约瑟夫环

题目描述

有 nn 个人(编号 0∼n−10\sim n-1)围成一圈,从编号为 kk 的人开始报数,报数依次为 1,2,…,m1,2,\ldots,m,报到 mm 的人出队。下次从出队者的下一个人开始重新从 11 报数,循环往复,直到队伍中只剩最后一个人,该人即“大王”。

给定三个整数 n,k,mn,k,m,请输出最后剩下的“大王”编号。

输入格式

在一行中输入三个整数 n,k,mn,k,m,用空格隔开。满足 2≤n≤1002\le n\le100,0≤k≤n−10\le k\le n-1,1≤m≤1001\le m\le100。

输出格式

输出一个整数,表示最后剩下的"大王"编号。

提示

初始队列编号为 [0,1,2,3,4][0,1,2,3,4],从编号 11 开始报数:

  • 22 出队,剩余 [0,1,3,4][0,1,3,4];
  • 44 出队,剩余 [0,1,3][0,1,3];
  • 11 出队,剩余 [0,3][0,3];
  • 00 出队,剩余 [3][3],输出 33。

样例 1

5 1 2
3

来源

牛客原题