Multiplicar e dividir

10

Dado um valor x, encontre o menor valor numérico maior que y, capaz de ser multiplicado e dividido por x , mantendo todos os dígitos originais.

  • Os novos números não perdem dígitos.
  • Os novos números não ganham dígitos.

Por exemplo:

Entrada: x = 2, y = 250000

  • Original: 285714
    • Divisão: 142857
    • Multiplicação: 571428

Isso é verdade porque 285714 é maior que y ; quando dividido por x resulta em 142857 e quando multiplicado por x resulta em 571428 . Nos dois testes, todos os dígitos originais de 285714 estão presentes e nenhum dígito extra foi adicionado.


As regras

  • X deve ser 2 ou 3, pois qualquer coisa mais alta demora muito para ser calculada.
  • É necessário que Y seja um número inteiro maior que zero .
  • O código mais curto vence.

Casos de teste

Esses são os meus casos de teste mais comuns, pois são os mais rápidos para testar.

  • x = 2, y = 250000 = 285714
  • x = 2, y = 290000 = 2589714
  • x = 2, y = 3000000 = 20978514
  • x = 3, y = 31000000 = 31046895
  • x = 3, y = 290000000 = 301046895

Esclarecimentos

  • O tipo de divisão não importa. Se você pode obter 2,05, 0,25 e 5,20 de alguma forma, fique à vontade.

Boa sorte a todos vocês!

Emma - PerpetualJ
fonte
4
" X deve ser um valor entre 2 e 5. " - se X> = 4, o número multiplicado por X será pelo menos 16 vezes maior que o número dividido por X, então com certeza terá mais dígitos
ngn
2
x não pode ser diferente de 2 ou 3, pois o produto é x ^ 2 vezes o quociente e ambos devem ter o mesmo número de dígitos. x = 1 será um caso trivial. IMO, não há solução para x = 3 para qualquer y, embora eu possa estar errado.
Jatin Sanghvi 27/09/18
2
A divisão é flutuante ou divisão inteira?
Erik the Outgolfer
3
Os casos de teste seriam ótimos
Stephen
3
Suspeito que não sou a única pessoa que se abstém de votar para reabrir porque o esclarecimento realmente torna o desafio mais ambíguo, porque a resposta correta pode mudar dependendo se a saída de ponto flutuante é considerada ou não. Eu suspeito que a pergunta de @EriktheOutgolfer não estava perguntando sobre permitir saída de ponto flutuante, mas sobre se é permitido usar a divisão de número inteiro truncada . (E desculpe-me se meus comentários aumentaram a confusão.) #
Ørjan Johansen

Respostas:

4

Casca , 14 bytes

ḟ§¤=OoDd§¤+d*/

Experimente online!

Explicação

ḟ§¤=O(Dd)§¤+d*/  -- example inputs: x=2  y=1
ḟ                -- find first value greater than y where the following is true (example on 285714)
 §               -- | fork
         §       -- | | fork
              /  -- | | | divide by x: 142857
                 -- | | and
             *   -- | | | multiply by y: 571428
                 -- | | then do the following with 142857 and 571428
                 -- | | | concatenate but first take
           +     -- | | | | digits: [1,4,2,8,5,7] [5,7,1,4,2,8]
          ¤ d    -- | | | : [1,4,2,8,5,7,5,7,1,4,2,8]
                 -- | and
       d         -- | | digits: [2,8,5,7,1,4]
      D          -- | | double: [2,8,5,7,1,4,2,8,5,7,1,4]
                 -- | then do the following with [2,8,5,7,1,4,2,8,5,7,1,4] and [1,4,2,8,5,7,5,7,1,4,2,8]
   =             -- | | are they equal
  ¤ O            -- | | | when sorted: [1,1,2,2,4,4,5,5,7,7,8,8] [1,1,2,2,4,4,5,5,7,7,8,8]
                 -- | : truthy
                 -- : 285714
