Runda 8 [Basic] - Nurek
24.01.2011 - Damian Rusak
Zadanie Tygodnia Runda 8; kategoria Basic Limit czasowy: 1s; Limit pamięciowy: 16MB NurekNa dnie Oceanu Kratowego odnaleziono wrak okrętu zatopionego przed wiekami w czasie wojen morskich. Ekspedycja nurków wyrusza, aby wśród zdradliwych piasków szukać dawno zapomnianych skarbów. Nurkom udało się sporządzić mapę dna morskiego za pomocą radarów i zamierzają wypuścić linę w głebiny oceanu, aby za jej pomocą sprawnie dostać się na dno. Oznaczyli na mapie kilka miejsc, w których chcą poszukiwać skarbu. Ponieważ lokalne wody są bardzo zdradliwe, postanowili, że na miejsce spuszczenia liny wybiorą pozycję, z której w sumie najszybciej uda im się odwiedzić wszystkie lokacje oznaczone na mapie. Każda pojedyńcza wyprawa w poszukiwaniu skarbu wymaga wielu przygotowań i koncentracji - badanie dna nie jest prostą sprawą. Nurkowie ustalili więc, że za kryterium oceny pozycji opuszczenia liny wybiorą sumę jego odległości do wszystkich lokacji oznaczonych na mapie. Jeśli współrzędne lokacji to a miejsce opuszczenia liny to to odległość między nimi określimy przez (gdzie to wartość bezwzględna z liczby ). Mając daną mapę dna morskiego, odpowiedz na pytanie o najlepsze miejsce na opuszczenie liny. Wejście: Pierwsza linia wejścia zawiera dwie liczby całkowite i () oznaczające wysokość i szerokość fragmentu dna przedstawionego na mapie. W kolejnych liniach (dla ) znajdują się ciągi znaków , , ..., . Jeśli to znak '#' to pole o współrzędnych jest puste, jeśli zaś to znak 'X' to pole to jest możliwą lokacją skarbu. Możesz założyć, że na mapie pojawi się chociaż jeden znak 'X'. Wyjście: Wyjście powinno zawierać dwie liczby całkowite - współrzędne pola, na które najlepiej opuścić linę. Jeśli takich pól jest kilka, wypisz to o najmniejszej współrzędnej - jeśli takich wciąż jest więcej niż jedno, spośród nich wybierz pole o najmniejszej współrzędnej . Przykład: Wejście: 5 6 ###### #X##X# ###### ###X## ###### Wyjście: 2 4 Wyjaśnienie: Skarby znajdują się na pozycjach , oraz . Suma odległości tych lokacji od to 2+1+2 = 5 i jest to minimalna suma możliwa do uzyskania.
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
(3 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com