1228. МассивОграничение времени: 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
|
|