ბიმო
fonte
Ajustei o valor para y para obter um ponto de partida mais próximo e o resultado estava incorreto para x = 3, y = 25000000 .
Emma - PerpetualJ
@PerpetualJ: Se você conhece o resultado, pode simplesmente ajustar y , e esta versão deve ser um pouco mais rápida (apenas a verificação de tipo).
ბიმო
Eu o ajustei após algumas reflexões e editei meu primeiro comentário.
Emma - PerpetualJ
@PerpetualJ: Eu consertei: fiz uma suposição sobre o -que estava errado.
ბიმო
11
@PerpetualJ: Eu escrevi o programa;) Eu adicionei uma explicação, agora todos devem entender o que está acontecendo.
ბიმო
5

Brachylog v2, 15 bytes

t<.g,?kA/p.∧A×p

Experimente online!

Recebe entrada no formulário [x,y].

Explicação

t<.g,?kA/p.∧A×p
t                  Tail (extract y from the input)
 <                 Brute-force search for a number > y, such that:
  .                  it's the output to the user (called ".");
   g                 forming it into a list,
    ,?               appending both inputs (to form [.,x,y]),
      k              and removing the last (to form [.,x])
       A             gives a value called A, such that:
        /              first ÷ second element of {A}
         p             is a permutation of
          .            .
           ∧         and
            A×         first × second element of {A}
              p        is a permutation of {.}

Comentário

A fraqueza de Brachylog em reutilizar vários valores várias vezes aparece aqui; este programa é quase todo encanamento e muito pouco algoritmo.

Como tal, pode parecer mais conveniente simplesmente codificar o valor de y (há um comentário sobre esta questão, na hipótese de que 2 é o único valor possível). No entanto, existem de fato soluções para y = 3, o que significa que, infelizmente, o encanamento também tem que lidar com o valor de y . O menor que eu conheço é o seguinte:

                         315789473684210526
315789473684210526 × 3 = 947368421052631578
315789473684210526 ÷ 3 = 105263157894736842

(A técnica que eu usei para encontrar esse número não é totalmente geral, portanto, é possível que exista uma solução menor usando outra abordagem.)

É improvável que você verifique isso com este programa. O Brachylog's pé escrito de uma maneira muito geral que não possui otimizações para casos especiais (como o caso em que tanto a entrada quanto a saída já são conhecidas, o que significa que você pode fazer a verificação em O ( n log n ) por meio de classificação, em vez disso do que o O ( n !) para a abordagem de força bruta que eu suspeito que esteja usando). Como conseqüência, leva muito tempo para verificar se 105263157894736842 é uma permutação de 315789473684210526 (eu o deixo em execução há vários minutos sem progresso óbvio).

(EDIT: verifiquei a fonte Brachylog pelo motivo. Acontece que, se você usar pem dois inteiros conhecidos, o algoritmo usado gera todas as permutações possíveis do número inteiro em questão até encontrar um que seja igual ao número inteiro de saída, como o algoritmo é "input → indigits, permute indigits → outdigits, outdigits → output". Um algoritmo mais eficiente seria configurar primeiro a relação outdigits / output , para que o retorno dentro da permutação levasse em consideração quais dígitos estavam disponíveis.)

ais523
fonte
Usar um garfo pode diminuir seu código em 1 byte. Experimente online!
Kroppeb 28/09
Ainda de acordo com os documentos, parece verificar se duas listas conhecidas são uma permutação é O (n²) swi-prolog.org/pldoc/man?predicate=permutation/2
Kroppeb
@ Kroppeb: o problema é que o Brachylog's pnão roda permutation/2com duas listas conhecidas, mesmo quando dados dois inteiros conhecidos como argumentos; gera todas as permutações do primeiro inteiro (utilizando permutation/2com uma lista conhecida) e, em seguida, compara-os contra o segundo número inteiro.
ais523
4

Perl 6 , 56 54 bytes

->\x,\y{(y+1...{[eqv] map *.comb.Bag,$_,$_*x,$_/x})+y}

Experimente online!

Alternativa interessante, computando n * x k para k = -1,0,1:

->\x,\y{first {[eqv] map ($_*x***).comb.Bag,^3-1},y^..*}
Nwellnhof
fonte
3

Limpo , 92 bytes

import StdEnv
$n m=hd[i\\i<-[m..],[_]<-[removeDup[sort[c\\c<-:toString j]\\j<-[i,i/n,i*n]]]]

Experimente online!

