1228. Массив

Рассмотрим n - арный массив Х, объявленный как array[0..k₁, 0..k₂, … , 0..k_n]. Порядок P элемента X[i₁, i₂, …, i_n] вычисляется по формуле P(i₁, i₂, …, i_n) = 1 + d₁ * i₁ + d₂ * i₂ + … + d_n * i_n. Числа d₁, d₂, …, d_n называются индексными множителями.

Рассмотрим массив X[0..2, 0..1, 0..3] и его индексные множители d₁ = 8, d₂ = 4, d₃ = 1. Порядок элемента X[1, 0, 3] равен P(1, 0, 3) = 1 + 8*1 + 4*0 + 1*3 = 13..

В задаче необходимо найти верхнюю границу для каждой размерности (k₁, k₂, …, k_n) по заданным индексным множителям и общим количеством элементов в массиве s.

Вход. Первая строка содержит размерность массива n (1 £ n £ 20) и общее число элементов s (1 £ s £ 2³¹ – 1) в массиве. Следующие n строк содержат индексные множители d₁, d₂, …, d_n.

Выход. Определить верхнюю границу для каждой размерности в порядке k₁, k₂, …, k_n (0 < k_i £ 1000). Выводимые размерности разделять пробелами или символами CR/LF.

Пример входа

3 24

8

4

1

Пример выхода

2 1 3

РЕШЕНИЕ

элементарные вычисления

Анализ алгоритма

Если величина текущего индексного множителя равна d_i, а текущее число элементов равно s, то граница i - ой размерности может быть максимум s / d_i. Оставшиеся s % d_i элементов следует располагать в следующих размерностях.

Реализация алгоритма

В массиве x храним входные индексные множители, в массиве k вычисляем верхнюю границу размерностей.

int x[20],k[20];

Читаем входные данные, заносим индексные множители в массив x.

scanf("%d %d",&n,&s);

for(i=0;i<n;i++) scanf("%d",&x[i]);

Вычисляем верхние границы размерностей и заносим их в массив k. Затем выводим их.

s--;

for(i=0;i<n;i++)

k[i] = s / x[i],s %= x[i];

for(i=0;i<n;i++) printf("%d ",k[i]); printf("\n");