Правила игры. В игру играет два человека, которые ходят по очереди. На столе лежит 50 спичек. Первым ходом можно взять одну или две спички. На каждом последующем ходу игрок может взять любое число спичек, не меньшее 1 и не более чем в два раза, чем взял предыдущий игрок. Тот, кто возьмет последнюю спичку, выиграл.
Вот пример партии:
Было – 50 спичек
1 игрок взял 1 спичку, осталось 49
2 игрок взял 2 спички, осталось 47
1 игрок взял 3 спички, осталось 44
2 игрок взял 6 спичек, осталось 38
1 игрок взял 11 спичек, осталось 27
2 игрок взял 8 спичек, осталось 19
1 игрок взял 3 спички, осталось 16
2 игрок взял 5 спичек, осталось 11
1 игрок взял 3 спички, осталось 8
2 игрок взял 2 спички, осталось 6
1 игрок взял 1 спичку, осталось 5
2 игрок взял 1 спичку, осталось 4
1 игрок взял 1 спичку, осталось 3
2 игрок взял 1 спичку, осталось 2
1 игрок взял 2 спички, осталось 0
Протокол такой партии можно записать в следующем виде:
1 50
1 49
2 47
3 44
6 38
11 27
8 19
3 16
5 11
3 8
2 6
1 5
1 4
1 3
1 2
2 0
Напишите программу, которая играет в эту игру. Программа получает на вход два числа: количество спичек, которое взял предыдущих игрок \(d\) и количество спичек на столе \(n\). Числа натуральные, не превосходят 100. Программа должна вывести два числа: количество взятых спичек \(d_1\) и количество оставшихся спичек \(n_1\), при этом \(1\le d_1\le 2d\), \(n_1=n-d_1\), \(n_1 \le 0\).
Пример
| 1 50 | 1 49 |
| 6 38 | 11 27 |
| 1 2 | 2 0 |
Программа должна тратить не более 1 секунды на ход. Постарайтесь придумать наилучшую стратегию для этой игры.