Bem simples. Explicação daqui a pouco.

Furioso
fonte
3

q, 65 bytes

{f:{asc 10 vs x};while[not((f y)~f y*x)&(f y*x)~f"i"$y%x;y+:1];y}

Divida o número na base 10, classifique cada ascendente e verifique se é igual. Caso contrário, aumente y e vá novamente

Thaufeki
fonte
3

JavaScript (ES6), 76 73 69 bytes

Salva 3 bytes usando eval(), conforme sugerido por @ShieruAsakoto

Toma entrada como (x)(y).

x=>y=>eval("for(;(g=x=>r=[...x+''].sort())(y*x)+g(y/x)!=g(y)+r;)++y")

Experimente online!

Uma versão recursiva teria 62 bytes , mas não é adequada aqui devido ao alto número de iterações necessárias.

Como?

A função auxiliar pega um número inteiro como entrada, converte-o em uma matriz de caracteres de dígitos e classifica essa matriz.g

Exemplo:

g(285714) = [ '1', '2', '4', '5', '7', '8' ]

Para comparar os dígitos de e os de com os de , testamos se a concatenação de com é igual à concatenação de consigo mesmo.y×xy/xyg(y×x)g(y/x)g(y)

Ao adicionar duas matrizes, cada uma delas é implicitamente coagida a uma cadeia de caracteres separada por vírgula. O último dígito da primeira matriz será diretamente concatenado com o primeiro dígito da segunda matriz sem vírgula entre elas, o que torna esse formato inequívoco.

Exemplo:

g(123) + g(456) = [ '1', '2', '3' ] + [ '4', '5', '6' ] = '1,2,34,5,6'

Mas:

g(1234) + g(56) = [ '1', '2', '3', '4' ] + [ '5', '6' ] = '1,2,3,45,6'

Comentado

x => y =>                   // given x and y
  eval(                     // evaluate as JS code:
    "for(;" +               //   loop:
      "(g = x =>" +         //     g = helper function taking x
        "r =" +             //       the result will be eventually saved in r
          "[...x + '']" +   //       coerce x to a string and split it
          ".sort() + ''" +  //       sort the digits and coerce them back to a string
      ")(y * x) +" +        //     compute g(y * x)
      "g(y / x) !=" +       //     concatenate it with g(y / x)
      "g(y) + r;" +         //     loop while it's not equal to g(y) concatenated with
    ")" +                   //     itself
    "++y"                   //   increment y after each iteration
  )                         // end of eval(); return y
Arnauld
fonte
66: x=>F=y=>(g=x=>r=[...x+''].sort()+'')(y*x)!=g(y)|r!=g(y/x)?F(y+1):yPode causar estouro de pilha se y estiver longe da solução.
Shieru Asakoto 28/09
ou 75 usando eval:x=>y=>eval("for(;(g=x=>r=[...x+''].sort()+'')(y*x)!=g(y)|r!=g(y/x);y++);y")
Shieru Asakoto 28/09
@ShieruAsakoto Obrigado pela eval()ideia. Minha primeira tentativa foi de fato recursiva, mas desisti por causa do alto número de iterações necessárias.
Arnauld
3

Haskell, 76 74 bytes

Dois bytes cortados graças ao comentário de Lynn

import Data.List
s=sort.show
x#y=[n|n<-[y+1..],all(==s n)[s$n*x,s$n/x]]!!0
umnikos
fonte
11
Para o mesmo byte contar a sua fpode ser f x y=[n|n<-[y+1..],all(==s n)[s$n*x,s$n/x]]!!0, mas, em seguida, definir a sua resposta como um operador poupa dois bytes: x!y=…e, em seguida, sua resposta é (!):)
Lynn
Não pensou em usar compreensões de lista! Obrigado pela sugestão: D
umnikos
2

Japonês, 24 bytes

Solução bastante ingênua com algumas cervejas; Tenho certeza de que há uma maneira melhor.

@[X*UX/U]®ì nÃeeXì n}a°V

Tente

