Недавно Оле подарили $%n$% коробок цветных карандашей, в $%i$%-й коробке $%a_i$% карандашей. К сожалению, обнаружилось, что для всех карандашей нужно выбрать цвет самой. У Оли есть любимые цвета, поэтому для каждого карандаша Оля может выбрать только один из $%k$% любимых цветов. Более того, Оля хочет, чтобы для каждого цвета и для любых двух коробок с карандашами количества карандашей этого цвета отличались бы не более, чем на один. Оля просит вас о помощи, вам нужно сказать, возможно ли это и если да, то предложить ему подходящую покраску. Если же решения не существует, то вам нужно это доказать. Асимптотика: $%max (a_i * n)$%, i - целое, от 1 до n.

Может кто-то подсказать в каком направлении думать? Непонятно в каком направлении .

задан 13 Сен 17:03

изменен 13 Сен 18:34

Абсолютно согласен с @falcao — формулировка ещё та. Надумано, и не понятно откуда могла появиться, не вижу модели.

(13 Сен 22:21) FEBUS
10|600 символов нужно символов осталось
1

Я не уверен в правильности своей трактовки задачи, потому что получается как-то подозрительно просто. Помимо всего прочего, сам сюжет представляется несколько несуразным с точки зрения здравого смысла: если карандаши (как реальные предметы) уже подарены, то как можно поменять их цвета? Если, конечно, речь не идёт о каком-нибудь "волшебстве" :)

Удобнее считать, что карандаши решили подарить, и указали их количество в каждой коробке. И тогда нужно сформировать заказ, указав количество карандашей каждого из k цветов по коробкам.

Это значит, что нужно сформировать матрицу с целыми неотрицательными элементами b[i,j] размером nxk, где сумма чисел i-й строки задана и равна a[i]. При этом требуется, чтобы числа j-го столбца принимали не более двух значений вида x[j] и x[j]+1.

Понятно, что x[1]+...+x[k]<=a[i]<=x[1]+...+x[k]+k при всех i. Тем самым, max(a[i])-min(a[i])<=k. Такое условие легко проверяется. Оно при этом является достаточным: полагаем s=x[1]+...+x[n], и в первом столбце матрицы полагаем (временно) все числа равными s. Далее по всем i рассматриваем число a[i]-s<=k, и прибавляем по единице к каждому из чисел i-й строки для первых a[i]-s столбцов.

Задача выглядит по всем критериям очень странной и искусственной.

ссылка

отвечен 13 Сен 22:13

1

@falcao: насчет формулирвоки абсолютно согласен. Полное фуфло. Чуть мозг не сломал пока пытался понять. Спасибо за ответ) Сечас буду изучать

(13 Сен 22:27) Konon
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,476
×1,296
×154
×48

задан
13 Сен 17:03

показан
64 раза

обновлен
13 Сен 22:27

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru