Задача
На доске выписаны $n$ целых чисел. Все они пронумерованы от $1$ до $n.$ Разрешается выбрать два произвольных числа, вытереть оба с доски и написать новое число, равное их среднему арифметическому. Новое число получает номер $n + 1.$ После этого снова выбираются два числа и вместо них записывается их среднее арифметическое, которому дается номер $n + 2$ и т.д. Так продолжается до тех пор, пока на доске не останется только одно число. Чем больше будет это число, тем более успешной считается последовательность действий.
Определите порядок действий, который приводит к максимально возможному числу в конце.
Входные данные
В первой строке записано целое число $n$ $(1 \leqslant n \leqslant 10^5).$ Во второй строке задаются $n$ целых чисел, которые были первоначально записаны на доске. Все числа лежат в диапазоне от $-10000$ до $10000.$
Выходные данные
Выведите $n — 1$ строку, в каждой из которых должны быть записаны по два целых числа, определяющие номера тех чисел, которые выбираются на соответствующем шаге.
Тесты
| Входные данные | Выходные данные |
| $3$ $7\;2\;4$ |
$2\;3$ $1\;4$ |
| $4$ $6\;2\;7\;1$ |
$2\;4$ $1\;5$ $3\;6$ |
| $4$ $12\;4\;7\;2$ |
$2\;4$ $3\;5$ $1\;6$ |
| $5$ $234\;2\;5\;54\;5$ |
$2\;3$ $5\;6$ $4\;7$ $1\;8$ |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> #include <map> using namespace std; int main() { multimap <double,int> multimap; int n; cin >> n; int element; for(int i = 1; i <= n; i++) { cin >> element; multimap.insert(pair<double,int>(element, i)); } while(multimap.size() != 1) { pair<double,int> x = *multimap.begin(); multimap.erase(multimap.begin()); pair<double,int> y = *multimap.begin(); multimap.erase(multimap.begin()); cout << min(x.second, y.second) << " " << max(x.second, y.second) << endl; multimap.insert(pair<double,int>((x.first + y.first) / 2, ++n)); } return 0; } |
Решение задачи
Для решения задачи создаем multimap, затем циклом вводим туда пары, где первое значение — это число с потока, а второе — его номер. После этого мы сохраняем первые два значения из multimap, выводим их номера и находим среднее число. Добавляем в multimap пару, где первое значение — это найденное средние двух чисел, а второе — номер. В конце концов мы получим, что в multimap будет всего одна пара и цикл остановит свою работу. Задача решена.
Ссылки
Условие задачи на e-olymp
Код решения на ideone.com