Shaggy
fonte
Infelizmente, isso produz um resultado incorreto quando x = 3 e y = 25000 .
Emma - PerpetualJ
@PerpetualJ Assumindo que 315789473684210526é a primeira solução x=3, Javascript ou Japt não podem computá-lo corretamente, pois não se encaixa em dupla precisão.
borbulhador
@PerpetualJ, corrigiu isso anteriormente. Esse caso de teste nunca será concluído, pelo motivo mencionado pelo Bubbler acima.
Shaggy
@ Shaggy Agora, esse resultado é correto e a solução apontada pelo Bubbler não é o primeiro resultado correto acima de 25000 . Veja meus casos de teste, se você estiver curioso sobre isso. +1
Emma - PerpetualJ
1

Python 2 , 69 bytes

S=sorted
x,y=input()
while(S(`y`)==S(`y*x`)==S(`y/x`))<1:y+=1
print y

Experimente online!

Chas Brown
fonte
f=lambda x,y,S=sorted:y*(S(`y`)==S(`y*x`)==S(`y/x`))or f(x,y+1)deve funcionar, mas atinge o limite de recursão rapidamente, e não sei o que as regras do PPCG têm a dizer sobre isso.
Lynn
1

Geléia ,  14  13 bytes

-1 graças a Erik the Outgolfer (`` usa make_digits, portanto Dnão era necessário)
+2 corrigindo um bug (obrigado novamente a Erik the Outgolfer por apontar o problema inicial)

×;÷;⁸Ṣ€E
‘ç1#

Um programa completo imprimindo o resultado (como um link diádico é gerada uma lista de comprimento 1).

Experimente online!

Como?

×;÷;⁸Ṣ€E - Link 1, checkValidity: n, x               e.g. n=285714,  x=2
×        -     multiply -> n×x                       571428
  ÷      -     divide -> n÷x                         142857
 ;       -     concatenate -> [n×x,n÷x]              [571428,142857]
    ⁸    -     chain's left argument = n             285714
   ;     -     concatenate -> [n×x,n÷x,n]            [571428,142857,285714]
     Ṣ€  -     sort €ach (implicitly make decimals)  [[1,2,4,5,7,8],[1,2,4,5,7,8],[1,2,4,5,7,8]]
        E    -     all equal?                        1

‘ç1# - Main link: y, x
‘    - increment -> y+1
   # - count up from n=y+1 finding the first...
  1  - ...1 match of:
 ç   -   the last link (1) as a dyad i.e. f(n, x)

Observe que, quando a divisão não é exata, a instrução decimal implícita (equivalente a D) aplicada antes da classificação produz uma parte fracionária,
por exemplo: 1800÷3D-> [6,0,0]
while 1801÷3D->[6.0,0.0,0.33333333333337123]

Jonathan Allan
fonte
Não tenho certeza se essa resposta é válida; o desafio exige que o resultado seja "maior que y ", que interpreto como "estritamente maior que Y ". Além disso, você não precisa D.
Erik the Outgolfer
Ah, bom lugar, >=eu perdi totalmente isso! Não tinha idéia de make_digits definido nele - obrigado. Terá que consertar e atualizar mais tarde ...
Jonathan Allan #
1

Mathematica, 82 74 bytes

