High School Programming League Problems Archive

Po ostatniej kradzieży, w Muzeum Historii Naturalnej został zainstalowany najnowocześniejszy system antywłamaniowy. Wiele osób zgłosiło się do testów tego systemu, ale jak na razie nikomu nie udało się go pokonać. Teraz dyrekcja muzeum chce zidentyfikować najsłabsze jego punkty. Poproszono Cię o pomoc. Napisz program, który znajdzie drogę, po której z najmniejszym prawdopodobieństwem wykrycia będzie można dostać się do najcenniejszego eksponatu muzealnego.

W tym celu dostałeś mapę pomieszczenia:

• Podłoga pomieszczenia składa się z kwadratowych kafli.
• W pomieszczeniu znajdują się też inne eksponaty – są to miejsca, na które nie można stanąć.
• Możesz poruszać się wyłącznie w czterech kierunkach: góra, dół, lewo, prawo (U, D, L, R),
• Początek drogi znajduje się w miejscu wylotu wentylacyjnego, a koniec – w miejscu najcenniejszego eksponatu.
• W pomieszczeniu zainstalowane są detektory ciepła, które w miejscu gdzie się znajdują mają 100% skuteczności wykrycia intruza. Im dalej od detektora tym skuteczność maleje. Rozkład skuteczności jest liniowy, z dokładnością do części całkowitej procentów.
• Jeśli na jednym polu występują dwie różne skuteczności wykrycia, wyznaczone przez różne czujniki to przyjmujemy, że łączna prawdopodobieństow wynosi max(s1,s2)
• w jednym miejscu może znajdować się i czujnik i eksponat.

Wejście

Opis wejścia jest prawie taki sam jak w zadaniu Mowing Optimization. Najpierw dany jest punkt początkowy (x1, y1) – potencjalny złodziej znajduje się na polu (x1, y1) (x1+1, y1) (x1+1, y1+1) (x1, y1+1) oraz punkt końcowy (x2, y2).

Następnie dany jest obrys zewnętrzny pomieszczenia: Liczba całkowita k – liczba elementów obrysu (4 <= k <= 1000), a następnie punkt początkowy (a, b) oraz k wektorów [ai, bi] rozdzielonych przecinkami opisujących kolejne elementy obrysu zgodnie z kierunkiem ruchu wskazówkami zegara (dla każdego i, 1<= i <= k zachodzi 0 < a_i² +b_i² < 10⁶ oraz a_ib_i=0).

W dalszej kolejności dana jest liczba n – ilość innych eksponatów w pomieszczeniu i dalej n opisów każdego eksponatu w formacie j.w. (punkt startowy i obrys eksponatu). Na końcu dana jest liczba d - ilość detektorów temperatury i dalej opis d detektorów w formacie (x,y) r, gdzie r oznacza zasięg detektora. Pozycja wyznaczona w ten sam sposób jak punkt początkowy i końcowy - czujnik znajduje się na środku kafelki.

Można założyć, że obrys jest łamaną zamkniętą, elementy obrysu się nie przecinają, elementy niesąsiednie się nie stykają, łączna liczba kafli nie przekracza 10 000, a całe pomieszczenie mieści się w kwadracie o boku 1000 na 1000 pól.

Wyjście

Na wyjściu należy podać steps - liczbę kroków do wykonania oraz ciąg steps liter opisujących kolejne kroki poruszania się. Po wykonaniu wszystkich kroków złodziej powinien znaleźć się w miejscu, gdzie znajduje się jego cel – najcenniejszy eksponat. Jeśli złodziej wejdzie na jakiś inny eksponat lub czujnik temperatury, to rozwiązanie zostanie potraktowane, jako błędne. Podobnie, jeśli złodziej znajdzie się poza pomieszczeniem. W przypadku kilku dróg o takim samym prawdopodobieństwie, wystarczy podać dowolną z nich.

Opis przykładów

• biały - zwykłe kafelki
• czarny - eksponaty muzealne
• niebieski punkt - start
• fioletowy punkt – cel kradzieży
• czerwony - czujnik temperatury
• pomarańczowy, żółty - zakres działań czujnika

Przykład 1

Wejście:
(0, 0) (3, 3)
4
(0, 0), [0, 4], [4, 0], [0, -4], [-4, 0]
0
2
(0, 3) 2
(3, 0) 4


