Crédito para Geobits na TNB pela ideia

Um post sem detalhes suficientes postou recentemente um jogo interessante:

2 crianças sentam-se na frente de uma variedade de doces. Cada pedaço de doce é numerado de 1 a x, xsendo a quantidade total de presente presente. Há exatamente 1 ocorrência de cada número.

O objetivo do jogo é que as crianças comam doces e multipliquem os valores dos doces que comeram para chegar a uma pontuação final, obtendo a pontuação mais alta.

No entanto, a postagem original perdeu informações importantes, como a seleção de doces, para que as crianças de nossa história decidissem que a criança mais velha iria primeiro e pudessem comer até metade do doce, no entanto, depois que ele anuncia o fim de seu turno, ele não pode mudar de idéia.

Uma das crianças deste jogo não gosta de doces, então ele quer comer o mínimo possível, e uma vez viu o pai escrever algum código uma vez e acha que pode usar as habilidades adquiridas com isso para descobrir quanto doce ele precisa comer para garantir a vitória, enquanto ainda come o mínimo possível.

O desafio

Dado o número total de doces x, seu programa ou função deve produzir a menor quantidade de doces que ele precisa comer para garantir a vitória n, mesmo que o oponente coma todo o restante do doce.

Números naturalmente maiores produzem números maiores, então, qualquer que seja a quantia que você lhe der, ele comerá os nmaiores números.

As regras

• xsempre será um número inteiro positivo no intervalo em 0 < x! <= lque lestá o limite superior dos recursos de manipulação de números do seu idioma
• É garantido que o garoto sempre coma o nmaior número, por exemplo, para x = 5e n = 2, ele coma 4e5

Casos de teste

x = 1
n = 1
(1 > 0)

x = 2
n = 1
(2 > 1)

x = 4
n = 2
(3 * 4 == 12 > 1 * 2 == 2)

x = 5
n = 2
(4 * 5 == 20 > 1 * 2 * 3 == 6)

x = 100
n = 42
(product([59..100]) > product([1..58]))

x = 500
n = 220
(product([281..500]) > product([1..280]))

Pontuação

Infelizmente, nosso corajoso concorrente não tem nada com o qual escrever seu código; portanto, ele precisa organizar os pedaços de doces nos caracteres do código; como resultado, seu código precisa ser o menor possível, o menor código em bytes ganha!

Python 3 , 76 bytes

F=lambda x:x<2or x*F(x-1)
f=lambda x,n=1:x<2or n*(F(x)>F(x-n)**2)or f(x,n+1)

Experimente online!

Conta com o fato de que, para comer $n$ balas, ainda ganha e o número total de balas sendo $x$ , $\frac{x!}{(x-n)!}>(x-n)!$deve ser verdadeiro, o que significa$x!>((x-n)!)^2$.

-1 de Skidsdev

-3 -6 do BMO

-3 de Sparr

+6 para corrigir x = 1

JavaScript (ES6), 53 bytes

n=>(g=p=>x<n?g(p*++x):q<p&&1+g(p/n,q*=n--))(q=x=1)||n

Experimente online!

Área de trabalho

Curiosamente, as diferenças entre os produtos infantis são sempre grandes o suficiente para que a perda de precisão inerente à codificação IEEE 754 não seja um problema.

Como resultado, ele funciona para $0 \le n \le 170$ . Além disso, a mantissa e o expoente estouram (produzindo + Infinito ) e precisaríamos de BigInts (+1 byte).

Quão?

Seja $p$ o doce da outra criança e $q$ seja o nosso próprio doce.

1. Começamos com $p=n!$(todos os doces para a outra criança) $q=1$ (nada para nós).

2. Repetimos as seguintes operações até $q\ge p$ :

   • dividir $p$ por $n$
   • multiplique $q$ por $n$
   • decremento $n$

O resultado é o número de iterações necessárias. (A cada iteração, 'pegamos o próximo doce mais alto do outro garoto'.)

Comentado

Isso é implementado como uma única função recursiva que primeiro calcula $n!$e então entra no loop descrito acima.

n => (           // main function taking n
  g = p =>       // g = recursive function taking p
    x < n ?      //   if x is less than n:
      g(         //     this is the first part of the recursion:
        p * ++x  //     we're computing p = n! by multiplying p
      )          //     by x = 1 .. n
    :            //   else (second part):
      q < p &&   //     while q is less than p:
      1 + g(     //       add 1 to the final result
        p / n,   //       divide p by n
        q *= n-- //       multiply q by n; decrement n
      )          //
)(q = x = 1)     // initial call to g with p = q = x = 1
|| n             // edge cases: return n for n < 2

