QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100
[0]

# 6173. 女生散步问题

Statistics

1850年,英格兰教会的一个教区长柯克曼(T. P. Kirkman)提出了一个有趣的女生散步问题。在某女子学校中,15 个女学生同在一个学组。她们每天都要去校外散步。为了加强她们的相互了解,增进友谊,柯克曼设想,如果将女生适当分成 5 组,每组有 3 位女生,使每个女生在 7 天之内,都能够与别的女学生有且仅有一次同组机会。如何分组才能达到此目的?

这个似乎很简单的问题,却有不同寻常的分组算法。这就是后来称为柯克曼三元系的分组算法。过了一百多年,又发明了许多有趣的女生散步分组算法。其中的一个有趣的随机圆环分组算法描述如下。

设有 n 个待分组的女生。首先随机分配给每位女生一个不同的编号。这 n 个女生的编号组成的集合恰为 [1,n]。分在同一组的女生可以自由地在草地上围坐成一个圆圈。圆圈中的每位女生需要满足如下条件,即她的编号和她左右邻座女生编号的乘积均小于 n。当圆圈中只有一个女生时,其自身的编号小于 n。满足上述条件的女生分为一组。其余女生继续按此方法分组。

女生散步问题:对于给定的一个整数 n,计算最多有多少位女生可分在同一组。

输入格式

依次给出待计算的多个测试数据。每行给出由一个整数 n ,表示有 n 个待分组的女生。

输出格式

对于输入文件中的每个测试数据 n,输出这个待分组的女生中,最多有多少位女生可分在同一组,每行输出一个计算结果。

样例数据

样例输入

2
3
5
7
8

样例输出

1
2
2
3
3

子任务

测试点编号 n
15 n600000
68 n50000005
910 n1000000000

  1. 赛时并未提供数据组数,“请选手自行评估”。
  2. 题目中的描述存在歧义,但赛时并未给出任何解释。