|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
22.03.2017, 22:13 | #1 | |
Спокойный псих
Участник клуба
Регистрация: 19.03.2013
Сообщений: 1,538
|
Олимпиадная задача (Перевёртыши 11/16)
Здравствуйте. Сегодня принимал участие в олимпиаде, и попалась одна задача, которую я даже не стал решать, по причине нехватки времени. К тому же, я понимал, что возникнет проблема, с которой в итоге я сюда и пришёл.
Задача для меня показалась интересной ... И вот, после пяти часов разбора и реализации алгоритма я пришёл сюда. Текст задачи: Цитата:
Суть проблемы: у меня на уме (и уже в коде) только полный перебор всех десятичных значений: перевести число в 11-ричную и 16-ричную СС, 16-ричное число развернуть, сравнить с 11-ричным. Ну и так далее ... Строками. Мой исходник на шарпе, если кому надо ... Мне изначально было понятно, что это довольно таки длительная операция; мой компьютер в один поток разгребает миллион чисел примерно за 3 секунды. Несложно посчитать, что все 2^40 будут одним потоком обрабатываться на протяжении 100 часов. В 8 потоков - 12 часов номинальной нагрузки на все ядра. С невозможностью работать за компом. Это вроде как выходит за рамки олимпиады и её условий. И тем не менее ... Если одно ядро моего процессора грузить обычным инкрементом - Код:
Вопрос: как правильно решать поставленную задачу ? Как я подозреваю, тут нужно не "перебирать всё", а "генерировать нужное". Как ?
Подпись ? Не, не слышал ...
Последний раз редактировалось OmegaBerkut; 23.03.2017 в 16:35. |
|
23.03.2017, 08:56 | #2 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Можно копнуть в сторону диофантовых уравнений в целых числах. Вот например для 4-значных:
a0 + a1*11 + a2*11^2 + a3*11^3 = a3 + a2*16 + a1*16^2 + a0*16^3 -> (1-16^3)*a0 + (11-16^2)*a1 + (11^2-16)*a2 + (11^3-1)*a3=0 нужно найти a0,a1,a2,a3 из [0..10] и при этом a3 и a0 > 0 Примеры решения подобных уравнений есть например здесь http://www.math.md/school/krujok/diofantr/diofantr.html Дерзай ))
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 23.03.2017 в 09:01. |
24.03.2017, 09:19 | #3 |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,526
|
написано в блокноте, код не проверялся!
Код:
программа — запись алгоритма на языке понятном транслятору
Последний раз редактировалось evg_m; 24.03.2017 в 09:28. |
29.03.2017, 18:57 | #4 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
И что, не получается? Вот еще наводка. При подборе крайнего правого 11-ричного верхняя оценка 11^n*(aN+1)-1 и нижняя оценка 16-ричного 16^n*aN, что на порядки снижает перебор при подборе коэффициентов диофантового уравнения, расчет мигом проходит. Вот все решения до 10-значных 16-ричных включительно, 40 бит из условия. За полноту не ручаюсь, мало ли, обшибся ))
Код:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
30.03.2017, 15:10 | #5 |
Спокойный псих
Участник клуба
Регистрация: 19.03.2013
Сообщений: 1,538
|
Я не разбирался, просто узнал, какое есть "быстрое" решение ...
Спасибо.
Подпись ? Не, не слышал ...
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Олимпиадная задача. (C#) | Nekro95 | Помощь студентам | 4 | 20.10.2013 14:39 |
Олимпиадная задача 3 | СергейАстрахань | Помощь студентам | 4 | 31.01.2013 16:45 |
Олимпиадная задача | СергейАстрахань | Помощь студентам | 2 | 31.01.2013 11:48 |
Олимпиадная задача. | Godziller | Фриланс | 6 | 28.05.2012 14:10 |
Олимпиадная задача | Carbon | Общие вопросы C/C++ | 2 | 23.05.2007 22:07 |