Как, вы не можете вспомнить 6 или 7-значный номер телефона, который появился на экране телевизора на секунду ?! Используя специальную технику, описанную ниже, вы превратитесь в прогулочную телефонную книгу!

Очевидно, что число 402легче запомнить, чем число 110010010, а число 337377легче запомнить, чем число 957472. Это означает, что запомненный номер, с одной стороны, должен содержать как можно меньше цифр, а с другой стороны, желательно, чтобы номер содержал как можно больше повторяющихся чисел.

В качестве критерия сложности запоминания мы берем сумму числа цифр в числе и числа разных цифр в номере. Запомненный номер можно записать в другой системе счисления, возможно, тогда его будет легче запомнить. Например, число 65535в шестнадцатеричной записи выглядит следующим образом FFFF.

задача

Вам необходимо написать программу для выбора базы системы счисления, чтобы минимизировать критерий сложности. Основа системы счисления должна быть выбрана в диапазоне от 2 до 36, тогда цифры 0-9и английские буквы A-Zмогут использоваться для представления числа.

вход

Входные данные содержат десятичное целое число от 1 до 999999999.

Выход

Выходные данные должны содержать базу системы счисления (от 2 до 36), минимизирующую критерий сложности запоминания, и число в выбранной системе счисления, разделенное одним пробелом. Если несколько базисов дают одно и то же значение критерия, то выберите наименьшее из них.

Примечания

• Буквы должны быть заглавными ( A-Z).

Тестовые случаи

Ввод, вывод

1              2 1

2              3 2

65535       16 FFFF

123          12 A3

Perl 6 , 55 54 байта

-1 байт благодаря Джо Кингу.

{~map({$^b,.base($b)},2..36).min:{@$_+.Set}o*[1].comb}

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

Python 2 , 150 149 127 144 байтов

lambda n:min((len(c(n,b))+len(set(c(n,b))),b,c(n,b))for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n/b,b,chr(n%b+48+7*(n%b>9))+s)or s or'0'

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

Python 3 , 136 байт

lambda n:min((len((*c(n,b),*{*c(n,b)})),b,c(n,b))for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n//b,b,chr(n%b+48+7*(n%b>9))+s)or s

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

Python 3.8 (предварительная версия) , 131 байт

lambda n:min((len((*(x:=c(n,b)),*{*x})),b,x)for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n//b,b,chr(n%b+48+7*(n%b>9))+s)or s

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

c преобразует число 10 в любое основание (2-36), и первая (анонимная) функция находит наименьший результат.

05AB1E , 16 14 байтов

-1 байт благодаря Кевину Круйссену

₆LBāøΣнDÙìg}1è

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

Или добавьте R) »в конце, чтобы точно соответствовать указанному выходному формату, но большинство других ответов не беспокоили.

Объяснение:

₆L          # range 1..36
  B         # convert the input to each of those bases
   āø       # enumerate (pair each element with its 1-based index)
Σ     }     # sort by
     g      # length
 н          # of the first element
    ì       # concatenated to
  DÙ        # itself, uniquified
1è          # take the second entry (first will always be base 1)

JavaScript (ES6),  87 85  101 байт

Изменить: +16 бесполезных байтов, чтобы соответствовать строгому формату вывода

n=>(g=m=>--b>2?g(m<(v=new Set(s=n.toString(b)).size+s.length)?m:(o=b+' '+s.toUpperCase(),v)):o)(b=37)

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

Japt v2.0a0 -gS, 24 23 байта

Не красиво, но это делает работу. +2 байта за абсолютно ненужное требование, чтобы вывод был в верхнем регистре.

37o2@sX u ¸iXÃñÈÌiXÌâ)l

Попытайся

37o2@sX u ¸iXÃñÈÌiXÌâ)l     :Implicit input of integer
37o2                        :Range [2,37)
    @                       :Map each X
     sX                     :  Convert the input to a base-X string
        u                   :  Uppercase
          ¸                 :  Split on spaces (there are none, so this returns a singleton array)
           iX               :  Prepend X
             Ã              :End map
              ñ             :Sort by
               È            :Pass each X through the following function
                Ì           :  Last element of X
                 i          :  Prepend
                  XÌâ       :    Last element of X, deduplicated
                     )      :  End prepend
                      l     :  Length
                            :Implicit output of the first sub-array, joined with spaces

PHP ,124 119 байт

for($i=36;$b=strtoupper(base_convert($argn,10,--$i));$o[strlen($b.count_chars($b,3))]="$i $b");krsort($o);echo end($o);

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

Позор в +12 байтах в PHP для вывода в верхнем регистре ... но ... в любом случае.

Zsh , 85 байт