Geléia , 9 bytes

ḊPÐƤ<!€TL

Experimente online! Ou veja a suíte de testes .

Quão?

ḊPÐƤ<!€TL - Link: integer, x                   e.g. 7
Ḋ         - dequeue (implicit range of x)           [   2,   3,   4,   5,   6,   7]
  ÐƤ      - for postfixes [all, allButFirst, ...]:
 P        -   product                               [5040,2520, 840, 210,  42,   7]
      €   - for each (in implicit range of x):
     !    -   factorial                             [   1,   2,   6,  24, 120, 720, 5040]
    <     - (left) less than (right)?               [   0,   0,   0,   0,   1,   1, 5040]
          -   -- note right always 1 longer than left giving trailing x! like the 5040 ^
       T  - truthy indices                          [                       5,   6, 7   ]
        L - length                                  3

R , 70 41 38 bytes

-29 porque Dennis conhece todas as funções internas

-3 alternando para a entrada scan ()

sum(prod(x<-scan():1)<=cumprod(1:x)^2)

Experimente online!

Implementação R bastante simples da resposta Python3 de nedla2004 .

Sinto que há uma implementação mais limpa do manuseio 1 e gostaria de perder o aparelho.

Estou bravo por não voltar a usar uma abordagem que, mais bravo por usar um estrito menos do que, mas ainda mais bravo por não saber que há uma cumprod()função. Ótima otimização por Dennis.

APL (Dyalog Unicode) , 10 bytes

+/!≤2*⍨!∘⍳

Experimente online!

Resposta do porto de Dennis . Obrigado ao Dennis por isso.

Quão:

+/!≤2*⍨!∘⍳ ⍝ Tacit function, takes 1 argument (E.g. 5)
         ⍳ ⍝ Range 1 2 3 4 5
       !∘  ⍝ Factorials. Yields 1 2 6 24 120
    2*⍨    ⍝ Squared. Yields 1 4 36 576 14400
  !        ⍝ Factorial of the argument. Yields 120.
   ≤       ⍝ Less than or equal to. Yields 0 0 0 1 1
+/         ⍝ Sum the results, yielding 2.

Como essa resposta não foi feita estritamente por mim, manteremos minha resposta original abaixo.

APL (Dyalog Unicode) , 14 12 11 bytes

(+/!>×\)⌽∘⍳

Experimente online!

Função de prefixo tácito. Basicamente, um porto Dyalog da resposta de Jonathan .

Obrigado a ngn e H.PWiz pela ajuda no chat. Obrigado a ngn também por me salvar um byte.

Obrigado a Dennis por apontar que meu código original estava errado. Acontece que me salvou 2 bytes.

Usos ⎕IO←0.

Quão:

+/(!>×\)∘⌽∘⍳ ⍝ Tacit function, taking 1 argument (E.g. 5).
           ⍳ ⍝ Range 0 1 2 3 4
         ⌽∘  ⍝ Then reverse, yielding 4 3 2 1 0
  (    )∘    ⍝ Compose with (or: "use as argument for")
   !         ⍝ Factorial (of each element in the vector), yielding 24 6 2 1 1
     ×\      ⍝ Multiply scan. Yields 4 12 24 24 0
    >        ⍝ Is greater than. Yields 1 0 0 0 1
+/           ⍝ Finally, sum the result, yielding 2.

Haskell , 52 51 bytes

$n$$\frac{x!}{(x-n)!}$$n$$(x-n)!$$n$

g b=product[1..b]
f x=[n|n<-[1..],g(x-n)^2<=g x]!!0

Experimente online!

Geléia , 7 bytes

R!²<!ċ0

Experimente online!

Como funciona

R!²<!ċ0  Main link. Argument: n

R        Range; yield [1, ..., n].
 !       Map factorial over the range.
  ²      Take the squares of the factorials.
    !    Compute the factorial of n.
   <     Compare the squares with the factorial of n.
     ċ0  Count the number of zeroes.

Python 3 , 183 176 149 bytes

R=reversed
def M(I,r=1):
 for i in I:r*=i;yield r
def f(x):S=[*range(1,x+1)];return([n for n,a,b in zip([0]+S,R([*M(S)]),[0,*M(R(S))])if b>a]+[x])[0]

Experimente online!

É muito mais rápido que algumas outras soluções - multiplicações 0 (N) em vez de O (N²) - mas não consigo reduzir o tamanho do código.

-27 de Jo King

Limpo , 57 bytes

