# 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

Source: codewars | Difficulty: EASY
Tags: Fundamentals

Starter code: def find_last(n, m):
	

Solutions:
def find_last(n, m):
	(li, start) = ([[0, i + 1] for i in range(n)], 0)
	while len(li) != 1:
		(prev, l_) = (li[start][1], len(li))
		for k in range(m):
			li[start][0] += 1
			start = (start + 1) % l_
		if m < len(li):
			k = start
			while li[k][1] != prev:
				li[k][0] += 2
				k = (k + 1) % l_
		li[start][0] += li.pop((start - 1) % l_)[0]
		start = [(start - 1) % l_, start][start == 0]
	return tuple(li[0][::-1])


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
		elif 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
			elif 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)