Lövöldözős játék. Használható hozzá matematika?

Ez egy kicsit bonyolultabb probléma szerintem, mint ahogy egy korábbi válaszadó lefesti, de mindenképpen érdekes.

Egy megjegyzés a sebzés-életerő kapcsolatáról: mivel a kettő nem függ egymástól, ezért elegendő azt figyelni, hogy egy adott ellenfelet hányszor kell eltalálni, hogy meghaljon. Így az életerő tetszőleges egész szám, a sebzést pedig ki lehet iktatni a feladatból.

A feladat egy átfogalmazása:

A továbbiakban általánosságban tegyük fel, hogy van n darab ellenfél, D[1],..,D[n] sebzéssel és L[1],..,L[n] élettel.(damage-life) A kérdés, hogy egy adott ellenfél a játék folyamán mennyit sebez rajtunk, ha ez megvan, summázva mindegyik ellenfélre megkapjuk, hogy a játék során mennyit sebeztek rajtunk összesen.

Ha egy ellenfél meghal a következő körben nem fog már sebezni, tehát a sebzése a játék során jellemezhető, egy a[k]=(1,1,1,1,..,1,0,...) sorozattal, ahol az utolsó egyes azon a helyen áll, hol az adott ellenfél meghalt. A rajtunk esett össz-sebzést a k-adik játékos által jelöljük mondjuk C[k]-val.

Ekkor C[k]=D[k]*max{i}{a[k]=1}

Legyen P L[1] db 1-es, L[2] db 2-es, stb...L[n] db n-es ismétléses permutációinak halmaza. Ekkor ha p egy ilyen permutáció, akkor ebből a fent bevezetett a[k] sorozatok megadhatóak úgy, hogy a[k] első l db tagja 1, a többi 0, ahol l=max{i:p(i)=k}, vagyis az utolsó alkalom, amikor az adott ellenfelet el kell találnom ahhoz, hogy meghaljon.

Így C[k]=max{j:p(j)=k}*D[k] és

C=sum{k=1,..,n}}{C[k]}

A feladat tehát az, hogy melyik az a p permutáció, melyre

a sum{k=1,..,n}{max{j:p(j)=k}*D[k]} minimális

Korábbi válaszoló vagyok... A te formalizmusoddal D[i]/L[i] szerint kell csökkenő sorrendbe rakni az ellenfeleket.

Vegyünk egy tetszőleges sorrendet, benne két olyan ellenfelet, akiket egymás után nyírsz ki. Az elsőnek D1 és L1, a másodiknak D2 és L2 az értékei. Kérdés: érdemes-e őket megcserélni az adott permutációban? Mindkettőt L1+L2 idő alatt nyírod ki, sorrendtől függetlenül, és ennyi kör körönként D1+D2 sebzést szenvedsz el, amiből levonódik az, amit az először kinyírt ellenfél már nem lő, mert idő előtt meghal. Ha ez elsőt (D1,L1) nyírod ki először, akkor a hátramaradó L2 időben mentesülsz körönként D1 sebzéstől. Ha fordítva, akkor L1 kör alatt szabadulsz meg körönként D2 sebzéstől. Melyik a több? Ha (L1,D1)-nek jobb az aránya, akkor D1/L1>D2/L2, ebből D1*L2>D2*L1. Vagyis, ha a nagyobb D/L arányút nyírod ki először, akkor több sebzéstől mentesülsz.

Tehát ha van egy permutációd, akkor azt folyamatosan javítgatod úgy, hogy a szomszédosakat megcseréled, hogy a nagyobb D/L arány kerüljön előre. Ezzel folyamatosan jobb megoldásokat kapsz, végül csökkenő sorrendben lesznek az ellenfelek. Tehát ez a legjobb megoldás. Ha két ellenfél D/L aránya megegyezik, akkor mindegy, milyen sorrendben nyírod ki őket, és szabadon fel is cserélhetők.

A sorrend tehát: ABKIGHFCDJEL.

Ajánlom figyelmedbe, hogy nem feltétlen ez a megoldás, ha az ellenfelek idő közben eltűnhetnek szem elöl, vagy leállhatnak a lövéssel.