Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

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


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


Задача A. Кольцевые гонки
Имя входного файла: 1.txt
Имя выходного файла: 2.txt
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт


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


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


Формат входных данных

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


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


Формат выходных данных

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


Примеры
Входной файл 1.txt Выходной файл 2.txt
3 4
1 3 3 1
3
3 5
1 1 2 3 1
1

Замечание

Система оценки: Решения, верно работающие при 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% тестов. Тесты можно скачать Здесь.



Счастливого программирования!


19-09-2018 в 15:43:01





Похожая статья:

Задача по информатике на собеседовании в IT-компанию. ''Размен монет''

Сегодня решим задачу по информатике, которую часто дают на собеседован...

Категория: Алгоритмы  Подкатегория: Задачи
Дата: 15-01-2018 в 16:47:34 0



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:


Последние
видео:



ЕГЭ по информатике. Задание 1
Присылайте ваши задачи


Подготовка к
ОГЭ


Подготовка к ОГЭ по информатике


Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy