Problem:


ヨセフのおイモ

昔、ヨセフのおイモというゲームがありました。n 人が参加しているとしましょう。参加者は中心を向いて円陣を組み、1 から順番に番号が振られます。アツアツのおイモがひとつ、参加者 n (左の図内側の大きい数字の 30 )に渡されます。おイモを渡された参加者は右隣の参加者にそのおイモを渡します。 m 回目に渡された人は右隣の人に渡して円陣から抜けます(左の図では m = 9 の場合を表しています) 。 回渡す毎に一人ずつぬけ、最後に残った人が勝者となり、おイモをいただきます。

n ,m が決まってから、実際におイモを渡し始める前にどこにいたら勝てるかわかるといいですよね。上の図は 30 人の参加者で 9 人ごとに抜けるというルールでこのゲームをした場合を書き表しています。内側の大きい数字が参加者に振られた番号、外側の小さい数字が抜ける順番です。それによると、9,18,27,6,16,26 という順番で円陣から抜け出し、最後には 21 が残ることになります。すなわち 21 が勝者となります(小さい数字が 30 になっています)。

ゲーム参加者数 n と円陣から抜け出す参加者の間隔 m を入力し、勝者の番号を出力するプログラムを作成してください。ただし、m, n < 1000 とします。

入力

複数のデータセットが与えられます。各データセットは以下の形式で与えられます。

n m

ゲーム参加者数 n （整数）と円陣から抜け出す参加者の間隔 m （整数）が空白区切りで１行に与えられます。

入力は２つの 0 で終わります。データセットの数は 50 を超えません。

出力

各データセットに対して、勝者となりおイモをいただく人の番号（整数）を１行に出力してください。

Sample Input

41 3
30 9
0 0

Output for the Sample Input

31
21



Sample input:
41 3
30 9
0 0


Sample output:
31
21

Submission status: Wrong Answer

Solution code:
while True:
  n,m = input().split()
  n = int(n)
  m = int(m)
  if n==m==0:
    break
  l = [i for i in range(n)]
  c = 0
  while len(l) >= 2:
    c = (c+m)%len(l)
    l.pop(c)
    c -= 1
  print(l[0])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
p, i = [i+1 for i in range(n)], m
while True:
    p.pop(m-1)
    if len(p)==1:
        print(p[0])
        break
    tmp = m+i-1
    m = tmp%len(p) if tmp>len(p) else tmp

Submission status: Wrong Answer

Solution code:
while True:
    n, m = map(int, input().split())
    if n==0: break
    p, i = [i+1 for i in range(n)], m
    while True:
        p.pop(m-1)
        if len(p)==1:
            print(p[0])
            break
        tmp = m+i-1
        m = tmp%len(p) if tmp>len(p) else tmp

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

for line in stdin:
    n, m = (int(s) for s in line.split())
    if not (n or m):
        break
    ary = bytearray(b'\x01'*n)
    index = n
    while any(ary):
        count = m
        while count:
            index = (index+1) % n
            if ary[index]:
                count -= 1
        ary[index] = 0
    print(index)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

for line in stdin:
    n, m = (int(s) for s in line.split())
    if not (n or m):
        break
    ary = list(range(0, n))
    i = m
    m -= 1
    answer = ary.pop(i)
    while ary:
        i = (i+m) % len(ary)
        answer = ary.pop(i)
    print(answer)

Submission status: Wrong Answer

Solution code:
while True:
    n, m = map(int, raw_input().split())
    if n==0 and m==0:
        break
    p = range(n); idx = 0;
    while len(p)>1:
        idx = (idx + m)%len(p)
        p.pop(idx)
        idx = (idx + len(p) - 1)%len(p)
    print p[0]

Submission status: Accepted

Solution code:
from copy import copy

while(1):
    n,m_ = [int(i) for i in input().split()]
    if n == 0 and m_ == 0:
        break
    m = m_ -1
    potato = [i+1 for i in range(n)]
    while(1):
        l = len(potato)
        if l == 1:
            print(potato[0])
            break
        pivot = (m+1)%l
        if pivot != 0:
            potato = copy(potato[pivot:] + potato[:pivot-1])
        else:
            potato = copy(potato[:-1])

Submission status: Accepted

Solution code:
while True:
    try:
        n, m = map(int, input().split(' '))
        pt = -1
        p_list = [i + 1 for i in range(n)]
        f_list = [0] * n
        while p_list.count(0) != n - 1:
            for i in range(m):
                if pt == n-1:
                    pt = 0
                else:
                    pt += 1
                while p_list[pt] == 0:
                    if pt == n-1:
                        pt = 0
                    else:
                        pt += 1
            p_list[pt] = 0
        print(sum(p_list))
    except:
        break

