Кондитерська фабрика (fixcandy)

Як і всі діти, Дім Дімич великий ласун, а тому, коли його спитали, де він хоче працювати, коли виросте, він, очевидно, відповів – виробляти цукерки. Коли ж фіксіки поцікавились, чи уявляє він, у чому буде полягати його робота, він відповів, що це не важливо, аби можна було з’їсти цукерок скільки завгодно. Сімка вирішила продемонструвати Дім Дімичу роботу на фабриці по упаковці вже готових цукерок.

Виконує упаковку фасувально-пакувальний автомат, який має N резервуарів, у кожен з яких кожну секунду потрапляє рівно одна цукерка. Цукерки пакуються рівно по k штук у коробці, а тому, як тільки в одному з резервуарів трапляється вказана кількість цукерок, вони відправляються на упаковку і резервуар стає пустим. Далі заповнення резервуару починається спочатку.

Коли Дім Дімич з’явився на фабриці, в кожному резервуарі автомата знаходилась деяка кількість цукерок. Йому доручили виготовити не менше L коробок по k цукерок, а після виконання завдання звільнити всі резервуари від цукерок, що залишилися. Сімка, почувши це, жахнулася, прекрасно розуміючи, що звільнення резервуарів перетвориться на їх поживу. А це означало, що хворі зуби Дім Дімичу забезпечені.

Поки робота тільки налагоджується, вона звернулася по допомогу до вас: мінімізувати кількість цукерок, що потрібно з’їсти. А для цього потрібно визначити, за який мінімальний час Дім Дімич гарантовано виконає (а може, і перевиконає) завдання, а кількість цукерок у резервуарах залишиться мінімально можливою.

Формат введення-виведення:

Програма fixcandy спочатку зчитує з клавіатури (стандартного пристрою введення) три цілих числа N, K, L (1≤N≤106, 1≤K≤109, 0≤L≤109). Потім зчитується N невід’ємних цілих чисел a1, a2 ,… aN строго менших К – кількість цукерок у кожному з резервуарів автомата перед початком роботи.

Програма fixcandy виводить на екран (стандартний пристрій виведення) одне число – мінімальну тривалість зміни, при якій гарантовано виконано завдання і при якій Дім Дімичу доведеться з’їсти мінімальну кількість цукерок.

Приклад вхідних та вихідних даних

Введення

Виведення

3 3 2

1 1 2

2

 

Примітка: В момент часу 0 (початок зміни) у резервуарах знаходиться (1, 1, 2) цукерок.

0 сек: (1, 1, 2)

1 сек: (2, 2, 0) => 1 упаковка

2 сек: (0, 0, 1) => 2 упаковки, всього 3

Таким чином, на другій секунді завдання вже виконано, а сума цукерок, яку потрібно з’їсти, мінімальна.

© LIKT 1998-2018