А170

Задача. Даны натуральные числа [latex]n, a_{1}, a_{2},\ldots, a_{n} (n\geq 4)[/latex]. Числа [latex]a_{1}, a_{2},\ldots , a_{n}[/latex] — это измеренные в сотых долях секунды результаты [latex]n[/latex] спортсменов в беге на [latex]100[/latex] м. Составить команду из четырёх лучших бегунов для участия в эстафете [latex]4\times100[/latex], т.е. указать одну из четверок натуральных чисел [latex]i, j, k, l[/latex], для которой [latex]1\leq i\leq j\leq k\leq l\leq n[/latex] и [latex]a_{i} + a_{j}+a_{k} + a_{l}[/latex] имеет наименьшее значение.

Тесты

      n         c Результаты бега спортсменов Номера спортсменов, избранных для команды Комментарий
6 3 11.77 12.34 12.14 11.15 11.16 11.40 4 5 6 Пройден
6 4 11.68 0 12.15 11.54 11.26 11.00 Введен отрицательный или нулевой результат Не пройден
6 2 11.68 -12.34 12.14 11.55 11.29 11.00 Введен отрицательный или нулевой результат Не пройден

 

Код программы на C++:

В этой задаче необходимо было найти номера лучших бегунов, для создания из них команды. Размер команды вводим сразу же после общего количества бегунов с клавиатуры. Для нахождения номеров бегунов нам потребуется функция mini, которая находит минимальный элемент массива и возвращает его значение, а также  функция team, вызывающая функцию mini. В функции team уже создан массив номеров бегунов, в который мы вначале  введем данные и отсортируем его по возрастанию. Также будем выводить номер этого минимального элемента на экран, прибавляя 1 (как бы считая бегунов с 1, а не с 0),  и присваивать этому (найденному) элементу массива какое-то большое значение для того, чтобы при следующей проверке программа не считала его минимальным элементом, а находила следующий минимальный.

В строках

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

В конечном итоге, применяем функцию team и получаем, собственно, ответ.

Код программы на Java

 

Related Images:

14 thoughts on “А170

    • Да, задача решится, но вряд ли решение будет оптимальным. Сложность алгоритма составляет O(c * n), что при c ~ n дает O(n^2). Существует возможность решить эту задачу за O(n).

    • Вы имеете в виду поразрядную сортировку? Я её только завтра расскажу на лекции
      И, кстати, для c = n задача становится тривиальной — в команду входят все. Ответ 1 2 3 … n

    • Нет, я имею в виду k-ю порядковую статистику.

    • И я написал c~ n. Например, c = n / 2. Для этого случая c-я порядковая статистика — самое то.

  1. — Не нужно вычислять размер команды случайным образом. Если уж Вы обобщили задачу (и это хорошо), то прочитайте размер команды из stdin.
    — Тесты (и решение) не соответствуют условию задачи. Вы не заметили, что номера в ответе должны идти по возрастанию.

    • Исправил. Вопрос в следующем: Стоит ли делать сортировку кучей, что было бы рациональнее или можно оставить в таком варианте?

  2. Сортировка кучей точно не нужна. Если сортировка, то поразрядная (цифровая). Она действительно была бы эффективней. Если использовать кучу, то только ее построение за О(n) и 4 поиска минимума (extract_min) за О(log(n)).
    Но стоит ли сортировать если нужно 4 раза найти минимум? Вы так и сделали.

    — Почему «номера минимального» не целое число?
    — 1000.0 в 26-й строке играет роль бесконечности? Сработает конечно если это не Паралимпийские игры. Может заменить максимумом массива или привлечь константу infinyty для типа double?
    — Зачем при вводе считать количество неверных данных? Причём до 1. Может лучше bool? Или сразу при нарушении напечатать сообщение об ошибке и сделать return.

    • Вчитался в условие.
      «измеренные в сотых долях секунды»
      Это скорее всего означает целое число сотых долей секунды.
      Можно понять иначе — с точностью до сотых. Хоть это и не так логично.
      Но Ваши тесты (11.778 12.345 12.145 11.154 11.169 11.401) не соответствуют ни первому, ни второму пониманию.

    • Исправил, спасибо за объяснение.

  3. Ума не приложу, почему я написал «зачтено» и не поставил оценку? Возможно из-за того, что в условии «даны натуральные числа», а в программе и тестах double.

    Расширенная задача, когда требуется найти c минимумов требует некоторой коллекции из C-элементов. При реализации на Java обычно используется структура PriorityQueue (очередь с приоритетами). Вставка элемента в очередь и извлечение максимального элемента выполняется за логарифмическое время. Программа будет очень простой:
    1. В цикле по i читаем элементы е из входного потока.
    2. Помещаем в PriorityQueue значение i с ключом е.
    3. Если в PriorityQueue стало больше чем с элементов извлекаем максимальный.

    Таким образом асимптотическая сложность будет порядка [latex]O\left(n \ln c \right)[/latex], а программа займет всего несколько строк.

Добавить комментарий