Prémia 1 - Vzorové riešenie

Kategórie:
5
6
7
8
9

Zadanie

Na pláne mesta môžeme vidieť ulice znázornené rovnými čiarami. Na každom mieste, kde sa stretávajú viaceré ulice, je zastávka, teda každá ulica spája práve dve zastávky. V meste potrebujú navrhnúť linky MHD podľa takýchto pravidiel:
  • Každá linka je cyklus, teda začína na rovnakej zastávke ako končí
  • Linka neprechádza viac krát jednou zastávkou
  • Každá linka má najmenej 10 zastávok
  • Po každej ulici musí prechádzať aspoň jedna linka
Pokúste sa podľa týchto pravidiel navrhnúť linky, a to tak aby boli čo najefektívnejšie, teda aby bol súčet dĺžok všetkých liniek čo najmenší. Za dĺžku linky sa považuje počet ulíc, ktorými prechádza.

Vzorové riešenie

Opravovali: Danko, Johnny, Prutky, ViktorB
Riešenie

Najmenší súčet dĺžok liniek, ktorý sa vám podarilo dosiahnuť bol 96. Na obrázku je jedno z takýchto riešení. (Každá farba predstavuje jednu linku.)

Bodovanie:
  • Súčet 96 - 6 bodov.
  • Súčet 97 až 103 - 5 bodov.
  • Súčet 104 až 108 - 4 body.
  • Súčet 109 až 114 - 3 body.
  • Súčet 115 až 119 - 2 body.
  • Súčet 120 a viac - 1 bod.