Фор­ма­ли­зу­ем ше­рен­гу в ка­че­стве ло­ман­ной, на­ри­со­ван­ной на клет­ча­том лист­ке, со­сто­я­щую из диа­го­на­лей кле­ток этого листа. Если сол­дат смот­рит на­пра­во, то ему от­ве­ча­ет линия, иду­щая по диа­го­на­ли «/», a если сол­дат смот­рит на­ле­во, то ему от­ве­ча­ет «\». Каж­дую се­кун­ду все со­че­та­ния «∧» ме­ня­ют­ся на «∨». Дви­же­ние в ше­рен­ге пре­кра­тить­ся и сол­да­ты смо­гут разой­тись в раз­ные сто­ро­ны тогда, когда в ло­ман­ной не оста­нет­ся ни од­но­го со­че­та­ния «∧». Число сол­дат по­вер­ну­тых в ту или иную сто­ро­ну оста­ет­ся по­сто­ян­ным, по­это­му концы ло­ман­ной за­фик­си­ро­ва­ны на про­тя­же­нии всего вре­ме­ни дви­же­ния в ше­рен­ге. Ко­неч­ная ло­ман­ная будет иметь един­ствен­ный излом типа «∧».

ше­рен­га из пяти сол­дат в на­чаль­ный мо­мент вре­ме­ни сразу после

по­во­ро­та по ко­ман­де «НАЛЕ-ВО» со­от­вет­ству­ет крас­ной ло­ман­ной.

Из­ме­не­ния через одну и две се­кун­ды (по крас­ной стрел­ке и зе­ле­ной стрел­кам)

ука­за­ны синим и зе­ле­ным со­от­вет­ствен­но.

Стро­ки, в ко­то­рых на­хо­дит­ся ло­ман­ная за­ну­ме­ру­ем свер­ху вниз, на­чи­ная с 1. Тогда, если в мо­мент вре­ме­ни t на стро­ке k на­хо­дит­ся излом типа «∧», то в мо­мент вре­ме­ни на стро­ке ровно под «∧» по­яв­ля­ет­ся излом типа «∨». Про­цесс за­кан­чи­ва­ет­ся тогда, когда не оста­ет­ся ни од­но­го из­ло­ма типа «∧», по­это­му в любой мо­мент вре­ме­ни пока про­цесс не за­кон­чил­ся на какой-то из строк на­хо­дит­ся излом типа «∧».

За­ме­тим, что на стро­ке 1, на­чи­ная с мо­мен­та вре­ме­ни не может быть ни од­но­го из­ло­ма типа «∧», от­сю­да сле­ду­ет, что в мо­мент вре­ме­ни новых из­ло­мов на стро­ке 2 не по­яв­ля­ет­ся, по­сколь­ку на стро­ке 1 уже не было ни од­но­го из­ло­ма типа «∧». Об­ра­тим вни­ма­ние также на то, что те из­ло­мы типа «∧», ко­то­рые были в мо­мент вре­ме­ни на стро­ке 2 пе­ре­хо­дят в из­ло­мы на стро­ке 3, по­это­му на стро­ке 2 на­чи­ная с мо­мен­та вре­ме­ни t  =  2 нет ни од­но­го из­ло­ма типа «∧».

Ана­ло­гич­но, если в мо­мент вре­ме­ни на стро­ке n нет ни од­но­го из­ло­ма типа «∧», то в мо­мент вре­ме­ни на стро­ке нет ни од­но­го из­ло­ма типа «∧» по­то­му что те, что были в мо­мент вре­ме­ни пе­ре­шли в из­ло­мы на стро­ке а новых не по­яви­лось по­то­му что не было на стро­ке n.

Таким об­ра­зом, время, не­об­хо­ди­мое для за­вер­ше­ния про­цес­са не боль­ше, чем ко­ли­че­ство строк, за­ни­ма­е­мых на­чаль­ной и ко­неч­ной кон­фи­гу­ра­ци­я­ми, сов­ме­щен­ны­ми на одном ри­сун­ке. Об­ра­тим вни­ма­ние, что по­сколь­ку ко­ли­че­ство раз­вер­нув­ших­ся в ту или иную сто­ро­ну сол­дат по­сто­ян­но, то сумма вы­со­ты ло­ман­ной на­чаль­ной кон­фи­гу­ра­ции и вы­со­ты ло­ман­ной ко­неч­ной кон­фи­гу­ра­ции не может пре­вы­шать ко­ли­че­ство столб­цов, а самая вы­со­кая ком­би­на­ция до­сти­га­ет­ся если на­чаль­ная кон­фи­гу­ра­ция цен­траль­но сим­мет­рич­на по от­но­ше­нию к ко­неч­ной кон­фи­гу­ра­ции, тогда время равно

Таким об­ра­зом, для за­вер­ше­ния дви­же­ния в ше­рен­ге после вы­пол­не­ния ко­ман­ды «НА­ЛЕ­ВО» со­став­ля­ет се­кун­ду.

Ответ: се­кун­ду.