Inspirado en /puzzling//q/626

En tus aventuras llegas a una serie de 7 puentes que tienes que cruzar. Debajo de cada puente vive un troll. Para cruzar el puente, primero debes darle al troll una cantidad de pasteles como porcentaje del número de pasteles que llevas. Debido a que estos son trolls amables, te devolverán una cierta cantidad de pasteles.

Al comienzo de cada día, el rey troll local establece el porcentaje de impuesto a la torta que cada viajero debe pagar, y el reembolso de la torta troll: la cantidad de tortas que cada troll debe devolver a los viajeros.

Su trabajo es calcular la cantidad mínima de pasteles necesarios para pasar los 7 puentes troll para las condiciones dadas en ese día.

Asumir:

1. Dos parámetros de entrada: porcentaje de impuesto a la torta (entero de 0 a 100) y reembolso de la torta de trol
2. Nadie, ni siquiera los trolls, quiere un pastel parcialmente comido por otro troll. Si te queda una fracción de pastel, el troll lo consigue.
3. Si un troll acepta un impuesto sobre los pasteles, pero luego tiene que devolverle todos los pasteles (se queda con los mismos o menos pasteles que antes), se enojará y se comerá a usted y sus pasteles.
4. Cada troll debe conservar al menos un pastel completo.
5. Solo puedes llevar un máximo de 100 pasteles.
6. Debe finalizar el día en el que se encuentra actualmente o al otro lado de los 7 puentes.

Desafío:

Escriba un programa completo para generar el número mínimo de pasteles para viajar para el día actual o cero si no es posible viajar hoy con seguridad; esperará para ver cuáles son los números mañana.

La entrada debe pasarse como stdin, argumentos de línea de comando o entrada de archivo.

El código más corto (recuento de bytes) gana.

Ejemplo:

25% de impuesto sobre la torta, reembolso del pastel de 2 troll.

comience con 19 pasteles
antes del troll 1: (19 * 0.75) = 14.25
después del troll 1: (14 + 2) = 16

antes del troll 2: (16 * 0.75) = 12
después del troll 2: (12 + 2) = 14

etc.

19 pasteles -> 16 -> 14 -> 12 -> 11 -> 10 -> 9 -> 8
18 pasteles -> 15 -> 13 -> 11 -> 10 -> 9 -> 8 -> 8 (regla 3)

Para 18 pasteles, el último troll no podría quedarse con ningún pastel. Por lo tanto, el número mínimo de pasteles para un 25% / 2 días es 19.

input: 25 2
output: 19

Ejemplo 2

90% de impuesto sobre la torta, 1 reembolso de la torta troll

100 pasteles -> 11 -> 2 -> 1 (regla 4)

El tercer troll no pudo quedarse con ningún pastel. Por lo tanto, no es posible viajar en un 90% / 1 día incluso comenzando con el número máximo de pasteles.

input: 90 1
output: 0

Datos

Prepare un gráfico rápido de valores de entrada y salida. Me sorprendió que esto no fuera "suave" (como una curva de campana o similar); Hay varias islas notables.

Datos para los interesados. Las columnas se dividen en intervalos de 5%, las filas son unidades de intervalos de reembolso de 1 torta (Excel rotó la imagen). Puede ver que no puede haber un reembolso superior a 28 tortas.

