1632: 对尽少移动棋子使正三角形实现翻折的研究

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：5 Solved：0

Description

用同样的圆棋子构成如图所示的正三角形（由白棋与黑棋组成），只要适当
移动原三角形顶点周围的某些棋子就能使原图形实现一次翻折. 例如当正三角
形每一边上的棋子数分别为5 与6 个时，按照图 1 与图2 的方法，可以将原图形
通过将其中的黑棋移动到涂有阴影的棋子处，得到新图形（由白棋与涂有阴影的
棋组成），从而实现翻折. 移动的棋子数分别为5 与7 .
 

 请根据上述规定，研究以下问题：

1. 用搜索算法求当正三角形每一边上的棋子数为N ( 1<N<10000)个时，至少要移动多少个棋子才能实现原图形一次翻折？

2. 当正三角形每一边上的棋子数为N ( N 为大于1的正整数)个时，至少要移动多少个棋子才能实现原图形一次翻折？请给出用N 表示移动的棋子数S 的关系式并说明理由。（用PPT说明你的研究过程）


Input

正三角形每一边的棋子数N（1<N<10000)

Output

能实现图形翻折的最少移动棋子数。

Sample Input Copy 

6

Sample Output Copy 

7