7
|
Задача 837. Упорядоченные строкипостоянный адрес задачи: http://www.diofant.ru/problem/2508/показать код для вставки на свой сайт >> |
Задачу решили:
40
всего попыток:
62
поделиться задачей:
|
|
|
Задача опубликована:
02.01.13 08:00
Прислал:
georgp
Вес:
1
сложность:
1
класс:
8-10
баллы: 100
Темы:
комбинаторика
|
|
Лучшее решение:
Timur
|
Пусть задана строка состоящая из 2m неотрицательных целых чисел, удовлетворяющих условию:
1) числа в строке не могут возрастать;
2) каждое число не превосходит m;
3) нулей может быть любое количество, не превосходящее 2m, остальные числа могут иметь только одну пару.
Пример для m=4:
(4,3,3,1,0,0,0,0), (4,3,2,1,1,0,0,0)
Найти количество таких строк при m=10.
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Обсуждение
Правила >>
Что означает "остальные числа могут иметь только одну пару"?
А если чисел всего 2m, то понятно, что и нулей среди них не более 2m.
Каждое число 0<n<m+1 входит в строку не более двух раз.
Спасибо! А все-таки сколько может быть нулей? Не более m или не более 2m?
Еще раз спасибо! И последний вопрос. Числа не могут возрастать ни на каком отрезке? Т.е. не может быть для m=2 : (1,2,0,0)?
Не может. Монотонно убывает. :) Всегда пожалуйста. Можно не плюсовать.
Три любопытные особенности задачи.
1. Просто ошибка - нулей вместo 2m могло быть m.
2. Примеры, которые должны служить более ясному пониманию задачи, подобраны не ахти и свою функцию выполняют не лучшим образом.
3. Рассматриваются не неубывающие, а невозрастающие последовательности - что, несколько, менее привычно и естественно.
Решал именно предложенную задачу, в которой условие понимается однозначно. Ведь, фраза "остальные числа могут иметь только одну пару" означает, что среди ненулевых чисел максимум одно встречается два раза. А как догадаться, что имеется в виду другой смысл: каждое ненулевое число встречается не более двух раз.
Объясните, почему в системе заложен ответ другой задачи?
Полностью с Вами согласен. Нечётко написанное условие водит в заблуждение, заставляет угадать, "что имелось в виду".
Речь в задаче не идёт ни о "символах", ни о цифрах, а лишь о числах. Число 10 это одно число.