27, 17, 13, 14, 15, 18, 20, 24, 53, 66, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
47, 27, 20, 19, 19, 19, 24, 39, 48, 68, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0
67, 37, 28, 24, 23, 28, 27, 29, 50, 70, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
87, 47, 33, 29, 27, 28, 31, 44, 37, 72, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 57, 40, 34, 31, 29, 34, 34, 62, 74, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 67, 48, 39, 35, 38, 37, 49, 57, 76, 92, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 77, 53, 44, 39, 38, 47, 39, 59, 78, 94, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 87, 60, 49, 43, 39, 40, 54, 46, 80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 97, 68, 54, 47, 48, 44, 44, 71, 82, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 73, 59, 51, 48, 47, 59, 73, 84, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 80, 64, 55, 49, 51, 49, 68, 86, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 88, 69, 59, 58, 54, 64, 70, 88, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 93, 74, 63, 58, 57, 54, 57, 90, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 100, 79, 67, 59, 67, 69, 82, 92, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 84, 71, 68, 60, 59, 77, 94, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 89, 75, 68, 64, 74, 79, 96, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 94, 79, 69, 67, 64, 66, 98, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 99, 83, 78, 71, 79, 91, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 87, 78, 74, 69, 93, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 91, 79, 77, 84, 88, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 95, 88, 87, 74, 90, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 99, 88, 80, 89, 77, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 89, 84, 79, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 98, 87, 94, 97, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 98, 91, 84, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 99, 94, 99, 86, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 97, 89, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

CJam, 46 43 41 39 38 36 33 bytes

100:H,{)_7{ea:i~H@m2$*H/+@;}*>}#)

Entrada a través de ARGV.

Hay un intérprete en línea, pero desafortunadamente no admite argumentos de línea de comandos. Para probar, puedes imitarlo desde STDIN con esta versión:

rr]:A;
100:H,{)_7{A:i~H@m2$*H/+@;}*>}#)

Explicación de la versión basada en ARGV:

100:H                                  "Push a 100 and save it in H.";
     ,                                 "Create a range (as an array) from 0 to 99.";
      {                       }#       "Find the first index in [0,1,2,...,99] for which the
                                        block produces a truthy (non-zero) value.";
       )_                              "Increment and duplicate the current array element.";
         7{                }*          "Execute the block seven times.";
           ea:i                        "Push the command-line arguments as an array of strings
                                        and convert each element to an integer";
               ~                       "Unwrap the array.";
                H@                     "Push a 100 and rotate the stack to pull up
                                        the first command line argument.";
                  m                    "Subtract (from 100).";
                   2$                  "Copy the last iterations result.";
                     *H/               "Multiply and divide by 100, deducting tax.";
                        +              "Add the refund.";
                         @;            "Rotate top three stack elements, and discard the one that 
                                        has been pulled to the top. This always leaves the last 
                                        two results on the stack.";

                             >         "Make sure that the last result was less than the second 
                                        to last. Yields 0 or 1.";
                                )      "After the # search completes, we'll get -1 if no such 
                                        index exists, or one less than the desired number if it 
                                        does, so we can just increment.";

El contenido de la pila se imprime automáticamente al final del programa.

CJam, 44 40 38 37 35 bytes

l~U100:M),{{_M5$-*M/3$+_@<*}7*}=]W=

O al usar argumentos y {}#trucos de la línea de comandos , 33 bytes :

100:M,{){_ea:i~M@-@*M/+_@<*}7*}#)

No poner este como mi {}#enfoque principal se inspira en la respuesta de Martin.

Ejemplo de ejecución:

Entrada:

25 2

Salida:

19

Otro:

Entrada:

15 14

Salida:

100

Cómo funciona

l~                       "Read the two numbers, swap and convert tax to double";
  U100:M),               "Push 0 and [0, 1, ... 100] to stack, storing 100 in M";
          {  ...  }=     "Run this code for each element until top stack element is 1";
           {...}7*       "Run this code block 7 times";
_                        "Copy the array element";
  M5$                    "Push 100 and a copy tax % to stack";
     -*                  "Number = (100 - tax %) * Number";
       M/                "Integer divide the number by 100";          
         3$+             "Add refund";
            _@<*         "Convert to 0 if refunded number > before tax one";
                    ]W=  "Take the last element of the stack";

Pruébalo en línea aquí

APL (39)

T R←⎕⋄⊃Z/⍨{⍵(⊢×>)R+⌊⍵×1-T÷M}⍣7¨Z←⍳M←100

Explicación:

