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:
- Zwei Eingabeparameter: Prozentuale Kuchensteuer (Ganzzahl von 0 bis 100) und Trollkuchenrückerstattung.
- 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.
- 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.
- Jeder Troll muss mindestens einen vollständigen Kuchen behalten.
- Sie können maximal 100 Kuchen mitnehmen.
- 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
25 2
11-Kuchen-Box geben Sie dem Troll 2,75 Kuchen und erhalten 2 zurück, damit der Troll 0,75 (+ 25) behält und Sie überleben. Im90 1
2-Kuchen-Fall geben Sie dem Troll 1,8 und erhalten 1 zurück, sodass der Troll 0,8 (+2) behält, aber Sie sterben.