Qminers provozují obchodní algoritmy na mnoha světových burzách. Chtěli by všechny svoje kolokace spojit pomocí jedné optické sítě. Protože ale nikomu nesmí prozradit, ve kterých městech obchodují, rozhodli se spojit rovnou desetitisíce různých světových měst.
Telekomunikační společnost má ve všech městech spojovací uzly a je ochotna umístit libovolné množství dalších spojovacích uzlů na libovolné jiné místo na světě. Bohužel si však nechá platit za každý kilometr optického kabelu a za každý nový uzel, který musí umístit.
Jak má vypadat výsledná síť, aby byla co nejlevnější?
Vítězem soutěže se stává řešitel, který představí řešení s nejnižší cenou.
Vstup
Vstup je k dispozici ve formě textového souboru. V něm jsou města zadána jako souřadnice na rovinné 2D mřížce. Na prvním řádku vstupního souboru jsou celá čísla N a S, kde
- N udává počet měst a
- S udává cenu za přidání jednoho uzlu.
Na následujících N řádcích jsou na každém dvě celá čísla z intervalu [0, 230 – 1] určující souřadnice jednotlivých měst.
Výstup
Na prvním řádku výstupu očekáváme celá čísla V a E, kde
- V je počet uzlů mimo města, které používáte, a
- E počet propojení mezi uzly.
Na následujících V řádcích očekáváme souřadnice přidaných uzlů specifikovány dvěma celými čísly z intervalu [0, 230 – 1].
Na následujících E řádcích očekáváme seznam jednotlivých spojení mezi uzly či městy. Ten je specifikován vždy dvěma celými čísly z intervalu [1, N + V], kde čísla z intervalu [1, N] odpovídají městům na vstupu v pořadí ve kterém byly vypsány ve vstupním souboru a čísla z intervalu [N+1, N+V] odpovídají vašim přidaným uzlům v pořadí ve kterém byly vyenumerovány ve výstupním souboru. Celý řádek znamená, že příslušné dva body mají být propojené kabelem.
Výsledná cena je součet eukleidovských vzdáleností všech dvojic propojených kabelem, plus S*V za přidání nových uzlů. V případě, že nejsou všechna města propojena, je cena nekonečno.
Vstup tedy může vypadat například takto:
| 4 | 5 |
| 0 | 0 |
| 0 | 100 |
| 100 | 0 |
| 100 | 100 |
Tomuto vstupu odpovídá například následující výstup:
| 2 | 5 |
| 29 | 50 |
| 71 | 50 |
| 1 | 5 |
| 2 | 5 |
| 3 | 6 |
| 4 | 6 |
| 5 | 6 |
To odpovídá následující ilustraci, kde A, B, C a D jsou pozice měst, a S1, S2 jsou přidané uzly.
Pokud je cena uzlu S=5, je cena tohoto řešení přibližně 283.2
Kdyby byla cena uzlu S=10, byla by cena řešení 293.2 – v takovém případě by bylo lepší použít řešení
| 1 | 4 |
| 50 | 50 |
| 1 | 5 |
| 2 | 5 |
| 3 | 5 |
| 4 | 5 |
s celkovou cenou 292.8. Kdyby byla cena uzlu dokonce S=20, bylo by optimální řešení
| 0 | 3 |
| 1 | 2 |
| 1 | 3 |
| 2 | 4 |
s cenou 300.
Vaše řešení vložte do soutěžního formuláře.
Toto zadání si můžete stáhnout ve formátu pdf .