for b ({36..2})x=$[[#$b]$1]&&x=${x#*\#}&&a[$#x+${#${(us::)x}}]=$b\ $x
a=($a)
<<<$a[1]

Для этого числа выражений внутри цикла for значение ...&&...&&...короче, чем {...;...;...;}.

for b ({36..2})                   # order decreasing: smaller bases overwrite larger ones
    x=$[[#$b]$1] && \             # set x to [base]#[num] 
    x=${x#*\#} && \               # strip leading [base]#
    a[$#x+${#${(us::)x}}]=$b\ $x  # use score as index to store "[base] [number]"
#            ${(us::) }           # (s::)plit into characters, take (u)nique
a=($a)                            # remove empty elements from array
<<<$a[1]                          # print out the first element (smallest score)

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

Вот 81-байтовое решение, которое печатает [base]#[num]вместо формы :

for b ({36..2})x=$[[#$b]$1]&&y=${x#*\#}&&a[$#y+${#${(us::)y}}]=$x
a=($a)
<<<$a[1]

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

J 67 байт

(];'0123456789ABCDEF'{~b)[:(2+]i.<./)](#+#@~.)@(b=:#.inv~)"+2+i.@35

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

Древесный уголь , 38 байт

Ｎθ≔ＥＥ³⁴↨θ⁺²ιＬ⁺ιΦι⁼λ⌕ικη≔⁺²⌕η⌊ηηＩη ↥⍘θη

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:

Ｎθ

Введите целое число.

≔ＥＥ³⁴↨θ⁺²ι

Преобразовать его из базы 2 в базу 36 ...

Ｌ⁺ιΦι⁼λ⌕ικη

... дедуплицировать, объединить и взять длину.

≔⁺²⌕η⌊ηη

Возьмите индекс минимальной сложности и добавьте 2, чтобы получить базу.

Ｉη ↥⍘θη

Выведите основание и целое число, преобразованное в это основание в верхнем регистре.

Stax , 19 байт

Ç╛;ⁿY3█↕(╖S♪*ò▌?½╦l

Запустите и отладьте его

Никакого сложного алгоритма, просто грубая сила. Около трети программы - форматирование для точных правил вывода.

Бонусная программа: Выход за [1..1000]

Желе , 25 байт

bⱮ36µQL+LN)Mḟ1Ḣ,ị‘ịØBʋ¥⁸K

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

Монадическая ссылка, принимающая целое число в качестве аргумента и возвращающая строку Jelly нужного формата. Если список из двух элементов был приемлемым выводом (согласно большинству проблем), можно было бы сэкономить 2 байта. Если бы база 1 была приемлемой для случая края 1 в качестве входных данных, можно было бы сохранить еще 2 байта.

Брахилог , 44 байта

∧Y≜∧36≥Xℕ₂≜&ḃ↙X Zd,Zl≡Y∧XwṢwZ{-₁₀;Ạụᵗ∋₍|}ᵐwᵐ

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

Больно немного писать.

Perl 5 , 161 байт

sub f{$X=99;for$b(2..36){$_=c($_[0],$b);$x=uniq(/./g)+y///c;($X,$B,$C)=($x,$b,$_)if$x<$X}$B,$C}
sub c{my($n,$b)=@_;$n?c(int$n/$b,$b).chr(48+$n%$b+7*($n%$b>9)):''}

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

Python 2 , 140 135 байтов

lambda n:min([(b,g(n,b))for b in range(2,36)],key=lambda(b,s):len(s)+len(set(s)))
g=lambda n,b:n and g(n/b,b)+chr(n%b+48+7*(n%b>9))or''

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

Perl 5 -Minteger -MList::Util=uniq,first -ap , 123 112 байт

$"=$,;map{@r=();$t="@F";do{unshift@r,(0..9,A..Z)[$t%$_]}while$t/=$_;$a[@r+uniq@r]||="$_ @r"}2..36;$_=first{$_}@a

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

Wolfram Language (Mathematica) , 109 111 байт

Print[a=OrderingBy[#~IntegerDigits~Range@36,Tr[1^#]+Tr[1^Union@#]&,1][[1]]," ",ToUpperCase[#~IntegerString~a]]&

+2: исправлено. Спасибо за улов @Roman

OrderingBy был представлен в Mathematica 12.0, которую TIO, похоже, еще не обновил.

C (лязг) , 165 байтов

n,i=2,j,p=99,r,m,x;char*g,*_,b[74][37];t(n){for(;g=b[i],i<37;r=j<p?_=g,p=j,i:r,++i)for(j=0,m=n;m;m/=i,*--g=x+=x>9?87:48)j+=b[i+36][x=m%i]++?1:2;printf("%i,%s",r,_);}

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

п // вход

, i = 2 // итератор от базы 2 до 36

, j // текущая сложность

, p = 99 // лучшая сложность

, r // результат = итератор

, m // временная копия n

, х; // м% я

char * g // текущая строка ptr

, * _ // лучший str ptr

, Б [74] [37]; // буфер

/ * [37 + 37] = [полученные строки + проверка используемых символов] * /

т (п) {

for (; g = b [i], // переместить ptr

   i<37 ; 
   r=j<p?_=g,p=j,i:r, // save best solution

   ++i){//for every base

для (j = 0, m = n; m; m / = i, // извлечь цифру

   *--g=x+=x>9?87:48)
   // move ptr backward for printf use and transform to ascii value

J + = Ь [I + 36] [х = т% я] ++ 1: 2; // увеличиваем байт относительно символа

// и, если это было 0, увеличивает j на 2: 1 для нового используемого символа и 1 для числа цифр

// иначе только цифры на счет + указатель перемещения

// printf ("% s -", ​​g); // тест

// printf ("r% ip% ij% i \ n", r, p, j); // тест

}

Е ( "% I,% s", г, _); // выход

}

Japt v2.0a0, 31 байт

2o37 ñ@sX Ê+UsX â ÊÃÎ
+S+NÎsU u

Попытайся