# Task

The game starts with `n` people standing in a circle. The presenter counts `m` people starting with the first one, and gives `1` coin to each of them. The rest of the players receive `2` coins each. After that, the last person who received `1` coin leaves the circle, giving everything he had to the next participant (who will also be considered "the first in the circle" in the next round). This process continues until only 1 person remains.

Determine the `number` of this person and how many `coins` he has at the end of the game.

The result should be a pair of values in the format: `[person, coins]`.

## Example:

```
n = 8, m = 3

People
1 2 3      1 2 ∙      1 2 ∙      ∙ 2 ∙       ∙  2 ∙       ∙ ∙  ∙       ∙ ∙  ∙
8   4  =>  8   4  =>  8   4  =>  8   4  =>   8    4  =>   8    4  =>   ∙    4  =>  7
7 6 5      7 6 5      7 ∙ 5      7 ∙ 5       7  ∙ ∙       7 ∙  ∙       7 ∙  ∙

Coins
0 0 0      1 1 ∙      3 3 ∙      ∙ 9 ∙       ∙ 10 ∙       ∙ ∙  ∙       ∙ ∙  ∙   
0   0  =>  2   3  =>  4   4  =>  5   6  =>   7    7  =>   8   20  =>   ∙   30  =>  51
0 0 0      2 2 2      7 ∙ 3      8 ∙ 5      16 ∙  ∙      17 ∙  ∙      18 ∙  ∙ 
```

## Notes:

* The presenter can do several full circles during one counting.
* In this case, the same person will receive `1` coin multiple times, i.e. no matter how many people are left in the circle, at least `m` coins will always be distributed among the participants during the round.
* If a person had already received `1` coin (possibly multiple times), he won't receive any additional `2` coins **at once(!)** during that round.
* People are counted starting with `1`.
* `m` can be **bigger** than `n` at start

Difficulty: introductory

Starter code:

def find_last(n, m):
	

Solutions:
def find_last(n, m):
    li, start = [[0, i + 1] for i in range(n)], 0      # form list of circle with numbers
    while len(li) != 1:
        prev, l_ = li[start][1], len(li)               # starting point and length of circle
        for k in range(m):                             # adding 1 to first m players in circle             
            li[start][0] += 1
            start = (start + 1) % l_

        if m < len(li):                                # if there's anyone left from adding 1 if so..
            k = start
            while li[k][1] != prev:                    # adding 2 to remaining players
                li[k][0] += 2
                k = (k + 1) % l_
                
        li[start][0] += li.pop((start - 1) % l_)[0]    # add last person who receives last 1 coin to next person
        start = [(start - 1) % l_ ,start][start==0]
    return tuple(li[0][::-1])                          # return last person with score and original number

def find_last(n, m):
    num = 0
    for i in range(2, n+1): num = (num + m) % i
    return num+1, n*(n+1)+m*(m-2)-n*m

from collections import deque

def person(n, m):
    q = deque(range(n))
    for i in range(n):
        q.rotate(1-m)
        x = q.popleft()
    return x + 1

def coins(n, m):
    return sum(m + max(i-m, 0) * 2 for i in range(n, 1, -1))

def find_last(n, m):
    return person(n, m), coins(n, m)

class Cycle:
    def __init__(self, n):
        self.length = n
        self.h = current = node = Node(1)
        for i in range(2, n+1):
            current.next = Node(i)
            current = current.next
        current.next = node
        
    def minimize(self, n):
        current = Node(0)
        current.next = self.h
        while self.length > 1:
            for i in range((n - 1) % self.length):
                current = current.next
            current.next = current.next.next
            self.length -= 1
            pass
        return current.next.n
    
class Node:
    def __init__(self, n):
        self.n = n
        self.next = None
    
def find_last(n, m):
    x = n - m
    return (Cycle(n).minimize(m), (1 + x) * x + (n - 1) * m)

def find_last(n, m):
    people = list(range(1, n + 1))
    coins = 0
    for staying in range(n, 1, -1):
        if staying >= m:
            people = people[m:] + people[:m - 1]
            coins += m + (staying - m) * 2
        else:
            last = (m % staying - 1) % staying
            people = people[last + 1:] + people[:last]
            coins += m
    return people[0], coins

def find_last(n, m):
    pp=list(range(1,n+1))
    p=0
    while len(pp)>1:
        p=(p+m-1)%len(pp)
        del pp[p]
    s=(n-1)*m+(n-m)*(n-m+1)
    return pp[0],s

def next_man(people, k):
    while True:
        if people[k] != '.':
            return k
        else:
            if k + 1 >= len(people):
                k = 0
            else:
                k += 1


def find_last(n, m):
    people = [0 for i in range(n)]
    lost_people = n
    k = 0

    while lost_people > 1:

        counter = 0
        while counter < m:
            if people[k] != '.':
                people[k] += 1
                counter += 1
                if k + 1 >= n:
                    k = 0
                else:
                    k += 1
            else:
                if k + 1 >= n:
                    k = 0
                else:
                    k += 1
        if k - 1 < 0:
            sub_money = people[-1]
            people[-1] = '.'
        else:
            sub_money = people[k - 1]
            people[k - 1] = '.'
        k = next_man(people, k)
        people[k] += sub_money
        lost_people -= 1

        whom2 = lost_people - m + 1
        flag = k
        if whom2 > 0:
            for i in range(whom2):
                people[k] += 2
                if k + 1 >= n:
                    k = 0
                else:
                    k += 1
                k = next_man(people, k)
        k = flag

    return k+1, people[k]


def find_last(n, m):
    num, i, L = 0, 0, [0]*n
    ni = lambda i: (i+1)%len(L)
    pi = lambda i: (i-1)%len(L)
    for v in range(2, n+1):
        num = (num + m) % v
        seen = set(range(len(L)))
        for _ in range(m):
            L[i] += 1
            seen.discard(i)
            i = ni(i)
        for x in seen: L[x] += 2
        j = pi(i)
        L[i] += L[j]
        del L[j]
        i = pi(i)
    return num+1, L[0]

from collections import deque

def find_last(n, m):
    circle = deque(range(1, n+1))
    coin = 0
    for _ in range(1, n):
        coin += m if len(circle) <= m else (2 * len(circle)) - m
        circle.rotate(-(m-1))
        circle.popleft()
    return (circle[0], coin)