Submission status: Accepted

Solution code:
def solve(li,nu,mu,cnt):
    if len(li) == 1:
        return li[0]
    next_num = (nu+mu)%(len(li))-1
    pop_num = (nu+mu)%(len(li))
    li.pop(pop_num)
    return solve(li,next_num,mu,cnt+1)

while True:
    n,m = map(int,raw_input().split())
    if n == m == 0:
        break
    lis = range(1,n+1)
    print solve(lis,n-1,m,0)

Submission status: Accepted

Solution code:
import sys
f = sys.stdin

while True:
    n, m = map(int, f.readline().split())
    if n == m == 0:
        break
    circle = [i + 1 for i in range(n)]
    cnt = 0
    while len(circle) != 1:
        cnt += m - 1
        cnt %= len(circle)
        circle = circle[:cnt] + circle[cnt + 1:]
    print(circle[0])

Submission status: Accepted

Solution code:
from collections import deque
while True:
    try:
        n,m = map(int,raw_input().split())
        if (n,m) == (0,0) :
            break
    except EOFError:
        break
        
    d = deque([i for i in range(1,1+n)])
    while len(d)> 1:
        d.rotate(-m+1)
        d.popleft()
    print d[0]

Submission status: Accepted

Solution code:
while True:
    n, m = map(int, raw_input().split())
    if n == 0: break
    
    lis = [i+1 for i in range(n)]
      
    while True:  
        for i in range(m):
            if i == m-1:
                del lis[0]
            else:
                lis.append(lis[0])
                del lis[0]
        
        if len(lis) == 1:
            print lis[0]
            break

Submission status: Accepted

Solution code:
while True:
  n,m = input().split()
  n = int(n)
  m = int(m)
  if n==m==0:
    break
  l = [i for i in range(n)]
  c = -1
  while len(l) >= 2:
    c = (c+m)%len(l)
    l.pop(c)
    c -= 1
  print(l[0]+1)

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,raw_input().split())
    if n==0:
        break
    l=range(1,n+1)
    tmp=[]
    cnt=0
    while 1:
        if len(l)==1 and len(tmp)==0:
            print l.pop()
            break
        cnt+=1
        if cnt%m:
            tmp.append(l.pop(0))
        else:
            l.pop(0)
        if len(l)==0:
            l=tmp
            tmp=[]
exit()

Submission status: Accepted

Solution code:
def solve(n,m):
	A=[i for i in range(1,n+1)]
	i=n-1
	while True:
		if len(A)==1:
			break
		i=(i+m)%len(A)
		A.pop(i)
		i=i-1 if i>0 else len(A)-1
	return A[0]




while True:
	n,m=map(int,input().split())
	if n==m==0:
		break
	print(solve(n,m))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
