Задача по комбинаторике

[TOTAL]

Tiberium в сообщении #1333030 писал(а):

Прошу прощения, я сначала неверно Вас понял. Действительно, можно считать, что нам нужно посчитать четырехзначные номера, у которых одинаковые цифры не идут подряд. Но тогда получается, что количество вариантов - $10\cdot9\cdot10\cdot8\cdot4$.

Количество каких вариантов?

[Tiberium]

TOTAL в сообщении #1333031 писал(а):

Коричество каких вариантов?

(здесь была написана глупость)

[TOTAL]

Tiberium в сообщении #1333032 писал(а):

TOTAL в сообщении #1333031 писал(а):

Коричество каких вариантов?

Четырехзначных номеров, у которых одинаковые цифры не идут подряд.

ABCDE таких $10*9*9*9*9$
ABCD таких $10*9*9*9$
ABCD таких $10*9*9*9$
ABCD таких $10*9*9*9$
ABCD таких $10*9*9*9$

Вот все допустимые варианты. Здесь B не равно A, C не раво B и т.д. Жирную цифру удвоить.

[Tiberium]

TOTAL в сообщении #1333033 писал(а):

ABCDE таких $10*9*9*9*9$
ABCD таких $10*9*9*9$
ABCD таких $10*9*9*9$
ABCD таких $10*9*9*9$
ABCD таких $10*9*9*9$

Вот все допустимые варианты. Здесь B не равно A, C не раво B и т.д. Жирную цифру удвоить.

Спасибо! Только что получилось то же самое — итого 72900 вариантов. Теперь же мы все учли? Выше были намеки на то, что правильный ответ - 95500

[TOTAL]

Tiberium в сообщении #1333035 писал(а):

Только что получилось то же самое — итого 72900 вариантов.

Получайте новое "итого"

[Tiberium]

TOTAL в сообщении #1333036 писал(а):

Получайте новое "итого"

94770

[wrest]

Tiberium в сообщении #1333035 писал(а):

Выше были намеки на то, что правильный ответ - 95500

Ну не точно этот, но близко. У меня получилось чуть больше, и на все депутатские пальцы бы не хватило, поэтому я написал "хватило бы примерно"
Впрочем, может я тоже неверно понял условие задачи...
Скажу откровенно -- я не заморачивался с биномами, поскольку хотел просто проверить ответ, так что быстренько перебрал все стотыщ номеров на калькуляторе

Не знаю хорошо ли это в педагогическом плане, но может вы тоже сперва все допустимые (или недопустимые) номера посчитаете на калькуляторе, а потом подумаете почему у вас не сходится?

[wrest]

(Как я понял условия задачи:)

