网络赛前10奖励计蒜客的本子或鼠标垫(外校也可以来现场领取)

问题 1005. -- xry111的音频传输

1005: xry111的音频传输

时间限制: 1 Sec  内存限制: 128 MB
提交: 65  解决: 30
[提交][状态][讨论版]

题目描述

众所周知,xry111在硬件方面非常矬,修个耳机都能把声道焊反。现在,xry111为了传送iPhone输出的n声道音频,要接一根n声道音频线。这种线中有n根信号线和1根地线,其中地线以屏蔽层的形式出现,很好区分。但是,对于n根信号线,xry111感觉十分头疼,不敢随意连接,只好拿万用表的导通测试档测定两端线头的对应关系。

例如,若n=3,xry111要确定A端的某根线头与B端的哪一根线头相连,他就把万用表红表笔接在这根线头上,黑表笔逐个测试B端的3根线头。当万用表发出响声时,就说明此时黑表笔与红表笔连接同一根线。

显然,用这种方法,最坏情况下,他要测试n次才能找到B端对应的线头。

但是,xry111发现,他并不需要测量这么多次。例如,n=5时,xry111将B端的线头编号为1~5,则他可以把红表笔接在A端的待测线头,然后把B端的线头2、4一起接黑表笔测量一次,线头3、4一起测量一次,再单独测量一次线头5。测量结果可能有:
(1)第1次响,第2、3次不响,结果是线头2。
(2)第1、2次响,第3次不响,结果是线头4。
(3)第1次不响,第2次响,第3次不响,结果是线头3。
(4)第1、2次不响,第3次响,结果是线头5。
(5)3次都不响,结果是线头1。

现在,xry111想知道,在n确定的情况下,他最坏情况下要测量多少次,才能确定A端某根线对应在B端的线。你可以认为,音频线没有损坏,即A端的每根线头与且仅与B端的1根线头相连。

输入

输入包含多组数据,请处理到EOF。
每组数据包括1行,仅包含一个整数n。
对于100%的数据,有1<=n<=1018
输入文件满足数据组数小于等于10000。

输出

对于每组输入,输出1行,包含一个整数,表示xry111在最坏情况下的测量次数。

样例输入

1
5

样例输出

0
3

提示

第2组样例输入就是问题描述中的那个例子。

来源

[提交][状态][讨论版]