По­строй­те схему, вы­пол­ня­ю­щую умно­же­ние вво­ди­мо­го числа в чет­ве­рич­ной си­сте­ме на 3.

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

В дан­ной за­да­че мы за­пи­сы­ва­ем число от по­след­ней цифры к пер­вой. Если ко­ли­че­ство цифр в про­из­ве­де­нии боль­ше ко­ли­че­ства цифр в мно­жи­те­ле, для пра­виль­ной ра­бо­ты ав­то­ма­та к мно­жи­те­лю спе­ре­ди нужно до­ба­вить 0 (т. е. до­ба­вить 0 в конце вво­ди­мой стро­ки).

На­при­мер, для стро­ки 123 ав­то­мат вы­даст стро­ку 322, а для стро­ки 1230 (со­от­вет­ству­ю­щей тому же са­мо­му чет­ве­рич­но­му числу 321) вы­даст ре­зуль­тат 3222 (со­от­вет­ству­ю­щий числу 2223).