Задача. Дана действительная квадратная матрица порядка [latex]n[/latex]. Получить [latex]x_{1}x_{n} + x_{2}x_{n-1}+ \cdots + x_{n}x_{1} [/latex], где[latex] x_k[/latex] — наибольшее значение элементов [latex]k[/latex]-й строки данной матрицы.
Суть задачи. Происходит заполнение многомерного массива. После этого в силу коммутативности умножения первая сумма полностью совпадает с последней, вторая — с предпоследней и т.д. Т.е. все слагаемые берутся дважды, кроме середины для нечётного [latex]n[/latex]. Это означает, что каждый максимум при вычислении суммы потребуется ровно один раз и никакой массив максимумов не нужен.
Оригинал решения
Решение на Try Haxe!
Тесты
| [latex]n[/latex] | Элементы | Результат |
|---|---|---|
| 2 | 1 2 3 4 | 16 |
| 3 | 1 2 3 4 5 6 7 8 9 |
1146 |
Код
|
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 |
static function main() { var n = Std.parseInt(Sys.stdin().readLine()); var array = new Array<Array<Float>>(); var sum:Float = 0; for (i in 0...n) { array[i] = new Array<Float>(); for (j in 0...n) { array[i][j] = Std.parseFloat(Sys.stdin().readLine()); } } for (i in 0...Std.int(((n + 1) / 2))) { sum += 2 * max(array[i]) * max(array[Std.int(n - i - 1)]); } trace(sum); } static function max(x:Array<Float>) : Float { var max:Float = x[0]; x[0] = 91; for (i in 1...x.length) { max = (max > x[i]) ? max : x[i]; } return max; } |