Рассмотрим прямоугольную таблицу размером n ´ m. Занумеруем строки таблицы числами от 1 до n, а столбцы – числами от 1 до m. Будем такую таблицу последовательно заполнять числами следующим образом.
Обозначим через aijчисло, стоящее на пересечении i-ой строки и j-ого столбца. Первая строка таблицы заполняется заданными числами – a11, a12, …, a1m. Затем заполняются строки с номерами от 2 до n. Число aij вычисляется как сумма всех чисел таблицы, находящихся в «треугольнике» над элементом aij. Все вычисления при этом выполняются по модулю r.
ai,j
Более точно, значение aij вычисляется по следующей формуле:
Например, если таблица состоит из трех строк и четырех столбцов, и первая строка состоит из чисел 2,3,4,5, а r = 40 то для этих исходных данных таблица будет выглядеть следующим образом (взятие по модулю показано только там, где оно приводит к изменению числа):
Требуется написать программу, которая по заданной первой строке таблицы (a11, a12, …, a1m), вычисляет последнюю строку, как описано выше.
Формат входных данных
Первая строка входного файла содержит числа n, m и r (2 ≤ n, m ≤ 2000, 2 ≤ r ≤ 109) – число строк и столбцов таблицы соответственно, а так же число, по модулю которого надо посчитать ответ. Следующая строка содержит m целых чисел – первую строку таблицы: a11, a12, …, a1m. Все a1i неотрицательны и не превосходят 109.
Формат выходных данных
В первой строке выходного файла необходимо вывести m чисел – последнюю строку таблицы: an1, an2, …, anm.
Примеры входных и выходных данных
table.in
2 3 10
1 2 3
table.out
3 6 5
Замечание о системе оценки
1) Решения, выдающие правильный ответ при n,m ≤ 50, будут оцениваться из 40 баллов.
2) Решения, выдающие правильный ответ при n,m ≤ 300, будут оцениваться из 60 баллов.
30 апреля 2008 в 13:04
Задача на самом деле не сложная, чисто идеяная….
21 марта 2008 в 17:03
о да=) А я в ней, кажись, идиотскую ошибку сделал – переполнение при подсчёте 2-ой строки
21 марта 2008 в 15:03
Задача 1. Таблица
Имя входного файла:
table.in
Имя выходного файла:
table.out
Максимальное время работы на одном тесте:
2 секунды
Максимальный объем используемой памяти:
64 мегабайта
Максимальная оценка
100 баллов
Рассмотрим прямоугольную таблицу размером n ´ m. Занумеруем строки таблицы числами от 1 до n, а столбцы – числами от 1 до m. Будем такую таблицу последовательно заполнять числами следующим образом.
Обозначим через aijчисло, стоящее на пересечении i-ой строки и j-ого столбца. Первая строка таблицы заполняется заданными числами – a11, a12, …, a1m. Затем заполняются строки с номерами от 2 до n. Число aij вычисляется как сумма всех чисел таблицы, находящихся в «треугольнике» над элементом aij. Все вычисления при этом выполняются по модулю r.
ai,j
Более точно, значение aij вычисляется по следующей формуле:
Например, если таблица состоит из трех строк и четырех столбцов, и первая строка состоит из чисел 2,3,4,5, а r = 40 то для этих исходных данных таблица будет выглядеть следующим образом (взятие по модулю показано только там, где оно приводит к изменению числа):
2
3
4
5
5 = 2 + 3
9 = 2 + 3 + 4
12 = 3 + 4 + 5
9 = 4 + 5
23 = 2 + 3 + 4 + 5 + 9
0 = (2 + 3 + 4 + 5 + 5 + 9 + 12) mod 40 = 40 mod 40
4 = (2 + 3 + 4 + 5 + 9 + 12 + 9) mod 40 = 44 mod 40
33 = 3 + 4 + 5 + 12 + 9
Требуется написать программу, которая по заданной первой строке таблицы (a11, a12, …, a1m), вычисляет последнюю строку, как описано выше.
Формат входных данных
Первая строка входного файла содержит числа n, m и r (2 ≤ n, m ≤ 2000, 2 ≤ r ≤ 109) – число строк и столбцов таблицы соответственно, а так же число, по модулю которого надо посчитать ответ. Следующая строка содержит m целых чисел – первую строку таблицы: a11, a12, …, a1m. Все a1i неотрицательны и не превосходят 109.
Формат выходных данных
В первой строке выходного файла необходимо вывести m чисел – последнюю строку таблицы: an1, an2, …, anm.
Примеры входных и выходных данных
table.in
2 3 10
1 2 3
table.out
3 6 5
Замечание о системе оценки
1) Решения, выдающие правильный ответ при n,m ≤ 50, будут оцениваться из 40 баллов.
2) Решения, выдающие правильный ответ при n,m ≤ 300, будут оцениваться из 60 баллов.