• T R←⎕: lea dos números desde el teclado y guárdelos en T(impuesto) y R(devolución).
• Z←⍳M←100: almacena el número 100en M, y todos los números de 1a 100en Z.
• {... }⍣7¨: para cada elemento en Z, ejecute la siguiente función 7 veces:
  • R+⌊1-T÷M: calcular cuántos pasteles hay que pagar,
  • ⍵(⊢×>): multiplica esa cantidad por 1 si el troll termina con más torta de la que comenzó, o por 0 si no.
• ⊃Z/⍨: para cada elemento Z, repítalo por el número que le dio esa función. (De modo que todos los números para los que la función regresó 0desaparecen). Luego, seleccione el primer elemento de esa lista. Si la lista terminó vacía, esto da 0.

C, 83 bytes

int cake(int perc_taken, int given_back)
{
    int startcake = floor(100.f/perc_taken*given_back+1);
    for(int i = 0; i < 6; i++)
    {
        startcake = ceil((startcake-given_back) * 100.f/(100 - perc_taken));
    }
    return startcake;
}

Si funciona, funciona para todos los pasteles de inicio posibles, no solo del 1 al 100.

EDITAR: funciona. Golfizado:

n(int p,int g) {int s=100./p*g+1,i=0;for(;i++<6;){s=ceil((s-g)*100./(100-p));}return s;}

Con el límite 'máximo de 100 pasteles':

n(int p,int g) {int s=100./p*g+1,i=0;for(;i++<6;){s=ceil((s-g)*100./(100-p));}return s>100?0:s;}

91 bytes.

CJam, 36 bytes

q~:R100:H*\d:T/i){R-H*HT-/m]}6*_H)<*

C ++ - 202 caracteres

Como de costumbre, mi C ++ hizo lo peor:

#include<iostream>
int main(){double p,g,c=1,i,r,t;std::cin>>p>>g;for(;c<101;c++){r=c;for(i=0;i<7;i++){t=(int)(r*(1-(p/100))+g);if(t>=r){r=-1;break;}r=t;}if(r!=-1)break;}r!=-1?std::cout<<c:std::cout<<0;}

APL, 36

x y←⎕⋄101|1⍳⍨y<x×{y+⍵-⌈⍵×x}⍣6⍳x÷←100

Explicación

Tenga en cuenta que hay un "umbral de pastel". Para la tasa de impuestos xy el reembolso y, necesitará estrictamente más que y÷xpasteles para pasar el próximo puente.

x y←⎕tomar entrada y asignar a x(impuesto) y y(retorno)
⍳x÷←100dividir xpor 100, y luego generar una matriz de 1 a 100

{y+⍵-⌈⍵×x}⍣6llame a la función "pasar puente" 6 veces:
⌈⍵×xla cantidad de pasteles que tiene, la tasa de impuestos multiplicada por el redondeo (la cantidad que paga)
⍵-Reste de la cantidad de pasteles que tiene
y+Agregue el reembolso

Luego obtienes una matriz de 100 elementos que muestra la cantidad de pasteles que te quedan después de cruzar 6 puentes si comienzas con 1 ~ 100 pasteles. Para ver si puede cruzar el último puente, verifique si está por encima del umbral y÷x. Alternativamente:
x×multiplique la matriz por x
y<verificación si es mayor quey

Finalmente,
1⍳⍨encuentre el índice de la primera aparición de 1(verdadero), devuelve 101si no se encuentra
101|mod 101

C 128

Bastante similar a la otra solución C pero creo que es inevitable. El truco principal es salir del bucle interno con diferentes valores dependiendo de si se completa o no. Esto me permite usar?: Cuando no podía si usaba break;

t,r,j,k,l,p;main(i){for(scanf("%d%d",&t,&r),i=101;k=--i;){for(j=8;--j>0;)(p=r+k*(100-t)/100)<k?k=p:j=0;j?0:l=i;}printf("%d",l);} 

Sin golf

int t,r,j,k,l,p;
main(int i)
{
    for(scanf("%d%d",&t,&r),i=101;k=--i;)
    {
        for(j=8;--j>0;)
        {
            if((p=r+k*(100-t)/100)<k)
                k=p;
            else
                j=0;
        }
        j?0:l=i;
    }
    printf("%d",l);
}