Вызов

Напишите функцию или программу, которая принимает положительное десятичное число, назовите его A и выведите два положительных числа, B и C , так, чтобы:

• A == B bitxor C
• B и C не должны содержать ни одной из цифр 0, 3 или 7 в своем десятичном представлении.

Примеры

>>> decompose(3)
1, 2
>>> decompose(7)
1, 6
>>> decompose(718)
121, 695
>>> decompose(99997)
2, 99999
>>> decompose(4294967296)
4294968218, 922
>>> decompose(5296080632396965608312971217160142474083606142654386510789497504098664630388377556711796340247136376)
6291484486961499292662848846261496489294168969458648464915998254691295448225881546425551225669515922,
1191982455588299219648819556299554251659915414942295896926425126251962564256469862862114191986258666

Поскольку декомпозиция не уникальна, ваша функция / программа не должна выводить те же самые результаты, что и приведенные примеры.

Очень подробные правила

1. Материалы должны быть в виде полной функции или программы . importЗаявления же засчитываются окончательный счет.

2. Вы можете предположить, что вход A всегда содержит хотя бы цифру 0, 3 или 7.

3. Вы можете предположить, что разложение всегда существует.

4. Вы можете использовать BigInt, если они являются частью стандартных библиотек языка или могут быть установлены через менеджер пакетов языка de jure .

5. Функция должна быть быстрой. Для запуска на достаточно современном компьютере должно потребоваться не более 20 секунд при вводе 100-значного числа и не более 2 секунд при вводе 10-значного числа.

6. Функция / программа должна поддерживать ввод не менее 100 цифр .

   • Если функция / программа может поддерживать только целые числа до N <100 цифр, штраф до + 10 × (100 / N - 1) байтов к окончательному счету будет уменьшен. Это должно поощрить игроков в гольф поддерживать более широкий диапазон чисел, даже если импорт может быть многословным.

7. Нет ограничений на представление входных / выходных данных, если они явно представлены в десятичном формате.

   • Функция может вводить и выводить строки / BigInts, если встроенных целочисленных типов недостаточно.
   • Входные данные могут поступать из параметра функции, аргумента командной строки или STDIN.
   • Функция может вернуть результат или просто распечатать результат непосредственно в STDOUT.
   • Однако переполнение со знаком на входах / выходах не допускается.
   • Приблизительные ответы не допускаются, ввод / вывод должен быть точным.

счет

Это код-гольф . Самое короткое решение в байтах побеждает.

Существует штраф, если программа может поддерживать только цифры менее 100 цифр:

• 64-разрядные целые числа (19 цифр) = +42 байта
• 63-разрядные целые числа (18 цифр) = +45 байтов
• 53-разрядные целые числа (15 цифр) = +56 байт
• 31/32-битные целые числа (9 цифр) = +101 байт

CJam, 70 байт

