using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Lab_3._2
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Введите N");
            int N = int.Parse(Console.ReadLine());
            Console.WriteLine("Введите k");
            int k = int.Parse(Console.ReadLine());
            var watch = System.Diagnostics.Stopwatch.StartNew();
            watch.Start();
            Console.WriteLine(Flavy(N, k));
            watch.Stop();
            Console.WriteLine(watch.ElapsedMilliseconds + " мс - массив");
            watch.Restart();
            Console.WriteLine(ListFlavy(N, k));
            watch.Stop();
            Console.WriteLine(watch.ElapsedMilliseconds + " мс - связный список");
            Console.ReadLine();
        }


        static int Flavy(int N, int k)
        {
            bool[] arr = new bool[N];
            for (int i = 0; i < N; i++)
                arr[i] = true;
            int count = 1;
            int index = 0;
            int aliveCount = N;
            while (aliveCount > 1)
            {
                if (index == N)
                    index = 0;

                if (!arr[index])
                {
                    index++;
                    continue;
                }
                if (count == k && arr[index] == true)
                {
                    arr[index] = false;
                    count = 0;
                    aliveCount--;
                }
                index++;
                count++;
            }
            int alive = -1;
            for (int i = 0; i < N; i++)
                if (arr[i])
                    alive = i;
            return alive + 1;
        }

        static int ListFlavy(int N, int k)
        {
            LinkedList<int> items = new LinkedList<int>();
            for (int i = 1; i <= N; i++)
                items.AddLast(i);
            int count = 1;
            var node = items.First;
            while (items.Count > 1)
            {
                var next = node.Next;
                if (count == k)
                {
                    items.Remove(node);
                    count = 0;
                }
                count++;
                if (next == null)
                    node = items.First;
                else
                    node = next;
            }
            return items.First.Value;
        }
    }
}