Ідея розв’язку олімпіадної задачі А

Задача А.

Ідея розв’язку задачі.

        Розглянемо перший тест у якому k = 3 – число ударів, які отримав кожний

«зелений чоловічок». Найбільше ударів завдав Тур n =7, найменше Грай - m

=3. Загальне число ударів, отриманих «зеленими чоловічками», має ділитися на

k = 3. Число ударів, нанесених козаком Граєм, менше від n =7, але більше за m

=3. Воно може дорівнювати або 4, або 5, або 6. Загальне число ударів може

дорівнювати 7+4+3=14, або 7+5+3=15, або 7+6+3=16.

           З трьох отриманих чисел тільки 15 ділиться на k = 3.

 Для цього тесту число 5 є відповіддю і воно єдине.

              З цих міркувань випливає ідея знаходження відповіді на задачу: рухаючись від

m вгору, знайти перше таке число i (m<i<n) щоб число m+i+n ділилося

без остачі на k. Цим самим знайдемо мінімальне число ударів, які б міг завдати

Грай. Аналогічно, рухаючись вниз від числа n, знайдемо максимальне число

ударів, які міг би завдати Грай. Такий підхід може набрати 90 балів. 

            Щоб отримати повний бал слід врахувати наступне:

 мінімальне число ударів, які міг би завдати Грай, більше за число m на величину, що рівна: k-(m+m+n) %k(%-операція mod) Аналогічно, максимальне число ударів, які міг би

завдати Грай, менше за число n на величину: k - (m+ n +n)% k. 

При цьому слід врахувати властивість операція %(mod): (x+y)%k=(x%k +y

%k)%k. Такий підхід дає повний бал.