Даша: Спасибо:3
31-05-2023
Читать статью
Санечка: я ничего не учила) но буду надеятся что ..
30-05-2023
Мейнер Сяо: Удачи всем сегодня на экзамене ;)..
Всем, привет! Сегодня отличная статья по информатике. Разбираем олимпиадную задачу из 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% тестов. Тесты можно скачать Здесь.