题目描述
这是一个经典问题。原来的问题是关于树林中的树叶的,这里量化一下,改为整数选择问题。现有n个随机的正整数依次出现在你的面前。当每个数字出现时,你可以选择或放弃。一旦选择,不可更改;如果放弃,则不可返回重新选择。若前n-1个数均未选择,则必须选择第n个数。你的任务是,设计一种选择方案,使得在给定n的情况下,选择的数尽可能大。
我们提出这样一个较优的简单方案。可能存在较为复杂的方案使得选择到较大数的概率更大,但为了简化问题,我们只考虑以下方案中的“加权平均值”,即所有可能选择的数及其出现概率的乘积之和。
首先由n确定一个m。对前m个数,只记录其最大值max。对后n-m个数,若存在某数大于max,则选择此数。若前n-1个数均未选择,则选择第n个数。
你的程序需要计算出使得“加权平均值”最大的m。显然,0<=m<n。注意,n个数完全随机,可能重复,需要考虑所有情况下的概率。
输入格式
输入一行,一个整数n。数据范围:1<=n<=10000.
输出格式
输出一行,一个整数m。
样例输入
样例输出