CUTSTICK - Cut Stick
Ann meets another problem.
Since she has a n-meter-long stick, she wants to cut it into small ones. Of course she would not let the small sticks be shorter than 1 meter. At the same time she is so mean that she can't stand that any three of the small sticks could make a triangle. That is to say, any 3 of the small sticks can not form a triangle if there are 3 or more small sticks.
You can assume that the small sticks only have integer length.
Input
A line contains a positive integer n, which is the length of the long stick. It does not exceed 10^5.
Output
Print a number -- the maximum number of small sticks Ann could get.
Example
Input: 1 2 3 4 Output: 1 2 2 3
hide comments
kokonut_hustle:
2020-11-24 18:42:42
there are many test cases per input, so you have to read all the input and output for all test cases |
|
Stanislav Zholnin:
2016-05-13 00:04:36
It is not obvious that there are several test cases per input. |
Added by: | [UNI]Jonathans |
Date: | 2013-03-16 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | TJU 2012 Team Selection |