Interessante Aufgabe aus einem Programmierwettbewerb (Lasthit Gold maximieren)

[Cinematic]

Jemand eine Idee wie man das lösen könnte? Falls sogar jemand sogar eine Lösung programmieren möchte, vorzugsweise in Java bitte wenn es geht. Und bevor jemand meckert, natürlich läuft der Wettbewerb nicht mehr.
Alle Möglichkeiten durchprobieren wird wohl nicht gehen, da es ja bis zu 50 Henchmengibt pro Case. Und das wächst exponentiell, insbesondere wenn die Henchmen viel Leben haben, und Lea und der Turm wenig Schaden.

 

[bull123]

Klingt für mich nach einer Art des Traveling Salesman Problem (TSP) bei dem der Weg den der Turm nimmt von Leas Handlungen abhängt und Lea die Nodes (Minions) abläuft die am meisten Leben haben und Geld droppen.

Kannst mal nach Varianten des TSP suchen. Vielleicht findest du etwas passendes.

 

[Miuwa]

Ich habe noch keine Lösung, aber ein paar Beobachtungen, die Hilfreich sein sollten

Anmerkung: Mit x\y bezeichne ich immer das aufgerundete Ergebnis von x/y.

1. Jeder Henchman wird entweder von Lea oder dem Turm getötet und da sich der Turm 100% deterministisch verhält weiß Lea im voraus was passieren wird.
2. Lea hat nichts davon mehr als die Minimale Anzahl an nötigen Schüssen auf einen Henchman abzugeben. Damit gilt für s_l_i (Schüsse Lea auf Henchman i) und s_t_i (Schüsse Turm auf Henchman i)
   • Wenn der Turm den letzten Hit macht (lh_i == 0)
     

     s_l_i = 0;
     s_t_i = h_i \ k;

   • Wenn Lea den letzten Hit macht (lh_i == 1)
     

     tmp=h_i % k
     if (t==0) 
       s_l_i  = k \ m 
       s_t_i = (h_i / k) -1;
     else 
       s_l_i = t \ m
       s_t_i = h_i / k;

Aus dieser Beobachtung und der Folge lh_1, lh_2, lh_3 ..., lh_n,ergibt sich dann auch für jeden Henchman eine Deadline (d.h. die Runde in der er stirbt), bis zu der Lea ihre Schüsse abgefeuert haben muss. Damit lässt sich die Frage wann Lea auf welchen Henchman schießen muss als Scheduling Problem formulieren, für das es ebenfalls eine geschlossene, optimale Lösung gibt (aber da hab ich noch nicht alle Spezialfälle durchdacht).

Damit haben wir ein max 50-Dimensionales integer-lineares Optimierungsproblem mit der zu maximierenden Zielfunktion

Sum_{i=1}^n {g_i*lh_i}

Das sollte sich in den meisten Fällen intelligent bruteforcen lassen: erst mal davon ausgehen, dass alle Henchmen von Lea getötet werden können und dann sukzessive einzelne Henchmen (z.B. in der Reihenfolge ihres Wertes) weglassen.

 

[cx01]

Die Aufgabe scheint identisch zu folgender zu sein: https://code.google.com/codejam/contest/3024486/dashboard#s=p1
Hier gibt es einige Lösungen dazu: https://www.go-hero.net/jam/14/problems/5/2