'import math'
while 1:
    n,m=input().split()
    n=int(n)
    m=int(m)
    if n==m==0:sys.exit()
    a=m-1
    while a<(m-1)*n:
        a=int(m*a/(m-1)+1)
    a=n*m-a
    print(a)

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,input().split())
    if n==m==0:break
    a=m-1
    while a<(m-1)*n:
        a=int(m*a/(m-1)+1)
    print(n*m-a)

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,input().split())
    if n==0:break
    a=m-1
    while a<(m-1)*n:
        a=m*a//(m-1)+1
    a=n*m-a
    print(a)

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,input().split())
    if n==0:break
    a=m-1
    while a<(m-1)*n:
        a=m*a//(m-1)+1
    print(n*m-a)

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,input().split())
    if n==0:break
    a=m-1
    while a<(m-1)*n:a=m*a//(m-1)+1
    print(n*m-a)

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,input().split())
    if n==0:break
    a=m-1
    while a<(m-1)*n:a=int(m*a/(m-1)+1)
    print(n*m-a)

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,input().split())
    if n==0:break
    a=m-1
    while a<m*n-n:a=m*a//(m-1)+1
    print(n*m-a)

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,input().split())
    if n==0:break
    a=0
    for i in range(2,n+1):a=(a+m)%i
    print(a+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

for s in sys.stdin:
    n, m = map(int, s.split())
    if n == m == 0:
        break

    lst = [i for i in range(1, n+1)]

    remove_index = m - 1
    while len(lst) > 1:
        del lst[remove_index]

        # next index
        remove_index += (m - 1)
        if remove_index >= len(lst):
            remove_index = remove_index % len(lst)

    print(lst[0])

Submission status: Accepted

Solution code:
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    p = [i for i in range(1, n+1)]
    idx = m-1
    while len(p) != 1:
        v = p.pop(idx)
        idx = (idx+m-1) % len(p)
    print(*p)

Submission status: Accepted

Solution code:
def act(t,m,l):
    t = (t+m) % len(l);
    del l[t-1]
    return (t-1) % (len(l)+1)

while True:
    i = raw_input().split()

    n = int(i[0])
    m = int(i[1])

    if n == 0 and m == 0:
        break
    else:
        l = range(1,n+1)
        t = 0
        for i in range(n-1):
            tt = act(t,m,l);
            t = tt;
        print l[0]

Submission status: Accepted

Solution code:
# Aizu Problem 0085: Joseph's Potato
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input2.txt", "rt")


def josephus_survivor(n,k):
    people = list(range(1, n+1))
    current = (k - 1) % n
    while len(people)> 1:
        removed = people.pop(current)
        current = (current + k - 1) % len(people)
    return people[0]

while True:
    n, m = [int(_) for _ in input().split()]
    if n == m == 0:
        break
    print(josephus_survivor(n, m))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0085

"""
import sys
from sys import stdin
input = stdin.readline


def solve(n, m):
    remaining = list(range(1, n+1))
    start = n - 1               #  ????????????????????????????????????
    while n > 1:
        v = (m+start) % n       #  ????????????????±???????
        remaining.pop(v)
        start = v - 1           #  ????????????????????¢????????£??????????????????
        n -= 1
    return remaining[0]


def main(args):
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break
        result = solve(n, m)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
while True:
    n,m = [int(i) for i in input().split()]
    if n == 0 and m == 0:
        break

    table = []
    for i in range(n):
        table.append(i+1)

    p = m - 1
    for i in range(n-1):
        table.pop(p)
        p = (p+m-1) % len(table)
        #print(table)
    print(table[0])

Submission status: Accepted

Solution code:
from collections import deque

while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    q = deque([i for i in range(n)]) 
    i = 0
    while True:
        i += 1
        if i == m:
            q.popleft()
            i = 0
            if len(q) == 1:
                print(q.pop() + 1)
                break
        else:
            q.append(q.popleft())

Submission status: Accepted

Solution code:
while True:
  n, m = map(int, input().split())
  if not n:
    break

  lst = [i for i in range(1, n + 1)]
  ind = n - 1

  while len(lst) > 1:
    ind = (ind + m) % len(lst)
    lst.pop(ind)
    ind -= 1

  print(lst[0])

Submission status: Accepted

Solution code:
while 1:
    n,m=list(map(int,input().split()))
    if n==0 and m==0:break
    l=[i for i in range(1,1+n)]
    st=m-1
    while len(l)!=1:
        del l[st]
        st+=(m-1)
        while 1:
            if st>=len(l):
                st=st-len(l)
            if st<len(l):break  
    print(l[0])

Submission status: Accepted

Solution code:
while 1:
    n,m=list(map(int,input().split()))
    if n==0 and m==0:break
    l=list(range(1,1+n))
    st=m-1
    while len(l)!=1:
        del l[st]
        st+=(m-1)
        while 1:
            if st>=len(l):
                st=st-len(l)
            if st<len(l):break  
    print(l[0])

Submission status: Accepted

Solution code:
# AOJ 0085 Joseph's Potato
# Python3 2018.6.15 bal4u

while True:
	try:
		n, m = map(int, input().split())
		if n == 0:
			break
			
	except EOFError:
		break
		
	k = 1;
	for j in range(2, n+1):
		k = (k + m) % j
		if k == 0: k = j
	print(k)

Submission status: Accepted

Solution code:
# AOJ 0085 Joseph's Potato
# Python3 2018.6.15 bal4u

while True:
	n, m = map(int, input().split())
	if n == 0:
		break
	k = 1;
	for j in range(2, n+1):
		k = (k + m) % j
		if k == 0: k = j
	print(k)

Submission status: Accepted

Solution code:
ans = []
while True:
    data = raw_input().split()
    n = int(data[0])
    m = int(data[1])
    if n == 0 and m == 0:
        break
    
    member = range(1,n+1)
    p = 0
    c = n
    while c != 1:
        p += m-1
        if p >= c:
            while p >= c:
                #print 'out:',p,'->',p-c
                p = p-c
                
        #print 'c:',c,' p:',p
        temp = member.pop(p)
        #print temp
        c -= 1
    ans.append(member[0])
for i in ans:
    print i

Submission status: Accepted

Solution code:
def f(n,k):
    return 0 if n==1 else (f(n-1,k)+k)%n
while True:
    n,k=map(int,raw_input().strip().split())
    if (n,k)==(0,0):
        break
    print f(n,k)+1

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

for line in stdin:
    n, m = (int(s) for s in line.split())
    if not (n or m):
        break
    ary = bytearray(b'\x01'*n)
    index = n - 1
    while any(ary):
        count = m
        while count:
            index = (index+1) % n
            if ary[index]:
                count -= 1
        ary[index] = 0
    print(index + 1)

Submission status: Accepted

Solution code:
while True:
    n, m = map(int, raw_input().split())
    if (n,m) == (0,0):
        break
    r = 1
    for i in range(2, n + 1):
        r = (r + m) % i
        if r == 0:
            r = i
    print r

Submission status: Accepted

Solution code:
while True:
      n, m = map(int, raw_input().split())
      if n == 0 and m == 0:
            break
      p = [ 1 for i in range(n) ]
      pn = n; count = 0
      while pn > 1:
            for i in range(n):
                  if p[i] == 1:
                        count += 1
                        if count == m:
                              if p.count(1) > 1:
                                    p[i] = 0
                                    pn -= 1
                                    count = 0
      print p.index(1)+1

Submission status: Accepted

Solution code:
while True:
      n, m = map(int, raw_input().split())
      if n == 0 and m == 0:
            break
      p = [ 1 for i in range(n) ]
      pn = n; count = 0; flag = 1
      while flag == 1:
            for i in range(n):
                  if p[i] == 1:
                        count += 1
                        if count == m:
                              p[i] = 0
                              count = 0
                              pn -= 1
                              if pn == 1:
                                    flag = 0
                                    break

      print p.index(1)+1

Submission status: Accepted

Solution code:
while True:
      n, m = map(int, raw_input().split())
      if n == 0 and m == 0:
            break
      p = [ i+1 for i in range(n) ]
      np = n; a = 0
      while np > 1:
            a = (a+m-1)%len(p)
            p.pop(a)
            np -= 1
      print p[0]

Submission status: Accepted

Solution code:
while True:
    n, m = map(int, raw_input().split())
    if n==0 and m==0:
        break
    p = range(1,n+1); idx = n-1;
    while len(p)>1:
        idx = (idx + m)%len(p)
        p.pop(idx)
        idx = (idx + len(p) - 1)%len(p)
    print p[0]

Submission status: Accepted

Solution code:
while 1:
  n,m=map(int,raw_input().split())
  if n==0&m==0:break
  G=range(1,n+1)
  while n>1:
    if m%n==0:G=G[:n-1]
    else:G=G[m%n:]+G[:(m-1)%n]
    n-=1
  print G[0]

Submission status: Accepted

Solution code:
import sys
for s in sys.stdin:
  n,m=map(int,s.split())
  if n==0&m==0:break
  G=range(1,n+1)
  while n>1:
    if m%n==0:G=G[:n-1]
    else:G=G[m%n:]+G[:(m-1)%n]
    n-=1
  print G[0]

Submission status: Accepted

Solution code:
while 1:
  n,m = map(int,raw_input().split())
  if n==0 & m==0: break
  G = range(1, n+1)
  while n>1:
    if m%n == 0: G = G[:n-1]
    else: G = G[m % n:] + G[:(m-1) % n]
    n-=1
  print G[0]

Submission status: Accepted

Solution code:
while 1:
  n,m=map(int,raw_input().split())
  if n==0==m:break
  G=range(1,n+1)
  p=0
  while n>1:
    p=(p+m-1)%n
    G.pop(p)
    n-=1
  print G[0]

Submission status: Accepted

Solution code:
while 1:
  n,m=map(int,raw_input().split())
  if n==0==m:break
  p=0
  for i in range(2,n+1):p=(p+m)%i
  print p+1

Submission status: Accepted

Solution code:
while True:
    n, m = map(int, input().split())
    if n == 0:
        break

    lst = [1]*n
    a = 0
    b = 0
    c = 0
    while b < n-1:
        a += lst[c%n]
        if a == m:
            a = 0
            lst[c%n] = 0
            b +=1
        c += 1
    print(lst.index(1)+1)

Submission status: Accepted

Solution code:
while True :
    n, m = map(int, input().split())
    if n == 0 and m == 0 :
        break
    
    guest = []
    for i in range(n) :
        guest.append(i+1)
    potate = n - 1
    
    while True :
        potate += m
        while potate >= n :
            potate -= n
        n -= 1
        del guest[potate]
        potate -= 1
        
        if n == 1 :
            break
    print(*guest)

Submission status: Accepted

Solution code:
while 1:
    n, m = map(int, input().split())
    if n == 0:
        break

    s = [i for i in range(1, n + 1)]

    ind = n - 1
    while len(s) > 1:
        ind = (ind + m) % len(s)
        s.pop(ind)
        ind -= 1
    print(s[0])

Submission status: Accepted

Solution code:
while True:
  n,m=map(int,input().split())
  if n==0 and m==0:
    break
  P=[]
  for i in range(1,n+1):
    P.append(i)
  a=m-1
  for i in range(n-1):
    #print(P.pop(a))
    P.pop(a)
    a+=m
    while True:
      if a<=int(len(P)):
        break
      a=a-int(len(P))
      
    a=a-1
  print(P[0])

Submission status: Accepted

Solution code:
if __name__ == '__main__':

	while True:

		n,m = map(int,input().split())
		if n == 0 and m == 0:
			break

		A = [i for i in range(1,n+1)]

		ind = 0
		for _ in range(n-1):
			x = len(A)
			ind += m - 1
			if ind >= x:
				ind = ind % x
			A.pop(ind)

		print(A[0])

Submission status: Accepted

Solution code:
while 1:
    counter=0
    try:
        n,m=map(int,input().split())
        if n==0:break
        count=[i+1 for i in range(n)]
        while len(count)>1:
            for j in count:
                counter += 1
                if counter==m:
                    if j==count[-1]:
                        count.remove(j)
                        counter=0
                    else:
                        count.remove(j)
                        counter = 1
        print(*count)
    except:break

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,input().split())
    if n==m==0:break
    l=[i+1 for i in range(n)]
    pos=0
    for i in range(n-1):
        pos=(pos+m-1)%len(l)
        del l[pos]
    print(l[0])

Submission status: Accepted

Solution code:
while 1:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break

    number = list(range(1, n+1))
    cnt = 0
    for i in range(2, n+1):
        cnt = (cnt + m) % i

    print(cnt+1)

Submission status: Accepted

Solution code:
import sys
for n, m in (map(int, l.split()) for l in sys.stdin):
    if not n:
        break
    if m == 1:
        print(n)
        continue

    a = list(range(1, n+1))
    rem = 0

    while len(a) > m:
        d, _rem = divmod(len(a)+rem, m)
        for i in list(range(-rem+m-1, len(a), m))[::-1]:
            del a[i]
        rem = _rem

    while len(a) > 1:
        i = (m % len(a) - rem - 1) % len(a)
        del a[i]
        rem = len(a)-i

    print(a[0])

Submission status: Runtime Error

Solution code:
while 1:
    n,m=list(map(int,input().split()))
    if n==0 and m==0:break
    l=range(1,1+n)
    st=m-1
    while len(l)!=1:
        del l[st]
        st+=(m-1)
        while 1:
            if st>=len(l):
                st=st-len(l)
            if st<len(l):break  
    print(l[0])

Submission status: Runtime Error

Solution code:
def f(n,k):
    return 0 if n==0 else (f(n-1,k)+k)%n
while True:
    n,k=map(int,raw_input().strip().split())
    if (n,k)==(0,0):
        break
    print f(n,k)+1

Submission status: Runtime Error

Solution code:
while 1:
    n,m=map(int,raw_input())
    if n==0==m: break
    data=range(n)
    pos=m
    while len(data)!=1:
        del data[pos]
        pos+=m
        if pos>=len(data): pos-=len(data)

Submission status: Runtime Error

Solution code:
while True:
      n, m = map(int, raw_input().split())
      if n == 0 and m == 0:
            break
      p = [1 for i in range(n)]
      pn = n; count = 0
      while pn > 1:
            for i in range(n):
                  if p[i] == 1:
                        count += 1
                        if count == m:
                              p[i] = 0
                              pn -= 1
                              count = 0
      print p.index(1)+1

Submission status: Runtime Error

Solution code:
while True:
      n, m = map(int, raw_input().split())
      if n == 0 and m == 0:
            break
      p = [ 1 for i in range(n) ]
      pn = n; count = 0
      while pn > 1:
            for i in range(n):
                  if p[i] == 1:
                        count += 1
                        if count == m:
                              p[i] = 0
                              pn -= 1
                              count = 0
      print p.index(1)+1

Submission status: Runtime Error

Solution code:
while True:
      n, m = map(int, raw_input().split())
      if n == 0 and m == 0:
            break
      p = [ 1 for i in range(n) ]
      pn = n; count = 0; flag = 1
      while flag = 1:
            for i in range(n):
                  if p[i] == 1:
                        count += 1
                        if count == m:
                              p[i] = 0
                              count = 0
                              pn -= 1
                              if pn == 1:
                                    flag = 0
                                    break

      print p.index(1)+1