Вы­яс­ним, как устро­ен ва­ри­ант вы­да­чи про­из­воль­ной суммы наи­мень­шим чис­лом монет. Возь­мем любой спо­соб вы­дать дан­ную сумму N. Если в нем ис­поль­зо­ва­но не менее 9 брон­зо­вых руб­лей  — за­ме­ним 9 из них на се­реб­ря­ную мо­не­ту. Ана­ло­гич­но если есть хотя бы 9 се­реб­ря­ных монет  — за­ме­ним на зо­ло­тую. При этом число монет будет умень­шать­ся.

Пусть те­перь ис­поль­зо­ва­но a зо­ло­тых, b се­реб­ря­ных и c брон­зо­вых монет, тогда Зна­чит, крат­но 9. Такое един­ствен­но  — это оста­ток от де­ле­ния N на 9. Ана­ло­гич­но, по­сколь­ку можно од­но­знач­но найти b как оста­ток от де­ле­ния на 9. После этого и a опре­де­лит­ся од­но­знач­но по фор­му­ле

Итак, любой ва­ри­ант может быть при­ве­ден к та­ко­му, и, зна­чит, этот ва­ри­ант оп­ти­ма­лен.

а)  Имеем: по­это­му тре­бу­ет­ся как ми­ни­мум монет.

б)  Имеем: по­это­му тре­бу­ет­ся как ми­ни­мум монет.

в)  Пусть для вы­пла­ты N руб­лей ис­поль­зо­ва­но a зо­ло­тых, b се­реб­ря­ных и c брон­зо­вых монет, тогда при­чем Раз­бе­рем ва­ри­ан­ты.

Если то и по­то­му

Если то и по­то­му

Если то

Под­хо­дит толь­ко пер­вый ва­ри­ант.

Ответ: а)  37; б)  нет; в)  647.