问题1449--Lucky Numbers

1449: Lucky Numbers

时间限制: 1 Sec  内存限制: 32 MB
提交: 83  解决: 28
[状态] [讨论版] [提交] [命题人:]
题目描述

A lucky number is made by the following rules:

Given a positive integer sequence {x | 1 <= x <= n}. From the first number, delete the last one in every 2 numbers. Select the minimum that has not been unused from the rest numbers. This number is xi. Then delete the last number in every xi numbers.

输入

There are several test cases, ended by the end of file. Each test case has a positive integer n.(3<=n<=10000)

输出

Output the number of lucky numbers in one line.

样例输入 Copy
20
30
样例输出 Copy
6
8
提示

eg.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

For the first time, delete the last number in every two numbers. The sequence become 1 3 5 7 9 11 13 15 17 19

For the second time, the minimum number that has never been used is 3. Delete the last number in every 3 numbers. The sequence become 1 3 7 9 13 15 19

For the third time, the minimum number that has never been used is 7. Delete the last number in every 7 numbers. The sequence becomes 1 3 7 9 13 15.

Then you cannot delete any numbers. There are 6 numbers left over. So the answer is 6.

来源/分类