Inspiriert von /puzzling//q/626

In deinen Abenteuern kommst du an eine Reihe von 7 Brücken, die du überqueren musst. Unter jeder Brücke lebt ein Troll. Um die Brücke zu überqueren, müssen Sie dem Troll zuerst eine Anzahl Kuchen als Prozentsatz der Anzahl Kuchen geben, die Sie tragen. Da es sich um nette Trolle handelt, geben sie Ihnen eine bestimmte Anzahl Kuchen zurück.

Zu Beginn eines jeden Tages legt der örtliche Trollkönig die prozentuale Kuchensteuer fest, die jeder Reisende zahlen muss, und die Rückerstattung des Trollkuchens - die Anzahl der Kuchen, die jeder Troll den Reisenden zurückgeben muss.

Ihre Aufgabe ist es, die minimale Anzahl von Kuchen zu berechnen, die erforderlich sind, um alle 7 Trollbrücken für die gegebenen Bedingungen an diesem Tag zu passieren.

Annehmen:

1. Zwei Eingabeparameter: Prozentuale Kuchensteuer (Ganzzahl von 0 bis 100) und Trollkuchenrückerstattung.
2. Niemand, nicht einmal Trolle, möchte einen Kuchen, der teilweise von einem anderen Troll gefressen wird. Wenn du einen Bruchteil eines Kuchens übrig hast, bekommt der Troll ihn.
3. Wenn ein Troll eine Kuchensteuer akzeptiert, Ihnen dann aber alle Kuchen zurückgeben muss (es verbleiben die gleichen oder weniger Kuchen als zuvor), wird er wütend und frisst Sie und Ihre Kuchen.
4. Jeder Troll muss mindestens einen vollständigen Kuchen behalten.
5. Sie können maximal 100 Kuchen mitnehmen.
6. Sie müssen den Tag beenden, an dem Sie sich gerade befinden oder auf der anderen Seite aller 7 Brücken.

Herausforderung:

Schreiben Sie ein komplettes Programm, um die Mindestanzahl an Kuchen für den aktuellen Tag oder Null auszugeben, wenn es heute nicht möglich ist, sicher zu reisen. Sie werden warten, bis die Zahlen morgen vorliegen.

Die Eingabe sollte als stdin, Befehlszeilenargumente oder Dateieingabe übergeben werden.

Der kürzeste Code (Byteanzahl) gewinnt.

Beispiel:

25% Kuchensteuer, 2 Trollkuchen Rückerstattung.

Beginnen Sie mit 19 Kuchen
vor Troll 1: (19 * 0,75) = 14,25
nach Troll 1: (14 + 2) = 16

vor Troll 2: (16 * 0,75) = 12
nach Troll 2: (12 + 2) = 14

etc.

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

Für 18 Kuchen würde der letzte Troll keine Kuchen behalten. Daher beträgt die Mindestanzahl an Kuchen pro 25% / 2 Tag 19.

input: 25 2
output: 19

Beispiel 2:

90% Kuchensteuer, 1 Trollkuchenrückerstattung

100 Kuchen -> 11 -> 2 -> 1 (Regel 4)

Der dritte Troll durfte keinen Kuchen behalten. Daher ist es nicht möglich, an einem 90% / 1 Tag zu reisen, auch wenn die maximale Anzahl an Kuchen erreicht ist.

input: 90 1
output: 0

Daten

Stellen Sie ein kurzes Diagramm der Eingabe- und Ausgabewerte zusammen. Ich war überrascht, dass dies nicht "glatt" war (wie eine Glockenkurve oder ähnliches); Es gibt mehrere auffällige Inseln.

Daten für Interessenten. Die Spalten sind in 5% -Intervalle unterteilt, die Zeilen sind Einheiten von 1-Kuchen-Erstattungsintervallen (excel hat das Bild gedreht). Sie können sehen, dass eine Rückerstattung von mehr als 28 Kuchen nicht möglich ist.

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/+@;}*>}#)

Eingabe über ARGV.

