4
|
Задача 287. Cумма вдоль диагоналейпостоянный адрес задачи: http://www.diofant.ru/problem/673/показать код для вставки на свой сайт >> |
Задачу решили:
9
всего попыток:
19
поделиться задачей:
|
|
|
Задача опубликована:
07.06.10 08:00
Прислал:
mikev
Источник:
Проект "Эйлер" (http://projecteuler.net)
Вес:
1
сложность:
1
класс:
8-10
баллы: 100
Темы:
арифметика
|
|
|
Посмотрите на таблицу. Легко проверить, что максимальная сумма чисел, стоящих подряд вдоль одного из диагональных направлений, равна 16 (= 8 + 7 + 1).
| -2 | 5 | 3 | 2 |
| 9 | -6 | 5 | 1 |
| 3 | 2 | 7 | 3 |
| -1 | 8 | -4 | 8 |
Давайте теперь рассмотрим ту же задачу для таблицы большего размера. Для этого будем использовать генератор случайных чисел Фибоначчи с запаздываниями:
Для 1≤k≤55, sk = [100003 - 200003·k + 300007·k3)] (mod 1000000) - 500000.
Для 56≤k≤4000000, sk = [sk-24 +sk-55 + 1000000] (mod 1000000) - 500000.
(Здесь x(mod y) означает остаток от деления x на y).
Например, s10 = -393027 и s100 = 86613.
Заполним при помощи первых четырех миллионов чисел этого генератора таблицу 2000×2000. Заполнять таблицу будем последовательно, строка за строкой.
Найдите максимальную сумму чисел, стоящих подряд вдоль какого-либо из диагональных направлений в получившейся таблице.
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Обсуждение
Правила >>
Правильно ли я понял, что числа не обязаны занимать всю диагональ, а могут занимать только непрерывную ЧАСТЬ диагонали?
Да, верно, непрерывную часть отрезка, параллельного одной из диагоналей.