Egy börtönben bizonyos rabok össze vannak láncolva, hogyan nehezebb legyen megszökniük. Egy lázadó csoport mégis úgy döntött, hogy megkísérlik a szökést. A terv egyik fontos eleme, hogy valamikor meg kell nyomniuk (pontosan egy időben) két egymástól távol lévő gombot. A csoportnak el kell döntenie, hogy melyik két rab a leginkább alkalmas erre a feladatra. A rabokat összekötő láncok hosszának ismeretében adjuk meg a maximális távolságot, amennyire (valamelyik) két rab el tud távolodni egymástól. Ha nem korlátos a távolság, akkor -1 írandó ki. FeladatÍrjunk programot, ami megadja a maximális elérhető távolságot, amit két megfelelően megválasztott rabbal elérhető.
BemenetA bemenet N darab karakterláncban kódolja a rabok közötti láncok hosszát. A j. sor i. karaktere az i. és j. rab közötti lánc hosszát adja meg:
Korlátok
KimenetEgyetlen szám a maximális elérhető távolság. Ha nem korlátos a táv, akkor -1-et kell kiírni.
Példák
CímkékA feladat forrása: TopCoder: Escaping Jail, http://community.topcoder.com/stat?c=problem_statement&pm=6222&rd=9822
Algoritmusok: legrövidebb út az összes pontpárra, Folyd-Warshall
megoldás |
Programozás > Feladatok >