singlepost

Задача №1 << На главную или назад  

сабж

3 ответов в теме “Задача №1”

  1. 3
    Андрей Гейн ответил:

    Задача на самом деле не сложная, чисто идеяная….

  2. 2
    Dispatch Level ответил:

    о да=) А я в ней, кажись, идиотскую ошибку сделал – переполнение при подсчёте 2-ой строки :)

  3. 1
    Макар Красноперов ответил:

    Задача 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 баллов.

Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.