x=Sort@*IntegerDigits;Do[If[x[i#]==x@Floor[i/#]==x@i,Break@i],{i,#2,∞}]&

-8 bytes graças ao tsh

Função que aceita argumentos como [x,y]. Efetivamente procurar uma força bruta que verifica se a lista ordenada de dígitos para y, y/xe xysão os mesmos.

Experimente online!

numbermaniac
fonte
Não estou familiarizado com o Mathematica. Mas pode-se provar que a resposta ainda estaria correta se você soltar a parte fracionária da divisão: todos ans, ans / x, ans * x devem ser divisíveis por 9. E isso pode tornar sua solução mais curta.
tsh
@tsh Isso funciona para x=3, mas não tenho certeza se é verdade x=2.
Ørjan Johansen
@ ØrjanJohansen Let v = a[1]*10^p[1] + a[2]*10^p[2] + ... + a[n]*10^p[n], u = a[1] * 10^q[1] + ... + a[n] * 10^q[n]. E já u-v = a[1]*(10^p[1]-10^q[1]) + ... + a[n]*(10^p[n]-10^q[n])que 10^x-10^y=0 (mod 9)sempre vale. u-v=0 (mod 9)sempre segura. Se houver uma resposta errada w, uma vez que w*x-w=0 (mod 9), e w-floor(w/x)=0 (mod 9): temos floor(w/x)=0 (mod 9). se floor(w/x)*x <> w, w-floor(w/x)*x>=9mas este conflito com o fato de que w-floor(w/x)*x<x, enquanto x poderia ser 2 ou 3.
TSH
@tsh Obrigado! Para o benefício de outras pessoas que demoram muito para entender esse ponto, w=0 (mod 9)segue-se w*x-w=0 (mod 9)porque x-1não é divisível por 3. #
Ørjan Johansen
Se eu excluir o IntegerQteste, ele produz alguns erros quando tenta com IntegerDigitsfrações, mas o Mathematica ainda os ultrapassa e produz a resposta correta. Não tenho certeza se os erros incluídos durante o cálculo serão permitidos, mesmo que a resposta final esteja correta.
Numbermaniac #
0

APL (NARS), 490 caracteres, 980 bytes

T←{v←⍴⍴⍵⋄v>2:7⋄v=2:6⋄(v=1)∧''≡0↑⍵:4⋄''≡0↑⍵:3⋄v=1:5⋄⍵≢+⍵:8⋄⍵=⌈⍵:2⋄1}
D←{x←{⍵≥1e40:,¯1⋄(40⍴10)⊤⍵}⍵⋄{r←(⍵≠0)⍳1⋄k←⍴⍵⋄r>k:,0⋄(r-1)↓⍵}x}
r←c f w;k;i;z;v;x;y;t;u;o ⍝   w  cxr
   r←¯1⋄→0×⍳(2≠T c)∨2≠T w⋄→0×⍳(c≤1)∨w<0⋄→0×⍳c>3
   r←⌊w÷c⋄→Q×⍳w≤c×r⋄r←r+c
Q: u←D r⋄x←1⊃u⋄y←c×x⋄t←c×y⋄o←↑⍴u⋄→0×⍳o>10⋄→A×⍳∼t>9
M:                     r←10*o⋄⍞←r⋄→Q
A: u←D r⋄→M×⍳x≠1⊃u⋄→B×⍳∼(t∊u)∧y∊u⋄z←r×c⋄v←D z⋄→C×⍳(⍳0)≡v∼⍦u
B: r←r+1⋄→A
C: k←z×c⋄⍞←'x'⋄→B×⍳(⍳0)≢v∼⍦D k
   ⎕←' '⋄r←z

teste

  2 f¨250000 290000 3000000
xxxx 
1000000xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 
10000000xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 
285714 2589714 20978514 
 3 f¨ 31000000 290000000 
xxxxxxxxx 
100000000xxxxxxxxxxxxxxxxxxxxxxxxxx 
31046895 301046895 

Eu pensei que o problema era um número conveniente ra que pode variar, de modo que se tenha os 3 números r, r * x, r * x * x no modo r começa a um valor em que r * x está próximo de y (onde xey são entradas do problema usando as mesmas letras da postagem principal). Utilizei a observação de que se o primeiro dígito de r é d, em que r deve aparecer também os dígitos d * x e d * x * x, para tornar r (ou melhor r * x) uma solução.

RosLuP
fonte
0

05AB1E , 16 bytes

[>©Ð²÷s²*)€{Ë®s#

Experimente online. (OBSERVAÇÃO: Solução muito ineficiente, use entradas próximas ao resultado. Funciona também para entradas maiores localmente, mas no TIO o tempo limite será excedido após 60 s.)

Explicação:

[                   # Start an infinite loop
 >                  #  Increase by 1 (in the first iteration the implicit input is used)
  ©                 #  Store it in the register (without popping)
   Ð                #  Triplicate it
    ²÷              #  Divide it by the second input
      s             #  Swap so the value is at the top of the stack again
       ²*           #  Multiply it by the second input
         )          #  Wrap all the entire stack (all three values) to a list
          €{        #  Sort the digits for each of those lists
             ®s     #  Push the value from the register onto the stack again
            Ë       #  If all three lists are equal:
               #    #   Stop the infinite loop
Kevin Cruijssen
fonte