Задача
На доске выписаны $n$ целых чисел. Все они пронумерованы от $1$ до $n$. Разрешается выбрать два произвольных числа, вытереть оба с доски и написать новое число, равное их среднему арифметическому. Новое число получает номер $n + 1$. После этого снова выбираются два числа и вместо них записывается их среднее арифметическое, которому дается номер $n + 2$ и т.д. Так продолжается до тех пор, пока на доске не останется только одно число. Чем больше будет это число, тем более успешной считается последовательность действий.
Определите порядок действий, который приводит к максимально возможному числу в конце.
Входные данные
В первой строке записано целое число $n$ $(1 \leq n \leq 10^5)$. Во второй строке задаются $n$ целых чисел, которые были первоначально записаны на доске. Все числа лежат в диапазоне от $-10000$ до $10000$.
Выходные данные
Вывести количество способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний.
Тесты
| Входные данные | Выходные данные |
| $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 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); TreeMap<Double, String> map = new TreeMap<>(); int n = in.nextInt(); for(int i = 1; i <= n; i++) { double item = in.nextDouble(); if(map.get(item) == null) map.put(item, Integer.toString(i)); else { String str = map.get(item); str += Integer.toString(i); map.put(item, str); } } while(map.size() != 1) { double x = map.firstKey(); String strX = map.get(x); char numx = '0'; if(strX.length() == 1) { map.remove(x); numx = strX.charAt(0); } else { numx = strX.charAt(0); map.put(x, strX.substring(1)); } double y = map.firstKey(); String strY = map.get(y); char numy = '0'; if(strY.length() == 1) { map.remove(y); numy = strY.charAt(0); } else { numy = strY.charAt(0); map.put(y, strY.substring(1)); } int numXInt = Character.getNumericValue(numx); int numYInt = Character.getNumericValue(numy); System.out.println(Math.min(numXInt, numYInt) + " " + Math.max(numXInt, numYInt)); double newKey = (x + y) / 2; if(map.get(newKey) == null) map.put(newKey, Integer.toString(++n)); else { String str = map.get(newKey); str += Integer.toString(++n); map.put(newKey, str); } } } } |
Решение задачи
Для решения задачи необходимо использовать multimap, которого не в языке программирования Java. Для решения данной задачи числа на доске будут ключами, а их номера будем записывать в строку. Для задания такого «multimap» будем считывать с входного потока числа и смотреть есть ли в нашей карте такой ключ, если есть, то к строке добавляем ещё символ справа, если нет, то за в строку вставляем номер числа. Затем в цикле, пока не один элемент в «multimap» будем выбирать первые два элемента. Для выбираем первый ключ с помощью функции map.firstKey(), находим значение по ключу, проверяем длину полученной строки, если она равна $1$, то запоминаем символ строки и удаляем элемент с «multimap», иначе запоминаем первый символ строки и удаляем его из строки, записывая в «multimap» элемент с измененной строкой. Аналогично получаем следующее значение. Переводим символы в числа и выводим их номера элементов, которые были изъяты из «multimap» и находим среднее число. Добавляем в «multimap» пару, где первое значение — это найденное средние двух чисел, а второе — номер(добавление данного элемента осуществляется аналогично заполнению, т.е. если ключ уже есть в «multimap», то добавляем к значению справа номер). В конце концов мы получим, что в «multimap» будет всего одна пара и цикл остановит свою работу. Задача решена. Однако она не проходит по времени.
Ссылки
Условие задачи на e-olymp
Код решения на ideone.com