|
|
|
|
|
|
|
Вернуться
| 1 Мнение, 04 октября 2010 г. 21:55:00 | |
|
Вообще, насколько я понимаю, программа генерирует одну и ту же перестановку символов. Тогда для какой-либо конкретной перестановки количество шагов до возврата равно НОКу всех "циклов" (под циклами понимается замкнутая цепочка переходов) в перестановке. Если же перестановка, которую генерирует программа неизвестна, то ответом является максимум среди всех подобных переходов. Т.е. максимальный НОК из чисел, которые в сумме дают n. Еще не знаю как это сделать, но думаю, что значение здесь меньше факториала.
|
|
|
| 2 Ладик Артём, 04 октября 2010 г. 19:30:53 | |
Короче могу сказать только суть...
Есть файл длинной из n символов.... есть программа которая какимто образом переставлят символы в файле, но эти перестановки зависят ТОЛЬКО от количества символов в файле... Мальчик у мальчика Вовы был файл длинной n символов. Он запустил программу и символы переставились... Вопрос: Какое минимальное количество раз ему нужно запустить программы, чтобы гарантировать получение исходного файла....
Я решал так
ans = n! - 1
|
|
|
| 3 Нигматуллин Нияз Габдуллазянович [СПбГУ ИТМО], 04 октября 2010 г. 16:40:02 | |
|
а в чем задача?
|
|
|
| 4 Ладик Артём, 03 октября 2010 г. 21:11:47 | |
|
пробовал хранить по модулю 10^9 не помогает... конечно может я задачу не правильно решал, но все тесты что в 2 сек укладывались проходили...
|
|
|
| 5 Ладик Артём, 03 октября 2010 г. 21:09:15 | |
|
Вроде возможно. Я вчера на олимпиаде такую задачу решал...
|
|
|
| 6 Яхнев Иван Николаевич, 03 октября 2010 г. 15:19:38 | |
Можно попробовать найти разложение числа n! на простые множители. Завести массив чисел s[1..n]. Затем для каждого числа от 1 до n найти все его делители (одинаковый нужно учитывать). При нахождении очередного делителя надо увеличить элемент s[ делитель ] на единицу. Число n! будет равно произведению всех чисел j от нуля до n в степени s[j]. (n! = 1^s[1] * 2^s[2] * ... * (n-1)^s[n-1] * n^s[n]). Основную массу множителей будут составлять маленькие числа (для n=100000): 2 будет входить 99994 раза, 3 - 49995, 5 - 24999, 7 - 16662, 11 - 9997, 13 - 8331, 17 - 6249. Значит чтобы меньше производить вычислений можно вычислять n!, начиная с чисел n, n-1, n-2, ... 3, 2, 1. (при этом используя быстрое возведение в степень). В две секунды, наверное, сложно будет уложиться.
Можно также попробовать применить дерево Фенвкика.
|
|
|
| 7 Беляев Сергей Николаевич, 03 октября 2010 г. 13:06:00 | |
|
А такое точно возможно? О прекалке тоже речи идти не может, слишком много будет "весить", если хранить даже через каждую тысячу...
|
|
|
| 8 Ладик Артём, 03 октября 2010 г. 12:42:24 | |
Как ТОЧНО вычислить факториал числа 100000 меньше чем за 2 секунды.... кто поможет буде очень благодарен...
ПС. не нужно ссылок на другие сайты... пишите идеи здесь
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
