Mount and Blade je názov počítačovej hry a súčasne 9. úlohy do našej súťaže, ktorú nám zaslal doktorand na matematickom ústave SAV Branislav Novotný. (To by človek nepovedal, čím všetkým sa Braňo ešte zaoberá okrem matematickej topológie a vyparovania čiernych dier :-)Táto úloha je síce pomerne jednoduchá, ale pekné na nej je to, že je to úplne reálny problém, ktorý možno trápi viacerých hráčov hry Mount&Blade. Nie som si však vedomý toho, že by ju už niekto v nasledovnom znení formuloval.
Pri hraní M&B hráte za hrdinu, ktorý môže mať v partii okrem bežných vojakov aj tzv. hrdinov, ktorí sú mimo iného nesmrteľní ( hrdinovia predsa neumierajú :-), teda sa ich oplatí mať v partii čo najviac. Ich základným problémom však je, že majú medzi sebou spory a dokážu sa tak pohádať, že opustia partiu. Nasleduje tabuľka mien (ženy majú hviezdičku, lebo z mena je to ťažko poznať) a zoznam kto koho má, či nemá rád.
Ľahko si všimneme, že všetky vzťahy sú vzájomné. Definujme konflikt ako dvojicu, čo sa nemá rada a priateľstvo ako dvojicu čo sa má rada. Povedzme, že parta je maximálna, ak za daných podmienok má maximálny počet členov a medzi partiami s max. počtom členov má max. počet priateľstiev. Povedzme, že partia je bezkonfliktná, ak neobsahuje konflikt. Nech je udržateľná ak ľubovoľný člen je účastníkom najviac takého počtu konfliktov ako priateľstiev.
Treba nájsť všetky:
a) maximálne bezkonfliktné partie,
b) maximálne udržateľné partie,
c) maximálne udržateľné partie obsahujúce všetky ženy.
5 komentárov:
hmm, po styroch dnoch to este nikoho neoslovilo. bud sa zda vsetkym prilis lahka, alebo pracna. lenze zase az taka pracna nieje, po tom co sa nakesli graf vztahov, tak odpoved na a) sa da najst do 30s. c) tak do 60-90s b) mozno par minut
a ak sa vam to nechce kreslit, tak si to mozte pozriet na
http://strategywiki.org/wiki/Mount%26Blade/Companion_Comparison
Braňo: Tvoja úloha je celkom príjemná, ale celkovo je posledných pár dní akési obdobie komentárových suchôt a to aj na blogu Peťa Richtárika, aj na misofovom a vlastne aj na Rasťovom a Paľovom, ak by som nekomentoval ja :)
Študenti asi finišujú so skúškami a Tí čo už skúšky majú hotové sú niekde na lyžovačke. No, nevadí. Asi sa to viac rozbehne o dva týždne.
to ma nenapadlo, ja mam praveze z toho isteho dovodu viac casu :)
Vyriešené ? :)
Zverejnenie komentára