Inspirowany /puzzling//q/626

W swoich przygodach dochodzisz do serii 7 mostów, które musisz pokonać. Pod każdym mostem mieszka troll. Aby przejść przez most, musisz najpierw dać trollowi liczbę ciastek jako procent liczby ciast, które nosisz. Ponieważ są to miłe trolle, oddadzą ci pewną liczbę ciastek.

Na początku każdego dnia lokalny król trolli ustala procent podatku od tortów, który każdy podróżny musi zapłacić, oraz zwrot kosztu trolli - liczbę ciast, które każdy troll musi zwrócić podróżnym.

Twoim zadaniem jest obliczenie minimalnej liczby ciastek potrzebnych do przejścia wszystkich 7 mostów trolli dla danych warunków w danym dniu.

Założyć:

1. Dwa parametry wejściowe: procent podatku od ciasta (liczba całkowita od 0 do 100) i zwrot ciasta za troll.
2. Nikt, nawet trolle, nie chce ciasta częściowo zjedzonego przez innego trolla. Jeśli zostanie ci ułamek ciasta, troll go dostanie.
3. Jeśli troll zaakceptuje podatek od ciast, ale potem będzie musiał oddać ci wszystkie ciastka (pozostanie z tymi samymi lub mniejszymi ciastami niż wcześniej), rozzłości się i zje ciebie oraz twoje ciastka.
4. Każdy troll musi zachować co najmniej jedno pełne ciasto.
5. Możesz przewozić maksymalnie 100 ciastek.
6. Musisz zakończyć dzień, w którym aktualnie się znajdujesz lub po drugiej stronie wszystkich 7 mostów.

Wyzwanie:

Napisz kompletny program, który wyświetli minimalną liczbę ciastek do przejechania w bieżącym dniu lub zero, jeśli dzisiaj nie będzie można bezpiecznie podróżować - poczekasz, aby zobaczyć, jakie będą liczby jutro.

Dane wejściowe należy przekazywać jako stdin, argumenty wiersza poleceń lub dane wejściowe pliku.

Najkrótszy kod (liczba bajtów) wygrywa.

Przykład:

25% podatku od ciast, zwrot 2 ciastek trolli.

zacznij od 19 ciast
przed trollem 1: (19 * 0,75) = 14,25
po trollem 1: (14 + 2) = 16

przed trollem 2: (16 * 0,75) = 12
po trollem 2: (12 + 2) = 14

itp.

19 ciast -> 16 -> 14 -> 12 -> 11 -> 10 -> 9 -> 8
18 ciast -> 15 -> 13 -> 11 -> 10 -> 9 -> 8 -> 8 (reguła 3)

W przypadku 18 ciast ostatni troll nie zdoła zatrzymać ciastek. Dlatego minimalna liczba ciastek na 25% / 2 dni wynosi 19.

input: 25 2
output: 19

Przykład 2:

90% podatku od ciast, zwrot 1 ciasta na trolla

100 ciastek -> 11 -> 2 -> 1 (reguła 4)

Trzeci troll nie zdążył zatrzymać ciasta. Dlatego nie można podróżować w 90% / 1 dniu, nawet zaczynając od maksymalnej liczby ciastek.

input: 90 1
output: 0

Dane

Przygotuj szybki wykres wartości wejściowych i wyjściowych. Byłem zaskoczony, że nie było to „gładkie” (jak krzywa dzwonowa lub podobna); jest kilka zauważalnych wysp.

Dane dla zainteresowanych. Kolumny są podzielone na 5% przedziały, rzędy to jednostki 1 odstępu zwrotu ciasta (excel obrócił obraz). Widać, że zwrot nie może przekroczyć 28 ciast.

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 bajtów

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

Wejście przez ARGV.

Istnieje internetowy tłumacz, ale niestety nie obsługuje on argumentów wiersza poleceń. Do testowania możesz naśladować go ze STDIN za pomocą tej wersji:

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

Objaśnienie wersji opartej na 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.";

Zawartość stosu jest automatycznie drukowana na końcu programu.

CJam, 44 40 38 37 35 bajtów

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

Lub używając argumentów wiersza poleceń i {}#lewy, 33 bajty :

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

Nie umieszczenie tego jako mojego głównego {}#podejścia jest inspirowane odpowiedzią Martina.

Przykładowy przebieg:

Wejście:

25 2

Wynik:

19

Inne:

Wejście:

15 14

Wynik:

100

Jak to działa

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";

Wypróbuj online tutaj

APL (39)

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

Wyjaśnienie:

• T R←⎕: odczytaj dwie cyfry z klawiatury i zapisz je w T(podatek) i R(zwrot).
• Z←⍳M←100: Zapisać numer 100w M, i wszystkie numery od 1do 100w Z.
• {... }⍣7¨: dla każdego elementu Zuruchom 7 razy następującą funkcję:
  • R+⌊1-T÷M: obliczyć, ile ciastek trzeba zapłacić,
  • ⍵(⊢×>): pomnóż tę kwotę przez 1, jeśli troll skończy z większą ilością ciasta, niż zaczął, lub przez 0, jeśli nie.
• ⊃Z/⍨: dla każdego elementu Zpowtórz go według numeru podanego przez tę funkcję. (Tak więc wszystkie liczby, dla których zwrócono funkcję, 0znikają.) Następnie wybierz pierwszy element z tej listy. Jeśli lista okazała się pusta, daje to 0.

C, 83 bajty

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;
}

Jeśli to działa, działa dla wszystkich możliwych ciastek startowych, nie tylko od 1 do 100.

EDYCJA: Działa. Gra w golfa:

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;}

Z limitem „maksymalnie 100 ciastek”:

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 bajtów.

CJam, 36 bajtów

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

C ++ - 202 znaków

Jak zwykle mój C ++ zrobił najgorsze:

#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

Wyjaśnienie

Zauważ, że istnieje „próg ciasta”. Aby uzyskać stawkę podatku xi zwrot pieniędzy y, będziesz potrzebować czegoś więcej niż y÷xciasta, aby przejść przez kolejny most.

x y←⎕weź dane wejściowe i przypisz do x(podatek) i y(zwrot)
⍳x÷←100podziel xprzez 100, a następnie wygeneruj tablicę od 1 do 100

{y+⍵-⌈⍵×x}⍣6zadzwoń do funkcji „most przejściowy” 6 razy:
⌈⍵×xliczba posiadanych ciastek, stawka podatku, zaokrąglanie w górę (
⍵-płacona kwota) Odejmij od liczby posiadanych ciastek
y+Dodaj zwrot

Następnie otrzymasz tablicę zawierającą 100 elementów, pokazującą liczbę ciastek, które pozostały Ci po przejściu 6 mostów, jeśli zaczniesz od 1 ~ 100 ciastek. Aby sprawdzić, czy możesz przejść przez ostatni most, sprawdź, czy przekroczyłeś próg y÷x. Alternatywnie:
x×pomnóż tablicę przezx
y< sprawdzenie, czy jest większa niży

Na koniec
1⍳⍨znajdź indeks pierwszego wystąpienia 1(true), zwraca 101jeśli nie znaleziono
101|mod 101

C 128

Całkiem podobne do innych rozwiązań C, ale myślę, że to nieuniknione. Główną sztuczką jest wyrwanie się z wewnętrznej pętli z różnymi wartościami w zależności od tego, czy dojdzie do jej zakończenia, czy nie. Pozwala mi to używać?: Kiedy nie mogłem, jeśli użyłem 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);} 

Nie golfił

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);
}