Preciso preparar dígitos feitos de papelão para exibir algum número ( exemplo ). Não sei de antemão qual número devo exibir - a única coisa que sei é que não é maior que n.

Quantos dígitos de papelão devo preparar?

Exemplo: n = 50

Para exibir qualquer número no intervalo de 0 a 50, preciso dos seguintes dígitos:

1. Um zero, para exibir o número 0 ou qualquer outro número redondo
2. Duas cópias dos dígitos 1, 2, 3 e 4, para exibir os números correspondentes
3. Uma cópia dos dígitos 5, 6, 7 e 8, caso apareçam como dígito menos significativo no número
4. O dígito 9 nunca é necessário, porque eu posso usar o dígito invertido 6

Total: 13 dígitos

Casos de teste (cada linha é um caso de teste no formato "entrada; saída")

0 1
1 2
9 9
11 10
50 13
99 17
100 18
135 19
531 22
1000 27
8192 34
32767 38

Geléia , 9 bytes

‘ḶDœ|/ḟ9L

Experimente online!

Como funciona

‘ḶDœ|/ḟ9L
‘Ḷ         [0,1,...,n]
  D        convert each to list of its digits
   œ|/     fold by multiset union
      ḟ9   remove 9
        L  length

Python 2 , 49 bytes

lambda n:9*len(`n`)-9+(n*9+8)/10**len(`n`)+(n<10)

Experimente online!

Uma fórmula aritmética desajeitada. Suponha que nse encaixe em um intpara que um Lnão seja anexado.

Agradecemos a Neil por salvar 5 bytes, apontando que 9 não sendo usados ​​podem ser manipulados fazendo-o em n*9+8vez de n*9+9, para que, digamos, 999*9+8=8999não passe para 9000.

Haskell , 117 114 108 95 89 88 87 84 82 63 bytes

6 bytes salvos graças a Laikoni

1 4 6 bytes salvos graças a nimi

g x=sum[maximum[sum[1|u<-show y,d==u]|y<-[0..x]]|d<-['0'..'8']]

Experimente online!

Mathematica, 49 bytes

Tr@Delete[Max~MapThread~DigitCount@Range[0,#],9]&

JavaScript (ES6), 60 53 bytes

f=(n,i=9)=>n>(i%9+1+"e"+(i/9|0))/9-1?1+f(n,-~i):n>9^1

Uma espécie de solução recursiva hacky. Isso gera os números que exigem a adição de um dígito:

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 22, 33, 44, 55, 66, 77, 88, 100, 111, 222, ...

e depois conta quantos são menores que a entrada. Por um feliz milagre, remover o dígito 9na verdade remove vários bytes da função, porque a sequência pode ser gerada assim (assumindo a divisão inteira):

1e1 / 9 = 1, 2e1 / 9 = 2, ..., 8e1 / 9 = 8, 9e1 / 9 = 10, 1e2 / 9 = 11, 2e2 / 9 = 22, ...

Precisamos levar em conta o fato de que números abaixo de 10 ainda exigem zero, mas isso é tão simples quanto adicionar n > 9 ? 0 : 1ao resultado.

Casos de teste

let f=(n,i=9)=>n>(i%9+1+"e"+(i/9|0))/9-1?1+f(n,i+1):n>9^1;

[0, 1, 9, 11, 50, 99, 100, 135, 531, 1000, 8192, 32767].map(n => console.log(f(n)));

Lote, 67 bytes

@if %1 geq 10%2 %0 %1 0%2 -~%3
@cmd/cset/a(%1*9+8)/10%2+9*%30+!%30

Na formulação padrão desse problema, você precisa separar 6e 9dígitos, mas não é necessário exibi-lo 0. À medida que o valor máximo nexigido aumenta, o número de numerais necessários aumenta toda vez que você alcança um repdigit (porque você não tem o suficiente desse número) e toda vez que você alcança uma potência de 10(quando você precisa de um zero extra). No total, cada potência de 10precisa de 10mais numerais do que a anterior, que pode ser calculada como floor(log10(n))*10. Para valores nentre potências de 10, o número de repdigits intermediários pode ser calculado como floor(n/((10**floor(log10(n))*10-1)/9))ou alternativamente floor(n*9/(10**floor(log10(n))*10-1)).

Eu calculo floor(log10(n))por meio do loop na primeira linha. Cada vez, %2ganha um extra 0e %3ganha um extra -~. Isso significa que 10%2é 10*10**floor(log10(n))e %30é floor(log10(n)).

A duplicação de 6e 9tem dois efeitos: primeiro, existem apenas 9números necessários para cada potência de 10, e segundo, a detecção de repdigit precisa ignorar os 9repdigits. Felizmente, como são um a menos de 10, isso pode ser alcançado ajustando a fórmula para resultar floor((n*9+8)/(10**floor(log10(n))*10)).

Lidar com o zero é razoavelmente simples: isso requer apenas um número extra quando n<10, ie floor(log10(n))==0.

Mathematica, 83 bytes

v=DigitCount;s=v@0;(Table[s[[i]]=v[j][[i]]~Max~s[[i]],{i,10},{j,#}];s[[9]]=0;Tr@s)&

Python 3 , 75 bytes

lambda n:sum(max(str(j).count(str(i))for j in range(n+1))for i in range(9))

Experimente online!

PHP , 60 bytes

<?=count(preg_grep('#^100+$|^([0-8])\1*$#',range(0,$argn)));

Experimente online!