Wyjście:
6
URURUR

Przykład 2

Wejście:
(0, 0) (2, 5)
6
(0, 0), [0, 6], [6, 0], [0, -5], [-3, 0], [0,-1], [-3, 0]
2
6
(1, 3), [0, 2], [2, 0], [0, -1], [-1, 0], [0, -1], [-1, 0]
4
(4, 2), [0, 2], [1, 0], [0, -2], [-1, 0]
2
(0, 5) 2
(3, 2) 4


Wyjście:
13
URRRRRUUUULLL

Punktacja

Za rozwiązanie tego zadania otrzymasz 10 punktów.

After the last robbery in the Museum of Natural History, a modern anti-theft alarm has been installed. Many people have volunteered to test the system, but so far none of them have managed to break it. Now, the management of the museum has changed their approach and they would like someone to find the weakest points of the system. They have asked you for help. Write a program which will find a route to the main exhibit such that the probability of being detected is the smallest possible. To do so, you have been given a map of the exhibition room.

• The floor consists of square tiles.
• There are other exhibits in the room – the thief cannot step on them.
• The thief can only move in four directions: up, down, left, and right (U, D, L, R),
• The starting point of the route is fixed – it is the position of a ventilation hole. The endpoint is also fixed – it is the position of the main exhibit.
• There are temperature sensors which have 100% detection efficiency at their location. The further from the sensor the thief is, the smaller the efficiency of the sensor. Its distribution is linear, up to integer rounding of the percentage value.
• If a tile is within the range of more than one sensor, then the probability of being detected is the maximum of the detection efficiencies of the particular sensors.
• There can be both a sensor and an exhibit at the same location.

Input

The input description is almost the same as in the Mowing Optimization problem. First, we are given the starting point (x1, y1) - the potential thief is located at (x1, y1) (x1+1, y1) (x1+1, y1+1) (x1, y1+1), and the end point (x2, y2)

Next, there is given a description of the border of the room which consists of: an integer k – the number of line segments (4 <= k <= 1000), then there come the descriptions of successive segments of the boundary, expressed by the coordinates of one distinguished point (a, b), followed by k vectors[ a_i, b_i] separated by commas, describing the i -th segment of the border when traversed in the clockwise direction (for each i , 1<= i <= k we have 0 < a_i² +b_i² < 10⁶ and a_ib_i=0).

Then there is given n - the number of other exhibits in the room and then there are n descriptions of every exhibit (i.e., the coordinates of the starting point and of the outline, as above). Then there is given d – the number of sensors, followed by d descriptions of each sensor (x, y) r, where r is the range of detector. Position is determined in the same way as the starting and ending point - sensor is placed in the centre of a tile.

You can assume that each outline is a closed line, in which no two segments cross, nonadjacent elements do not touch themselves, the total number of tiles to be cut does not exceed 10000, and the whole room fits into a 1000x1000 square.

Output

First, output a single integer, describing the number of steps to be made, followed by a sequence of letters describing the successive steps. After all the steps have been completed, the thief should be located at the main exhibit point. If the thief will step onto another exhibit or a temperature sensor, your solution will be deemed incorrect. Likewise, your solution will be incorrect if at any time the theft will be located outside the room. If more than one possible route exists, you should output any one of them.

Example description

• white - normal tile
• black – other exhibits
• blue point - start
• violet point –target
• red – a temperature sensor
• orange, yellow –range of a sensor

Example 1

Input:
(0, 0) (3, 3)
4
(0, 0), [0, 4], [4, 0], [0, -4], [-4, 0]
0
2
(0, 3) 2
(3, 0) 4

Output:
6
URURUR

Example 2

Input:
(0, 0) (2, 5)
6
(0, 0), [0, 6], [6, 0], [0, -5], [-3, 0], [0,-1], [-3, 0]
2
6
(1, 3), [0, 2], [2, 0], [0, -1], [-1, 0], [0, -1], [-1, 0]
4
(4, 2), [0, 2], [1, 0], [0, -2], [-1, 0]
2
(0, 5) 2
(3, 2) 4


Output:
13
URRRRRUUUULLL

Scoring

For solving this problem you will score 10 points.