15. Два поезда выходят навстречу друг другу со станций 1 и 2. Карта внизу показывает ?
15. Два поезда выходят навстречу друг другу со станций 1 и 2. Карта внизу показывает ??се станции и цветные пути между ними. В каждый момент один из поездов едет, а другой стоит на какой-нибудь станции. Во время движения поезда записывается цвет отрезка пути, по которому происходит движение. К сожалению, в записи не указывается, какой из поездов движется. Например, запись BG может означать, что один из поездов прошел сначала отрезок Blue, а затем отрезок Green, или, что один из поездов прошел отрезок Blue, а другой поезд прошел отрезок Green.
Гость
Ответ(ы) на вопрос:
Гость Будем вести запись в виде Cn, где С - код цвета, n - номер поезда. Например, G2 означает, что поезд №2 прошел отрезок цвета G. Если путь невозможен, n=0. Если несколько вариантов, то их пишем в круглых скобках.
1) GBYBYGY. G2-B0 -нет поездов с доступным отрезком В
2) YYBYGGBG. Y1-Y1-B1-Y0 -нет поездов с доступным отрезком Y
3) GYGBGYBB.
Если решение есть, то оно тут. Вариантов несколько, поэтому составим возможные пути длиной 8 отрезков.
a) YBYGYYYG b) YBYBGGYYG c) YYBBGBGG d) YYBGGYYG
Но последние два отрезка пути имели коды BB, следовательно нас устроит только последовательность, в которой есть эти BB, т.е. с)
Теперь попробуем построить последовательность (3) из последовательности (с), "забирая" символы с разных сторон (слева - поезд 1, справа - поезд 2).
Первым двигается поезд 2 (G только у него) и получаем для G2:
c) YYBBGBG 3) YGBGYBB
Y в (с) слева, поэтому следующий отрезок Y1:
c) YBBGBG 3) GBGYBB
Теперь G в (с) справа и получаем G2:
c) YBBGB 3) BGYBB
Далее:
B2: c) YBBG 3) GYBB
G2: c) YBB 3) YBB
Y1: c) BB 3) BB
А теперь у нас три варианта и все три верные: B1-B1, B1-B2, B2-B2
Окончательно: G2-Y1-G2-B2-G2-Y1-(B1-B1 или B1-B2 или B2-B2).
Ответ: GYGBGYBB.
Не нашли ответ?
Похожие вопросы