Tyger has an array of positive integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ of length $$$n$$$, on which he wants to perform a series of operations. An operation on an array consists of removing a number $$$x$$$ from the array and adding two positive integers $$$y$$$ and $$$z$$$ to the array such that $$$x = y + z$$$ and the addition doesn't yield any carries. Find the maximum possible number of operations Tyger can perform on the array.
The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 100)$$$, representing the length of the array.
The following line contains $$$n$$$ positive integers $$$a_1, a_2, \dots ,a_n$$$ $$$(1 \leq a_i \leq 10^{10^4})$$$, representing Tyger's original array.
Output a single integer, the maximum number of operations that can be done on array $$$a$$$.
| Subtask | Constraint | Points |
| $$$1$$$ | $$$a_i \leq 9$$$ | $$$30$$$ |
| $$$2$$$ | $$$a_i \leq 10^9$$$ | $$$40$$$ |
| $$$3$$$ | No additional constraints | $$$30$$$ |
4 1 2 3 11
4
The first element, $$$1$$$, cannot be split any further using an operation. Tyger can complete an operation and split $$$2$$$ into $$$1$$$ and $$$1$$$, and since $$$1$$$ cannot be split any further, $$$2$$$ allows for one operation. $$$3$$$ can be split into $$$2$$$ and $$$1$$$, and since $$$2$$$ can be split once and $$$1$$$ can be split no more times, we can complete a total of two operations. $$$11$$$ can be split into $$$10$$$ and $$$1$$$, allowing for one operation.
Therefore, Tyger can complete a total of $$$1 + 2 + 1 = 4$$$ operations on this array.
| Lexington Informatics Tournament 2026 |
|---|
| Закончено |
