Сайт підготовки до олімпіади з інформатики

Тема. Жадібні алгоритми

Задача 1. Центи

Задача 2. Кінцевий результат

Задача 3 Знижки

1.Задача про центи

Нехай є монети номіналом 25, 10, 5 та 1 цент. Якою найменшою кількістю монет можна видати суму S центів? На думку зразу ж інтуїтивно спадає такий алгоритм розв'язування цієї задачі: спочатку візьмемо максимально можливу кількість монет номіналом 25 центів, але так, щоб ця сума не перевищу, вала S. Потім визначимо, скільки монет номіналом 10 центів не перевищить залишку від S. Ту саму операцію проведемо із монетою номіналом 5 центів. Остаточний залишок видамо мо­нетами 1 цент.

Цей алгоритм без сумніву можна назвати жадібним і записа­ти у такому вигляді:

1.     Спочатку визначити максимальне п, для якого 25 * n <= S.

2. Якщо S - 25 * п > 0, то визначити максимальне m, для яко­го 10 * m <= S - 25 * n; у протилежному випадку перейти до п. 5.

3.     Якщо S - 25 * п - 10 * m > 0, то визначити максимальне k, для якого 5 * k <= S - 25 * п - 10 * n; у протилежному випадку перейти до п. 5.

4.     Якщо S - 25 * n - 10 * m - 5 * k > 0, то суму S - 25 * п - 10 ** m - 5 * k видати монетами номіналом 1 цент.

5.     Завершити алгоритм.

Задача 2. Кінцевий результат

Вхідний файл:                                                                                 LASTASK.DAT

Вихідний файл:                                                                          LASTASK.SOL

Максимальний час роботи на одному тесті:        2сек

Змагання по розв'язуванню задач з програмування майже завершились. Залишилась остання задача - підрахувати кінцевий результат.

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

Наприклад, якщо були отримані наступні штрафні бали 2, 5, 7, 1 та 4, то учасник може

1. замінити 5 та 7 на 12; залишаться '2, 1, 4 та 12, а кінцевий результат стане рівним 12.

2.     замінити 2 та 4 на 6; залишаться 6. 1 та 12, а кінцевий результат стане рівним 18.

3.     замінити 1 та 6 на 7; залишаться 7 та 12, а кінцевий результат стане рівним 25.

4.     замінити 7 та 12 на 19; остаточно, кінцевий результат стане рівним 44.                                                         
Але можна порахувати і інакше, наприклад:

1. замінити 1 та 7 на 8; залишаться 2, 5, 4 та 8, а кінцевий результат стане рівним 8.

2.     замінити 2 та 4 на 6; залишаться 6, 5 та 8, а кінцевий результат стане рівним 14.

3.     замінити 6 та 8 на 14; залишаться 5 та 14, а кінцевий результат стане рівним 28.

4.     замінити 5 та 14 на 19; остаточно, кінцевий результат стане рівним 47.
Зрозуміло, учасник хоче щоб кінцевий результат був найменшим.

Необхідно написати програму, яка визначає найменше можливе значення кінцевого результату.

Вхідні дані. Перший рядок вхідного файлу містить єдине ціле число N (3<=N<=100000) - кількість задач. В другому рядку знаходяться N невід'ємних чисел - штрафних балів, отриманих учасником. Сусідні числа в рядку розділені пропуском.

Вихідні дані. Єдиний рядок вихідного файлу має містити одне ціле число - найменше можливе значення кінцевого результату учасника. Гарантується що відповідь не перевищує 2⁶³

Приклад.

LASTASK.DAT                     LASTASK.SOL

5                                                               41

2 5 7 1 4

Задача 3 Знижки

Відвідавши перед Новим роком великий магазин, ви обрали багато подарунків рідним та друзям. Зекономити певну кількість грошей вам можуть допомогти два типи передноворічних знижок, що діють у магазині:

1. При купівлі трьох товарів ви платите за них як за два найдорожчих з них.

2. При купівлі чотирьох товарів ви платите за них як за три найдорожчих з них.

Таким чином, певні товари можна об'єднати у трійки або четвірки і заплатити за них менше. Треба визначити найменшу можливу суму грошей, яка буде витрачена на придбання усіх подарунків. Наприклад, якщо ціни п'яти обраних подарунків складають: 50, 80, 50, 100, 20, то можна окремо придбати чотири перших товари, отримати за них знижку, та потім купити подарунок, що залишився за його номінальну ціну. Загалом вся покупка буде коштувати 250 грошових одиниць, замість 300.

Завдання. Напишіть програму DISCOUNT, що за цінами усіх подарунків, знаходить мінімальну суму грошей, якої вистачить на їх купівлю.

Вхідні дані

Перший рядок вхідного файлу DISCOUNT.DAT містить одне ціле число N (0≤N≤10 000). Другий рядок містить N натуральних чисел - ціни подарунків. Сума цін усіх подарунків менша за 10⁹. Об'єднувати можна не лише ті товари, що йдуть підряд у вхідних даних.

Вихідні дані

Єдиний рядок вихідного файлу DISCOUNT.SOL має містити одне ціле число - знайдену мінімальну суму грошей, за яку можна купити усі подарунки.

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