Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Общие вопросы по программированию, компьютерный форум
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 22.03.2017, 22:13   #1
OmegaBerkut
Спокойный псих
Участник клуба
 
Аватар для OmegaBerkut
 
Регистрация: 19.03.2013
Сообщений: 1,538
По умолчанию Олимпиадная задача (Перевёртыши 11/16)

Здравствуйте. Сегодня принимал участие в олимпиаде, и попалась одна задача, которую я даже не стал решать, по причине нехватки времени. К тому же, я понимал, что возникнет проблема, с которой в итоге я сюда и пришёл.
Задача для меня показалась интересной ...
И вот, после пяти часов разбора и реализации алгоритма я пришёл сюда.
Текст задачи:
Цитата:
Перевёртыши_11/16.
Найти все такие числа х (представленные в 11-ричной системе счисления цифрами 0,1,…,9,А), что если цифры числа х записать в обратном порядке и рассматривать их как шестнадцатиричные, то получится то же самое число х.
Например: 32(11)=23(16) (=35). Ответ вывести в шестнадцатиричном формате (в данном примере – 23).
1. Найдены все числа, обладающие указанным свойством и не превышающие 2^32 – 7 баллов.
2. Найдены все числа из диапазона от 2^32 до 2^40, обладающие указанным свойством – 3 балла.
Пять часов - потому что лень и усталость. Так, на непосредственное придумывание и написание кода ушло порядка получаса.

Суть проблемы: у меня на уме (и уже в коде) только полный перебор всех десятичных значений: перевести число в 11-ричную и 16-ричную СС, 16-ричное число развернуть, сравнить с 11-ричным. Ну и так далее ... Строками.
Мой исходник на шарпе, если кому надо ...

Мне изначально было понятно, что это довольно таки длительная операция; мой компьютер в один поток разгребает миллион чисел примерно за 3 секунды. Несложно посчитать, что все 2^40 будут одним потоком обрабатываться на протяжении 100 часов. В 8 потоков - 12 часов номинальной нагрузки на все ядра. С невозможностью работать за компом.
Это вроде как выходит за рамки олимпиады и её условий.

И тем не менее ... Если одно ядро моего процессора грузить обычным инкрементом -
Код:
long g=0,n=(long)Math.Pow(10,9),ticks=DateTime.Now.Ticks;
for (;g<n;g++);
Console.WriteLine(((DateTime.Now.Ticks-ticks)/10000).ToString());
Console.ReadLine();
- мой не очень то и слабый ноутбук перебирает указанный миллиард за 950 миллисекунд. Что касается трюлика - это примерно 15 минут. Чистого инкремент-сравнения, без какой либо обработки и/или генерации.

Вопрос: как правильно решать поставленную задачу ?
Как я подозреваю, тут нужно не "перебирать всё", а "генерировать нужное". Как ?
Подпись ? Не, не слышал ...

Последний раз редактировалось OmegaBerkut; 23.03.2017 в 16:35.
OmegaBerkut вне форума Ответить с цитированием
Старый 23.03.2017, 08:56   #2
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Можно копнуть в сторону диофантовых уравнений в целых числах. Вот например для 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
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,515
По умолчанию

написано в блокноте, код не проверялся!
Код:
var
  j: int64; // 2^40 сюда поместится
  
for j:=1 to N do begin
  r:=j;
  k:=0;
  s:=0;
  while r>0 do begin
    if (k=0) and (r mod 16 =0) then break; //первое условие последняя цифра не ноль
      k:=k+1; //здесь у нас будет число использованных шестнадцати- одиннадцати- ричных цифр в записи числа
    if (r mod 16) >=11 then break; // в шестнадцатеричном разложении неправильная цифра
      s:=s*11 +(r mod 16); //собираем одиннадцатитеричное значение в обратном порядке
    if s>j then break; //мы уже перешагнули наше проверяемое число
      r:=r div 16; // "вычеркиваем" последнюю цифру и переходим к следующей шестнадцатеричной цифре
  end;
  if s=j then //ура есть совпадение
end;
программа — запись алгоритма на языке понятном транслятору

Последний раз редактировалось evg_m; 24.03.2017 в 09:28.
evg_m вне форума Ответить с цитированием
Старый 29.03.2017, 18:57   #4
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

И что, не получается? Вот еще наводка. При подборе крайнего правого 11-ричного верхняя оценка 11^n*(aN+1)-1 и нижняя оценка 16-ричного 16^n*aN, что на порядки снижает перебор при подборе коэффициентов диофантового уравнения, расчет мигом проходит. Вот все решения до 10-значных 16-ричных включительно, 40 бит из условия. За полноту не ручаюсь, мало ли, обшибся ))
Код:
0
1
2
3
4
5
6
7
8
9
A
23
46
69
1013
1383
1504
1874
2026
2396
2517
2887
2A08
3039
33A9
352A
389A
12615
23299
103666
124947
1026169
119144A
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 30.03.2017, 15:10   #5
OmegaBerkut
Спокойный псих
Участник клуба
 
Аватар для OmegaBerkut
 
Регистрация: 19.03.2013
Сообщений: 1,538
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
И что, не получается?
Я не разбирался, просто узнал, какое есть "быстрое" решение ...
Спасибо.
Подпись ? Не, не слышал ...
OmegaBerkut вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Олимпиадная задача. (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