SIOKULE - Kule
Secret Committee members, Little Petar and Little Tux, enjoy playing the board game "Kule" during the breaks between preparing contests and exam revision. The rules of the game assume that the players initially have at their disposal a set of cubes, stacked together to form a tower.
A single turn has Petar splitting the tower into two or more smaller towers, and then ordering these smaller towers in an array. Tux then has to choose one of the smaller towers. This tower will be used for all future turns, while the remainder is discarded. If Tux chooses the kth tower, Petar is obliged to pay k2 dinars to him immediately (e.g. if Tux chose the 3rd tower in the array, Petar has to give him 9 dinars). The game concludes when only a single cube remains.
As it is well-known that Secret Committee members don't have time for anything (including playing games), Petar and Tux decided to, instead of actually playing the game, trust each other that they would have played optimally, and that Petar should immediately give Tux the amount of dinars that he would have won under that condition. They have asked for your help in determining this amount.
Input
The first and only line of the standard input contains a single integer N, the number of cubes in the initial tower.
Output
Write to the first and only line of the standard output a single integer M, representing the amount of dinars that Petar should give to Tux.
Example
Input: 7 Output: 8
Explanation
In one of the possible pair of optimal strategies for Petar and Tux, Petar first splits the tower into two towers of heights 5 and 2 (in that order). Tux chooses the second tower and he immediately gets 4 dinars, after which Petar is forced to split the tower into two towers of heights 1 each. Tux once again chooses the second tower, gaining a total of 8 dinars.
Constraints
- 2 <= N <= 10100
hide comments
vagesh_verma:
2015-07-14 11:28:22
can we do it in this way--
|
|
Avi Aryan:
2015-07-14 08:59:18
@Akash Goel . But in last one he will choose the 2nd "1" , so his total will be 5 + 2^2 = 9 |
|
Akash Goel:
2015-07-13 14:26:54
@PetarV @jkelava6 - shouldn't the optimal answer for test case be 6?
|
|
jkelava6:
2015-07-02 11:02:27
@Jaswanth taking tower 2 made of 1 cube wouldn't be optimal in that scenario, but taking tower 1 made of 6 cubes! |
|
Jaswanth:
2015-07-01 08:56:58
@PetarV : Why can't we split the Tower with 7 cubes into 6 and 1 and so the answer will be 4 . given " trust each other that they would have played optimally" .
|
Added by: | PetarV |
Date: | 2015-06-23 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 JS-MONKEY |
Resource: | Serbian Olympiad in Informatics 2015 (by Dušan Zdravković) |