Модуль: 11.2А - Решение заданий методом перебора (задание 27А)


Задача

9 /9


Как написать переборное решение к задаче типа 27


Как правильно написать "переборбоное решение" к задаче?
Вначале надо определиться
  • зачем нужно "переборное решение"
  • какие требования надо предъявить к "переборному решению"
Ваша задача
  1. Ответить на поставленные вопросы
  2. Написать  идеальное "переборное решение" для указанной задачи (полные комментарии)
  3. "Сократить" его до "экзаменнационного" варианта (без комментариев)
  4. Сделать "разумную" модификацию под "оптимальное" решение (можно поэтапно)
Для этого:
  • скопируйте тетрадь
  • напишите свой ответ
  • ссылку на тетрадь прикрепите в комментариях 

Условие задания (задание 51149) 
По мотивам задачи: 
Пробник ИМЦ СПб (Уровень: E) (kompege =6638, silvertests=51149
Решение этой задачи возможно "простым переборным решением"
Задание выполняется с использованием прилагаемых файлов.

В некоторой стране построен радиотелескоп. Антенны телескопа расположены вдоль шоссе. 
Номер антенны соответствует километровой отметке от начала шоссе. Каждая антенна в сутки принимает
определённое количество сигналов, формирует их в пакеты и отправляет пакеты в Центр обработки.
Центр обработки разместили рядом с одной из антенн так, чтобы количество энергии,
расходуемой на передачу данных от всех антенн, было минимальным.

Количество энергии, необходимое для передачи всех пакетов с данными, равно
произведению расстояния от антенны до центре обработки на количество передаваемых пакетов с данными.
Определите номер антенны, рядом с которой следует разместить центр обработки данных.
Если таких номеров несколько, укажите наименьший из них.

Пример входного файла: Ответ Пояснение

6
1 100
3 250
8 7
10 4
15 1
31 160

3 Для случая, когда центр обработки данных размещён около 3-й антенны,
суммарную энергию, необходимую для передачи данных,
можно оценить как
2·100 + 5·7 + 7·4 + 12·1 + 28·160 = 4755

Входные данные:

Дан входной файла (27A_6638.txt), который содержит:

  • в первой строке число: количество антенн N (1 ≤ N ≤ 1000).
  • Каждая из следующих N строк содержит два натуральных числа – номер антенны
    и количество пакетов, отправленных антенной в Центром обработки.
    Антенны нумеруются в порядке их расположения вдоль шоссе, начиная с нулевой отметки.

В ответе укажите два числа (в одной строке через пробел) : сначала искомый номер антенны, затем суммарную энергию.

Прикрепленные файлы
27A_6638.txt
27B_6638.txt

time 1000 ms
memory 256 Mb

Комментарий учителя