Олимпиадная задача по информатике. Кольцевые гонки.

Всем, привет! Сегодня отличная статья по информатике. Разбираем олимпиадную задачу из 11 класса.

Участники кольцевых гонок на одноколесных велосипедах нумеруются числами от 1 до N. Им предстоит проехать K кругов и победителем является тот, кто проехал их раньше всех. Участники стартуют одновременно с некоторой линии, которая называется конец круга. Каждый раз, когда участник пересекает эту линию, его номер фиксируется автоматической системой с высокой точностью (то есть два участника не могут пересечь эту линию одновременно). После прохождения K кругов эта же линия является финишной прямой. К сожалению, некоторые участники сходят с дистанции и проезжают меньшее количество кругов.

Организаторы соревнования забыли число K и стесняются спросить его у участников. Помогите организаторам определить победителя соревнования, используя только записи с системы фиксации. Гарантируется, что хотя бы один из участников преодолел необходимые K кругов и никто из участников не проехал более K кругов. Первая фиксация номера участника происходит после прохождения первого круга.

В первой строке задаются целые числа N и M (1 ⩽ N ⩽ 100, 1 ⩽ M ⩽ 10000) — количество участников соревнования и записей с системы фиксации соответственно

Во второй строке задается M целых чисел от 1 до N – номера участников в том порядке, как они фиксировались системой.

Выведите одно число — номер победителя.

Система оценки: Решения, верно работающие при N ⩽ 10, M ⩽ 20 будут получать не менее 50% баллов.

В первом примере участники 1 и 3 проехали 2 круга, но после последнего круга впереди был участник номер 3, поэтому он и является победителем. Участник номер 2 сошёл с дистанции на первом круге.

Во втором примере участник 1 единственный проехал 3 круга и является победителем. Участники 2 и 3 сошли на втором круге.

Решать олимпиаду по информатике советую на языке C#. Разбираемся с условием задачи.

Первое число N, это количество участников. Второе число M - это количество замеров в системе, и это число совпадает с количеством чисел в нижней строчке. Таким образом, сразу отметим, что оно нам дано для удобства, потому что количество чисел в нижней строчке мы могли посчитать и сами. Так же сразу отметим, дано много лишней информации, чтобы запутать участника олимпиады: "на одноколесных велосипедах", "стесняются спросить его у участников". Таким образом, нам нужно чётко сфокусироваться на значимой информации и отсекать шелуху.

Считаем из файла все числа с помощью команд (Добавив пространство имён System.IO; ):

string s = File.ReadAllText("1.txt");
          
int[] nums = s
     .Split(new char[] { ' ', '\n' }, StringSplitOptions.RemoveEmptyEntries)
     .Select(n => int.Parse(n))
     .ToArray();

Теперь едем словно на мерседесе! В целочисленном массиве nums у нас все числа. Если взять первый пример, в нулевом элементе будет nums[0] - 3, в первом элементе nums[1] - 4, во втором nums[2] - 1, в третьем nums[3] - 3, в четвёртом nums[4] - 3 и т.д. Т.е. все числа у нас в кармане.

Заведём массив arr, чтобы был элемент массива для каждого участника.

int N = nums[0]; // Количество участников соревнования.
int M = nums[1]; // Количество записей системы.
int[] arr = new int[N+1];

У нас N участников, но мы заведём для удобства N+1 элементов массива, чтобы первому участнику соответствовал первый элемент, а не нулевой.

Далее, задача чем-то напоминает нахождение максимального элемента в массиве. Мы должны посчитать сколько раз каждый участник пересек черту. Для первого участника, значение будет хранится в arr[1], для второго в arr[2] и т.д. Плюс нам нужно найти самого первого участника, у которого будет самое большое количество пересечений системы фиксирования.

int max = 0;
int k = 0;
int i = 0;

for (i=2; i<=M; i++)
{
   arr[nums[i]]++;

   if (arr[nums[i]]>max)
   {
      max = arr[nums[i]];
      k = i;
   }
}

Победитель определяется элементом nums[k]. Полный текст программы:

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

namespace ConsoleApp5
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = File.ReadAllText("1.txt");
          
            int[] nums = s
                .Split(new char[] { ' ', '\n' }, StringSplitOptions.RemoveEmptyEntries)
                .Select(n => int.Parse(n))
                .ToArray();

            int N = nums[0]; // Количество участников соревнования.
            int M = nums[1]; // Количество записей системы.
            int[] arr = new int[N+1];
            int max = 0;
            int k = 0;
            int i = 0;

            for (i=2; i<=M; i++)
            {
                arr[nums[i]]++;

                if (arr[nums[i]]>max)
                {
                    max = arr[nums[i]];
                    k = i;
                }
            }

            File.WriteAllText("2.txt", Convert.ToString(nums[k]));
        }
    }
}

Программа прошла 100% тестов. Тесты можно скачать Здесь.