ri:Q{;Qmr_Q^`1$`+730`&}g_Q^p

Попробуйте онлайн.

Случайно выбирает целые числа, пока не найдет совпадение. Это едва соответствует 20-секундному пределу для 64-разрядных целых чисел (с использованием интерпретатора Java), поэтому я добавил 42 к фактическому количеству байтов.

Пример запуска

$ cjam t <<< 7777777777; echo
2695665494
6161166119

Common Lisp, 240 224 183 173 169 байт

Common Lisp немного многословен для игры в гольф. Однако это позволяет разложить 100-значные числа менее чем за секунду и 200-значные целые числа менее чем за десять секунд, поэтому штрафы не требуются. Алгоритм является детерминированным.

(defun s(z)(and #1=(some(lambda(q)(position q(format()"~a"z)))"037")(+ z(floor z(expt 10 #1#)))))
(defun d(x)(do((y x(or(s y)(s #3=(logxor x y))(return`(,y,#3#)))))(())))

Перевод строки между функциями предназначен только для типографских целей. Пробный запуск с эталонным вводом из 100 цифр:

(time (d 5296080632396965608312971217160142474083606142654386510789497504098664630388377556711796340247136376))
took 677,000 microseconds (0.677000 seconds) to run.
      20,989 microseconds (0.020989 seconds, 3.10%) of which was spent in GC.
During that period, and with 8 available CPU cores,
     671,875 microseconds (0.671875 seconds) were spent in user mode
           0 microseconds (0.000000 seconds) were spent in system mode
 54,221,104 bytes of memory allocated.
(1864921261592819619661568919418981552559955289196969112566252282429216186594265918444566258544614425
 5891958562486995519825158818455999516899524658151445485616155916296966645869599949958954491929662561)

В качестве бонуса я включаю версию кода, которая постепенно создает решение сверху вниз. Он может управлять 1000-значным числом менее чем за десять секунд, но не может соревноваться в гольфе из-за дополнительного кода.

(defun decompose (x)
  (flet ((s (z)
           (mapcan #'(lambda (c) (and #1=(position c #2=(format () "~a" z))
                                 (list (- (length #2#) #1# 1))))
                   '(#\0 #\3 #\7))))
    (do ((y x (let ((p (nconc (s y) (s #3=(logxor x y)))))
                (or p (return`(,y,#3#)))
                (+ y (expt 10 (apply #'max p))))))
        (nil))))

* (time (decompose (parse-integer (make-string 1000 :initial-element #\7))))
took 9,226,000 microseconds (9.226000 seconds) to run.
        90,966 microseconds (0.090966 seconds, 0.99%) of which was spent in GC.
During that period, and with 8 available CPU cores,
     9,234,375 microseconds (9.234375 seconds) were spent in user mode
             0 microseconds (0.000000 seconds) were spent in system mode
 487,434,560 bytes of memory allocated.
(8889898889152488921298888992819221914229899249999918899888899888888889999989141219898898888988988898888888888899142442899924898918898898988988895189988898888924192198992454114198911989191888889898888918888988988998888891421118891899122898888998989898888898988898888999988918888898889189918889888888899888989219188898998888988892119889198888988888894888912188898989952999888888888898899998988898889228918998949999998898898991141888898999988912121292118899889998989899999892889941898888911888898889118998898888911889889888891452888998889288921141888888942189888899988891918889118888888888989892198899199914111188988889421111188889118888918989988912989999998989891119888898888888892621229888988888999619888952462219889189899998899888889989898891118989218888888898962988891188899888888888999888888888888888888888891269188921288888888998898899214191188888888898992188998898889919888889989889899988892115549998888898889218899988998911898989199918898918988898888891889888989119899888889888998918889112189998
 4184469818464841952189561886965821566229261221619858498284264289194458622668559698924621446851546256444641488616184155821914881485164244662156846141894655485889656891849662551896595944656451462198891289692696856414192264846811616261884188919426294584158925218559295881946496911489245664261126565546419851585441144861859822815144162828551969425529258169849412525611662488849586554989254181228254465226521648916188265491499166186964881248156451994924294646681548996645996894665198811511522424996844864211629888924642289925565591484541149414914699289441561496451494562955652129199261462268846144518142486845251946444998812988291119592418684842524648484689261441456645518518812265495165189812912919529151991611962525419626921619824496626511954895189658691229655648659252448158451924925658586522262194585891859285841914968868466462442488528641466655911199816288496111884591648442984864269495264612518852292965985888414945855422266658614684922884216851481646226111486498155591649619266595911992489425412191)
* (apply #'logxor *)
7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777

Python 2, 103 + 42 = 145 байт

Python изначально поддерживает bigints, но эта программа намного превышает 20 секунд для 100-значного числа. Однако он разлагает 64-разрядные целые числа примерно за 2 секунды.

from random import *
def d(a):
 b=c=0
 while set(`b`+`c`)&set('037'):
    b=randint(1,a);c=a^b
 return b,c

Python 3 (132 байта)

(Это просто для того, чтобы стимулировать лучшие решения. Это мое решение при решении исходной проблемы в фильме ASCII.)

def d(a):
 l=len(str(a));s=int('1'*l);u=10**(l-1)
 while u:
  while set(str(s)+str((a^s)//u))&set('037'):s+=u
  u//=10
 print(s,a^s)

Хотя поведение побитового xor в десятичной системе довольно сложное, есть одно важное наблюдение: изменение младших разрядов не повлияет на старшие . Поэтому мы можем работать сверху вниз: попытаться освободить верхние цифры от 0, 3, 7, а затем работать с следующей цифрой, пока не будет получено все число. Это позволяет нам работать за линейное время, после чего обработка тысячного числа может завершиться менее чем за 1 секунду. (Решение Common Lisp также использует ту же технику, которую я считаю.)