Es gibt einen Online-Interpreter, der jedoch leider keine Befehlszeilenargumente unterstützt. Zum Testen können Sie es mit dieser Version von STDIN nachahmen:

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

Erklärung der ARGV-basierten Version:

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

Der Inhalt des Stapels wird am Ende des Programms automatisch ausgedruckt.

CJam, 44 40 38 37 35 Bytes

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

Oder bei Verwendung von Befehlszeilenargumenten und {}#Tricks 33 Byte :

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

{}#Die Antwort von Martin inspiriert mich, diesen Ansatz nicht zu meinem Hauptansatz zu machen .

Beispiellauf:

Eingang:

25 2

Ausgabe:

19

Ein weiterer:

Eingang:

15 14

Ausgabe:

100

Wie es funktioniert

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

Probieren Sie es hier online aus

APL (39)

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

Erläuterung:

• T R←⎕: Lesen Sie zwei Zahlen von der Tastatur und speichern Sie sie in T(Steuer) und R(Rückgabe).
• Z←⍳M←100: Speichern Sie die Nummer 100in Mund alle Nummern von 1bis 100in Z.
• {... }⍣7¨: ZFühren Sie für jedes Element in die folgende Funktion siebenmal aus:
  • R+⌊1-T÷M: Berechnen Sie, wie viele Kuchen bezahlt werden müssen,
  • ⍵(⊢×>): Multipliziere diesen Betrag mit 1, wenn der Troll mehr Kuchen hat als er begonnen hat, oder mit 0, wenn nicht.
• ⊃Z/⍨: Für jedes Element in Zreplizieren Sie es mit der Zahl, die diese Funktion angegeben hat. (Alle Nummern, für die die Funktion zurückgegeben wurde, 0verschwinden.) Wählen Sie dann den ersten Eintrag aus dieser Liste aus. Wenn die Liste leer ist, gibt dies 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;
}

Wenn es funktioniert, funktioniert es für alle möglichen Startcakes, nicht nur für 1 bis 100.

EDIT: Es funktioniert. Golf gespielt:

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

Mit der Höchstgrenze von 100 Kuchen:

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 Zeichen

Wie immer hat mein C ++ das Schlimmste getan:

#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

Erläuterung

Beachten Sie, dass es eine "Kuchenschwelle" gibt. Für den Steuersatz xund die Rückerstattung ybenötigen Sie unbedingt mehr als y÷xKuchen, um die nächste Brücke zu passieren.

x y←⎕Nehmen Sie die Eingabe und weisen Sie x(Steuer-) und y(Rückgabe-)
⍳x÷←100Division xdurch 100 zu, und generieren Sie dann ein Array von 1 bis 100

{y+⍵-⌈⍵×x}⍣6rufen Sie die „Pass - Brücke“ Funktion 6 mal:
⌈⍵×xDie Anzahl der Kuchen Sie, mal Steuersatz, aufrunden (der Betrag , den Sie bezahlen) haben
⍵-subtrahieren aus der Anzahl der Kuchen Sie haben
y+Fügen Sie die Rückerstattung

Dann erhalten Sie ein 100-Elemente-Array mit der Anzahl der verbleibenden Kuchen, nachdem Sie 6 Brücken überquert haben, wenn Sie mit 1 bis 100 Kuchen beginnen. Um festzustellen, ob Sie die letzte Brücke überqueren können, prüfen Sie, ob Sie über der Schwelle liegeny÷x . Alternativ:
x×Multiplizieren Sie das Array, indem Sie x
y<prüfen, ob größer alsy

Schließlich
1⍳⍨finden Sie den Index des ersten Auftretens von 1(true), gibt zurück, 101wenn nicht gefunden
101| mod 101

C 128

Ziemlich ähnlich wie die andere C-Lösung, aber ich denke, das ist unvermeidlich. Der Haupttrick besteht darin, mit unterschiedlichen Werten aus der inneren Schleife auszubrechen, je nachdem, ob sie abgeschlossen ist oder nicht. Dies erlaubt mir? Zu benutzen: wenn ich nicht könnte, wenn ich break benutzt hätte;

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

Ungolfed

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