import StdEnv
$x=while(\e=prod[1..x-e]^2>prod[1..x])inc 1

Experimente online!

Uma solução direta.

05AB1E , 15 11 bytes

E!IN-!n›iNq

Experimente online!

E!IN-!n›iNq

E                For loop with N from [1 ... input]
 !               Push factorial of input    
  IN-            Push input - N (x - n)
     !           Factorial
      n          Square
       ›         Push input! > (input - N)^2 or x! > (x - n)^2
        i        If, run code after if top of stack is 1 (found minimum number of candies)
         N       Push N
          q      Quit, and as nothing has been printed, N is implicitly printed

Usa a mesma abordagem que meu envio do Python . Muito novo para 05AB1E, portanto, qualquer dica sobre código ou explicação é muito apreciada.

-4 bytes graças a Kevin Cruijssen

Gelatina , 14 bytes

ạ‘rP>ạ!¥
1ç1#«

Experimente online!

Manipula 1 corretamente.

Carvão , 20 bytes

ＮθＩ⊕ΣＥθ‹Π⊕…ιθ∨Π…¹⊕ι¹

Experimente online!Link é a versão detalhada do código. Explicação:

Ｎθ                      Input `n`
    Σ                   Sum of
      θ                 `n`
     Ｅ                  Mapped over implicit range
        Π               Product of
           ι            Current value
          …             Range to
            θ           `n`
         ⊕              Incremented
       ‹                Less than
              Π         Product of
                ¹       Literal 1
               …        Range to
                  ι     Current value
                 ⊕      Incremented
             ∨          Logical Or
                   ¹    Literal 1
   ⊕                    Incremented
  Ｉ                     Cast to string
                        Implicitly print

Productem uma lista vazia em Charcoal retorna em Nonevez de 1, então eu tenho que logicamente Or.

PHP , 107 bytes

<?php $x=fgets(STDIN);function f($i){return $i==0?:$i*f($i-1);}$n=1;while(f($x)<f($x-$n)**2){$n++;}echo $n;

Experimente online!

Usa o mesmo $x^2>((x-1)!)^2$ método como outros usaram.

Usa a função fatorial da submissão do PHP para este desafio (graças a @ donutdan4114)

Wolfram Language (Mathematica) , 43 bytes

Min[n/.Solve[#!>(#-n)!^2, Integers]]/.n->1&

Experimente online!

05AB1E , 7 bytes

L!ns!@O

Resposta de Port of Dennis ♦ 'Jelly , por isso, certifique-se de vomitá-lo se você gosta desta resposta!

Experimente online ou verifique todos os casos de teste .

Explicação:

L          # List in the range [1, (implicit) input]
 !         # Take the factorial of each
  n        # Then square each
   s!      # Take the factorial of the input
     @     # Check for each value in the list if they are larger than or equal to the
           # input-faculty (1 if truthy; 0 if falsey)
      O    # Sum, so determine the amount of truthy checks (and output implicitly)

Japt -x , 7 bytes

Solução de geléia no porto de Dennis.

Só funciona na prática até n=4quando entramos em notação científica acima disso.

õÊ®²¨U²

Tente

õ           :Range [1,input]
 Ê          :Factorial of each
  ®         :Map
   ²        :  Square
    ¨       :  Greater than or equal to
     U²     :  Input squared
            :Implicitly reduce by addition

C # (.NET Core) , 93 bytes

n=>{int d(int k)=>k<2?1:k*d(k-1);int a=1,b=d(n),c=n;for(;;){a*=n;b/=n--;if(a>=b)return c-n;}}

Experimente online!

Baseado na resposta javascript de @ Arnauld.

C (gcc) , 68 bytes

n;f(x){int i=2,j=x,b=1,g=x;while(i<j)b*i>g?g*=--j:(b*=i++);n=x-j+1;}

Experimente online!

Edit: troca de bytes contra mults, sem fazer 2 * x mults em vez de x + n

Editar: voltando ao int em vez da macro longa. Falharia aos 34 com muito tempo.

Bem, eu tenho isso em C. Falha em 21.

Existe uma possível ambiguidade sobre se o bom garoto sempre quer vencer ou nunca perder ... o que você acha?

Python 3 , 75 bytes

f=lambda n:n<1or f(n-1)*n
n=lambda x:x-sum(f(n)**2<f(x)for n in range(1,x))

Experimente online!

Versão de 74 bytes

f=lambda n:n<1or f(n-1)*n
n=lambda x:1+sum(f(n)>f(x)**.5for n in range(x))

mas esta versão transbordou para 500 ...