Question

Сдать решение задачи 4-Музей Задача 4: Музей Музей представляет собой 25 квадратных залов в форме квадрата 5×5, схему которого вы можете видеть на картинке ниже. В каждом зале музея нужно повесить табличку «Продолжение осмотра», которая указывает в один из чётырёх соседних залов. Направление осмотра будем обозначать одной из четырёх букв: «L» (влево), «R» (вправо), «U» (вверх), «D» (вниз), обозначающей, в какой из четырёх соседних залов можно пройти из данного зала. Утром музей заполняется посетителями, но ввиду ограничений на численность в каждом зале первоначально располагается ровно один человек. После этого посетители музея начинают перемещаться в соседние залы в направлении стрелок. Для того, чтобы посетители музея как можно больше приобщились к прекрасному, необходимо разместить таблички так, чтобы суммарное число залов, в которых побывает каждый посетитель, было как можно больше. Считается, что посетитель может побывать в каком-либо зале, если он может попасть в этот зал, перемещаясь по стрелкам. Вам необходимо придумать такое размещение табличек. При этом не следует беспокоиться о выходах из музея: если посетителю надоест блуждать по музею, он всегда сможет выйти из него, игнорируя таблички (но уже не осматривая залы). В ответе запишите план музея — пять строк по пять символов в каждой. Каждый символ — направление обхода из соответствующего зала. Чем больше будет сумма осмотренных залов всеми посетителями музея, тем больше баллов вы получите (для каждого посетителя считается количество осмотренных им залов и берётся сумма по всем посетителям). Пример записи ответа (не являющегося оптимальным) для музея размера 3×3: UUD LLR RRD

Answer 1

Ответ:

DLLDL

DRUDU

DUUDU

DULLU

RRRRU

Чтобы посетители прошли через максимальное количество залов, я решил сделать цепочку, по которой все обходят залы. Поскольку площадь квадрата - нечетное число, у меня получилось что 24 посетителя обходят 24 зала, а один оставшийся обошел все 25 залов (поскольку он изначально стоял в том зале до которого не дошли 24 посетителя). Этот зал является центром.

Ps если хотите увидеть цепочку то она начинается с центра

Answer 2

Ответ:

RRRRD

LLLLD

RRRRD

LLLLD

RRRRL

В конце L значит выйти, а остальное я считаю понятным.

Answer 3

Для решения данной задачи нужно учесть, что каждый зал имеет 4 соседа (если они существуют). Один из способов решения этой задачи - установить таблички в каждом зале таким образом, чтобы направление обхода было противоположным тому направлению, из которого пришел посетитель. Например, если посетитель пришел из зала слева, то табличка будет указывать направление вправо, и так далее.

Вот оптимальное размещение табличек для музея размером 5×5:

Copy code
DLUUR
LURRD
RDLUD
URRDL
LDRUU

Эти таблички обеспечивают максимальное количество осмотренных залов. Посетители, начиная с любого зала, смогут посетить 22 зала из 25.