LINQ и ЕГЭ

@S3VDIT0 · Регистрация: 02.02.2017

Студворк — интернет-сервис помощи студентам

Здравствуйте! Решил одну задачу и дабы не городить кучу условий использовал LINQ, и тут встал вопрос, пройдет ли данный алгоритм все условия задачи(эффективность по памяти и времени)? Тянет ли моё решение на все 4 балла?

Описание задачи и условия к ней

В телевизионном танцевальном марафоне с определением победителя с помощью телезрителей после каждого тура объявляется sms-голосование, в котором зрители указывают наиболее понравившуюся им пару из максимум 16 пар, которые участвуют в проекте. Вам предлагается написать программу, которая будет обрабатывать результаты sms-голосования по данному вопросу. Результаты голосования получены в виде номеров пар (каждый элемент списка соответствует одному sms-сообщению).

Имеется набор данных, состоящий из целых чисел. Набор может быть очень большим.
Напишите программу для решения этой задачи.
Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.

Следует учитывать, что количество голосов в списке может быть очень велико. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество пришедших sms-сообщений N. В каждой из последующих N строк записан номер пары от 1 до 16.Пример входных данных:

4
2
16
3
2

Программа должна вывести список всех пар, встречающихся в списке, в порядке убывания (невозрастания) количества голосов, отданных за ту или иную пару, с указанием количества отданных за неё голосов. При этом каждая пара должна быть выведена ровно один раз вне зависимости от того, сколько раз она встречается в списке. Пример выходных данных для приведённого выше примера входных данных:

2 2
3 1
16 1

Решение

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using System;
using System.Linq;
using System.Collections.Generic;
 
public class Program
{
    public static void Main(String[] args)
    {
        List<Int16> Virables = new List<Int16>();
 
        for (Int32 i = Int32.Parse(Console.ReadLine()); i > 0; i--)
            Virables.Add(Int16.Parse(Console.ReadLine()));
 
        foreach (var Line in from g in Virables
                             group g by g into ng
                             orderby ng.Key
                             select new
                             {
                                 Count = ng.Count(),
                                 Key = ng.Key
                             })
            Console.WriteLine("{0} {1}", Line.Key, Line.Count);
    }
}

Благодарю за ответ!

@S3VDIT0 · 04.05.2017, 19:38 **[ТС]**

Aael, видимо в подобных задачах будет разумно использовать Dictionary, чем List и прочие коллекции. Или я не так понял?

@Aael · 04.05.2017, 19:52

S3VDIT0, да, т.к. на каждой итерации прийдется искать символ в списке, общее время работы будет:
O(число_символов * скорость_поиска) > O(число_символов)
У массива и хэш таблицы (внути словаря она и есть) скорость_поиска = 1

Добавлено через 3 минуты
*Поиск по массиву конечно же больше чем O(1), но в нашем случае мы сразу знаем номер нужно элемента - это код символа или его алфавитный нормер, ничего искать не нужно.

@S3VDIT0 · 04.05.2017, 20:09 **[ТС]**

Aael, теперь я понял, что мне следует почитать чуть больше о коллекциях и о способах оптимизации запросов(и LINQ вообщем), ибо мои решения(с использованием LINQ и коллекций) "немного" затратны по ресурсам...

Новые блоги и статьи Все статьи Все блоги /
Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .

@S3VDIT0 0 / 0 / 0 Регистрация: 02.02.2017 Сообщений: 10
	04.05.2017, 19:38 [ТС]
	Aael, видимо в подобных задачах будет разумно использовать Dictionary, чем List и прочие коллекции. Или я не так понял? 0

@Aael 964 / 485 / 241 Регистрация: 02.06.2016 Сообщений: 760
	04.05.2017, 19:52
	S3VDIT0, да, т.к. на каждой итерации прийдется искать символ в списке, общее время работы будет: O(число_символов * скорость_поиска) > O(число_символов) У массива и хэш таблицы (внути словаря она и есть) скорость_поиска = 1 Добавлено через 3 минуты *Поиск по массиву конечно же больше чем O(1), но в нашем случае мы сразу знаем номер нужно элемента - это код символа или его алфавитный нормер, ничего искать не нужно. 0

@S3VDIT0 0 / 0 / 0 Регистрация: 02.02.2017 Сообщений: 10
	04.05.2017, 20:09 [ТС]
	Aael, теперь я понял, что мне следует почитать чуть больше о коллекциях и о способах оптимизации запросов(и LINQ вообщем), ибо мои решения(с использованием LINQ и коллекций) "немного" затратны по ресурсам... 0