Задача Toys2019. У класі НУШ  встановили автомат, який продає іграшки (реформа освіти!). Учні, звичайно ж, вишикувались у чергу, але з’ясувалося, що:

  • Вартість іграшки – 1 гривня;
  • Кожен учень може придбати лише одну іграшку;
  • Автомат приймає лише купюри 1, 2 та 5 гривень і видає за потребою решту;
  • У кожного учня є лише одна купюра;
  • Якщо автомат не має чим видати решту, він зупиняється;
  • На початку роботи в автоматі немає жодної купюри;
  • Учні категорично не хочуть мінятися місцями в черзі і пропускати інших учнів.

Скільки учнів зможуть придбати іграшки?

Технічні умови. Програма Toys2019 читає з пристрою стандартного введення в першому рядку кількість учнів N – натуральне число, не більше 105, в другому – N розділених пропуском чисел 1, 2 або 5 – номінали купюр учнів в черзі, починаючи від автомата. Програма виводить на пристрій стандартного виведення єдине число – максимальну кількість учнів, що придбають іграшки.

Приклад

Введення

7

1 2 1 2 5 5 1

Виведення

5

© LIKT 1998-2018