#1513. 【提高】天气之子 Tenki

【提高】天气之子 Tenki

题目描述

高中一年级的夏天,少年帆高离家出走,由小岛去到东京。

但他生活极之贫困,孤独度日,终于找到的一份工,却只是为一本古怪的「神秘学杂志」写稿。

跟着连日滂沱大雨,像是来映衬他的失落。 在纷纭杂沓的大都会一角,帆高遇上了一个可爱的少女阳菜。

阳菜和弟弟相依为命,个性坚强、开朗,但心中隐藏一个重大秘密──

她拥有一股不可思议的力量,她说:「现在开始天晴了!」

然后,雨渐渐停下来,美丽的阳光洒落到街上。 那原来是能让天空放晴的超能力……

nn 个人依次进入观影厅,观看 Weathering with You

观影厅只有一排座位,第 11 个人进入时,会选择第 11 个座位坐下。

由于观影厅空调坏掉了,十分炎热,之后的每个人进入时,他会选择一个离最近的已经坐下的人尽可能远的空位。

如果有多个空位使得离最近的人同样远,则他会从其中随机选取一个。

若有两个人选择的位置相邻,他们就会不满意。

为了让所有人都满意,观影厅至少需要有几个座位呢?

输入格式

包含一行,仅一个正整数 nn,表示前来观影的人数。

输出格式

包含一行,仅一个正整数,表示至少需要的座位数目。

样例

4
8

观影厅只有 77 个位置时,前 33 个人会依次选择 1,7,41,7,433 个位置,第 44 个人无论选哪个空位,都会与其他人相邻。

观影厅有 88 个位置时,他们依次选取的位置可能是 1,8,4,61,8,4,61,8,5,31,8,5,3 两种情况,都是合法的。

数据范围与提示

测试点编号 nn
121 \sim 2 5\le 5
363 \sim 6 105\le 10^5
7107 \sim 10 1018\le 10^{18}
112011 \sim 20 101000\le 10^{1000}

对于 100%100\% 的数据, n101000n\le 10^{1000}