Задания
Версия для печати и копирования в MS Word
Тип Д12 № 8662
i

Ис­пол­ни­тель Чертёжник пе­ре­ме­ща­ет­ся на ко­ор­ди­нат­ной плос­ко­сти, остав­ляя след в виде линии. Чертёжник может вы­пол­нять ко­ман­ду сме­стить­ся на (a, b), где a, b – целые числа. Эта ко­ман­да пе­ре­ме­ща­ет Чертёжника из точки с ко­ор­ди­на­та­ми (x, y) в точку с ко­ор­ди­на­та­ми (x + a; y + b).

На­при­мер, если Чертёжник на­хо­дит­ся в точке с ко­ор­ди­на­та­ми (4, 2), то ко­ман­да сме­стить­ся на (2, -3) пе­ре­ме­стит Чертёжника в точку (6, -1).

Цикл

    ПО­ВТО­РИ число РАЗ

        по­сле­до­ва­тель­ность ко­манд

    КОНЕЦ ПО­ВТО­РИ

озна­ча­ет, что по­сле­до­ва­тель­ность ко­манд будет вы­пол­не­на ука­зан­ное число раз (число долж­но быть на­ту­раль­ным).

Чертёжнику был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм (бук­ва­ми n, a, b обо­зна­че­ны не­из­вест­ные числа, n>1):

НА­ЧА­ЛО

    сме­стить­ся на (60, 100)

    ПО­ВТО­РИ n РАЗ

        сме­стить­ся на (a, b)

        сме­стить­ся на (33, 44)

    КОНЕЦ ПО­ВТО­РИ

    сме­стить­ся на (13, 200)

    сме­стить­ся на (-1, 60)

КОНЕЦ

Ука­жи­те наи­боль­шее воз­мож­ное зна­че­ние числа n, для ко­то­ро­го най­дут­ся такие зна­че­ния чисел a и b, что после вы­пол­не­ния про­грам­мы Чертёжник воз­вра­тит­ся в ис­ход­ную точку.

Спрятать решение

Ре­ше­ние.

За время ра­бо­ты про­грам­мы Чертёжник сдви­нет­ся на век­тор  левая круг­лая скоб­ка 60 плюс n умно­жить на a плюс 33 умно­жить на n плюс 13 минус 1, 100 плюс n умно­жить на b плюс 44 умно­жить на n плюс 200 плюс 60 пра­вая круг­лая скоб­ка = левая круг­лая скоб­ка n умно­жить на левая круг­лая скоб­ка a плюс 33 пра­вая круг­лая скоб­ка плюс 72, n умно­жить на левая круг­лая скоб­ка b плюс 44 пра­вая круг­лая скоб­ка плюс 360 пра­вая круг­лая скоб­ка .

По усло­вию также из­вест­но, что этот век­тор равен (0, 0).

Таким об­ра­зом, имеем:

n умно­жить на левая круг­лая скоб­ка a плюс 33 пра­вая круг­лая скоб­ка = минус 72, n умно­жить на левая круг­лая скоб­ка b плюс 44 пра­вая круг­лая скоб­ка = минус 360

От­ве­том будет наи­боль­ший общий де­ли­тель чисел -72 и -360  — 72.

Раздел кодификатора ФИПИ: 1.6.2 Вы­чис­ли­мость. Эк­ви­ва­лент­ность ал­го­рит­ми­че­ских мо­де­лей