Hi All! Не могли бы вы помочь решить другую задачку:

← →
Delphin © (2005-01-28 00:01) [0]

Hi All! Не могли бы вы помочь решить другую задачку:

Через к5 обозначаем комплент из пяти десятичных цифр. В этом комплекте несколько цифр могут быть одинаковыми.
Скажем, что натуральное пятизначное число правильно образовано от к5, если запись этого числа получена, написав поочереди все цифры из к5, беря каждую один раз, и эта запись не начинается с нуля.
Например, Если к5 содержит цифры 1,1,7,0 и 4, тогда цифры 17140 и 47011 есть правильно созданные от к5.
Четыре натуральных пятизнычных числа С1,С2,С3,С4, назовём великой четвёркой из к5, если одновремено в силе следующие условия:
С1 - правильно создано от к5
С2 - правильно создано от к5
С3 - правильно создано от к5
С4 - правильно создано от к5
- Между числами С1,С2,С3,С4 нет двух одинаковых.
- С1+С2+С3=С4

По введённым в комплекте к5 цифрам, определить, сколько различных Великолепных четвёрок можно создать.
Изменение порядка цифр в одной Великолепной четвёрки, не ведёт к созданию Великой четвёрки

Заранее благодарен

← →
TUser © (2005-01-28 05:56) [1]

Все цифири С создай перебором (их, очевидно, никак не более 120), упорядочь, ну и двигайся сверху массива - для каждого числа проверяй, из каких трех оно м.б. составлено (для каждого числа возможных троек - очевидно, не более 120^3).

Если же (n!)^3 тебе не нравится (мне тоже) - тогда, можно, например, составить матрицу всех сумм С1 + С2 и матрицу всех разностей С4 - С3 (это займет (n!)^2 времени). Упорядочить всех их ((n!)^2*2*log(n!)) и найти все общие числа (n!^2). Всего получаем оценку (n!^2)*log(n!) = n*(n!^2)*log(n).

Наверное, и лучше что-нибудь можно придумать.

← →
han_malign © (2005-01-28 09:32) [2]

>... и эта запись не начинается с нуля
>для каждого числа проверяй, из каких трех...
- очевидно, что у "каждого" числа, первая цифра должна быть не меньше "3"... Точнее 3 умноженное на минимальную не нулевую цифру из набора.

← →
wal © (2005-01-28 09:35) [3]

Олимпиада?

Всем огромное спасибо :)

Hi All! Не могли бы вы помочь решить другую задачку: Найти похожие ветки