Problem A
Chopping Tomatoes
Languages
en
sv
At the Svensson household, tacos are served every Friday. This means that $N$ tomatoes must be cut into quarters. To optimize the process, they’ve discovered it’s possible to slice two tomato pieces simultaneously instead of just one. A single cut can mean slicing two whole tomatoes into halves, two half tomatoes into quarters, or slicing one whole and one half tomato into halves and quarters, respectively. What’s the minimum number of cuts required to divide all tomatoes into quarters?
Input
The input consists of a single line containing an integer $N$ ($1 \leq N \leq 10^9$).
Output
Output a single integer: the minimum number of cuts required to divide all tomatoes into quarters.
Scoring
Your solution will be tested on multiple groups of test cases. To receive points for a group, you must pass all test cases in the group.
|
Group |
Points |
Constraints |
|
1 |
15 |
$N \leq 10$ |
|
2 |
15 |
$N = 2s$ where $s$ is an integer |
|
3 |
70 |
No additional constraints |
Explanation
In the second sample case, you can first cut two tomatoes at a time three times to divide the first six tomatoes. Then, you can split the seventh tomato with one cut. Afterward, seven more cuts can be used to split all fourteen tomato halves two at a time. In total, this requires in eleven cuts.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 |
11 |
| Sample Input 3 | Sample Output 3 |
|---|---|
100 |
150 |
