ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC, Центральный подрегион, Рыбинск, октябрь 2002

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

E. Массив

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Императивные языки программирования позволяют использовать как линейные, так и многомерные массивы. Например, в языке Паскаль для массива с именем X выражение array[0..2, 0..1, 0..3] объявляет трёхмерный массив со следующими ограничениями для каждой размерности: 0..2, 0..1, 0..3. (В этой задаче мы будем рассматривать только массивы, каждая размерность которых начинается с нуля, хотя в Паскале возможны и другие значения нижних границ размерностей.)
Можно определить порядок, в котором перечислены элементы массива. Этот порядок определяется принципом "чем правее индекс, тем быстрее он меняется". Это значит, что последний (самый правый) индекс проходит по всем возможным значениям, затем соседний с ним индекс (второй справа) меняет своё значение на 1, а последний индекс опять проходит по всем значениям между нижней и верхней границей, и так далее.
Пример. Элементы упомянутого выше массива перечисляются в следующем порядке: X[0,0,0], X[0,0,1], X[0,0,2], X[0,0,3], X[0,1,0], X[0,1,1], X[0,1,2], X[0,1,3], X[1,0,0], X[1,0,1], X[1,0,2], X[1,0,3], X[1,1,0], X[1,1,1], X[1,1,2], X[1,1,3], X[2,0,0], X[2,0,1], X[2,0,2], X[2,0,3], X[2,1,0], X[2,1,1], X[2,1,2], X[2,1,3].
Пусть n-мерный массив X описан как array[0..k1, 0..k2, …, 0..kn]. Теория говорит, что порядковый номер P любого элемента X[i1, i2, …, in] находится как P(i1, i2, …, in) = 1 + D1*i1 + D2*i2 + … + Dn*in, если используется порядок перечисления элементов, описанный выше. Здесь D1, D2, …, Dn — так называемые множители индексов.
Пример. Для рассматриваемого массива множители индексов равны D1 = 8, D2 = 4, D3 = 1. Поэтому, например, порядковый номер элемента X[1,0,3] будет равен P(1,0,3) = 1+8*1+4*0+1*3 = 12.
Ваша задача — найти неизвестные верхние границы размерностей массива (k1, k2, …, kn) по заданным множителям индексов D1, D2, …, Dn, и общему количеству элементов, содержащихся в массиве.

Исходные данные

Первая строка ввода содержит n — количество размерностей (1 ≤ n ≤ 20) и s — общее количество элементов массива (1 ≤ s < 231−1). Следующие n строк содержат множители индексов D1, D2, …, Dn.

Результат

Найдите верхние границы для каждой размерности массива в порядке: k1, k2, …, kn (0 < ki ≤ 1000). Числа должны быть разделены пробелами и/или переводами строк.

Пример

исходные данныерезультат
3 24
8
4
1
2 1 3
Источник задачи: Четвертьфинальные соревнования ACM ICPC 2002–2003 в центральном регионе России, Рыбинск, октябрь 2002
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1228. Массив