Tiberium129121(lst)=my(m=#lst);for(i=1,m-2,if(lst[i]==lst[i+1],if(lst[i+2]==lst[i],return(0));if(i<m-2,if(lst[i+2]==lst[i+3],return(0)))));return(1)

Вышеприведенная функция Tiberium129121 определяет хороший ли номер. Входной параметр lst это массив из цифр номера, например lst=[1,2,9,1,2,1], функция возвращает 1 если номер хороший и 0 если плохой. Сначала ищем пару одинаковых цифр, начинаем с левой цифры. Если пара не нашлась -- номер хороший, выход. Пара нашлась: запоминаем где и проверяем осталась ли за найденной парой ещё цифра и не равна ли она цифрам пары (т.е. не тройка ли это одинаковых цифр), если тройка -- номер плохой, выход. Если до конца номера осталось не менее 2 цифр, проверяем не пара ли там. Если там пара, то номер плохой, выход. Если нет, продолжаем искать пару со следующей, за запомненной, позиции, если до конца номера не менее трех цифр. Если менее -- номер хороший, выход.

[TOTAL]

wrest в сообщении #1333051 писал(а):

(Как я понял условия задачи:)

Tiberium129121(lst)=my(m=#lst);for(i=1,m-2,if(lst[i]==lst[i+1],if(lst[i+2]==lst[i],return(0));if(i<m-2,if(lst[i+2]==lst[i+3],return(0)))));return(1)

Вышеприведенная функция Tiberium129121 определяет хороший ли номер. Входной параметр lst это массив из цифр номера, например lst=[1,2,9,1,2,1], функция возвращает 1 если номер хороший и 0 если плохой. Сначала ищем пару одинаковых цифр, начинаем с левой цифры. Если пара не нашлась -- номер хороший, выход. Пара нашлась: запоминаем где и проверяем осталась ли за найденной парой ещё цифра и не равна ли она цифрам пары (т.е. не тройка ли это одинаковых цифр), если тройка -- номер плохой, выход. Если до конца номера осталось не менее 2 цифр, проверяем не пара ли там. Если там пара, то номер плохой, выход. Если нет, продолжаем искать пару со следующей, за запомненной, позиции, если до конца номера не менее трех цифр. Если менее -- номер хороший, выход.

Подавайте четыре числа - разности соседних цифр. Если среди них более одного нуля, то номер плохой.

[wrest]

TOTAL в сообщении #1333053 писал(а):

Подавайте четыре числа - разности соседних цифр. Если среди них более одного нуля, то номер плохой.

Не, номер XXYZZ имеет более одного нуля в разностях соседних цифр, но номер не плохой. Так что подавать надо три разности от четырех подряд идущих цифр и эту четверку смещать. Что собсно эквивалентно тому что я написал: сравнение двух цифр и сравнение их разности с нулем это одно и то же (хотя по скорости не знаю, зависит от компилятора).

(Оффтоп)

Плюс, у меня в коде сравниваются в общем-то не цифры, а элементы массива (вернее -- списка, а в PARI/GP в списке могут быть разнотипные элементы, так что проверку равенства сделать можно, а сложение может быть и неопределено), то есть могут быть и буквы или что-то, для чего арифметики нет.

[Yadryara]

Tiberium в сообщении #1333037 писал(а):

94770

У меня получилось столько же. И подсказке, которую дал wrest, полностью соответствует. Жаль только, что TOTAL фактически решил задачу за Вас.

[Tiberium]

Yadryara в сообщении #1333057 писал(а):

Жаль только, что TOTAL фактически решил задачу за Вас.

Мне тоже жаль. Я умудрился несколько раз по-разному и неправильно понять формулировку задачи, так ещё и арифметика подвела в итоге. В общем, стыд и позор:) Но выводы я для себя сделал.

Всем большое спасибо за помощь!

[EUgeneUS]

wrest в сообщении #1333054 писал(а):

Не, номер XXYZZ имеет более одного нуля в разностях соседних цифр, но номер не плохой.

Плохой же. Если номер $78855$ плохой (пример из стартового поста), то и $88755$ - плохой.

[TOTAL]

wrest в сообщении #1333054 писал(а):

TOTAL в сообщении #1333053 писал(а):

Подавайте четыре числа - разности соседних цифр. Если среди них более одного нуля, то номер плохой.

Не, номер XXYZZ имеет более одного нуля в разностях соседних цифр, но номер не плохой.

Отвратительный номер! (В нем более одного повтора.)

[wrest]

EUgeneUS в сообщении #1333060 писал(а):

Плохой же. Если номер $78855$ плохой (пример из стартового поста), то и $88755$ - плохой.

Читаем условие:

Tiberium в сообщении #1332920 писал(а):

в номере может быть максимум одна пара одинаковых цифр, идущих подряд

Смотрим. В номере $78855$ две пары идут подряд (пара $88$ и за ней сразу, то есть подряд, идёт пара $55$). А в номере $88755$ хотя и две пары, но они НЕ идут подряд, а разделены цифрой $7$.

А... ну да, наверное вы правы. Велик могучим русский языка