1208: 正整数序列(noip模拟题)

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:3 通过:2

题目描述

给定正整数 n,你的任务是用最少的操作次数把序列 1,2,···,n 中的所有数都变成 0。每次操作可从序列中选择一个或多个整数,同时减去一个相同的正整数。比如对于序列 1,2,3,可以把 2 和 3 同时减小 2,得到 1,0,1。

输入格式

输入仅一行, 为正整数 n。

输出格式

输出一行,为最少操作次数。

输入样例 复制

3

输出样例 复制

2

数据范围与提示

对于 20% 的数据,有 1 ≤ n ≤ 20
对于 40% 的数据,有 1 ≤ n ≤ 104
对于 60% 的数据,有 1 ≤ n ≤ 10 6
对于 100% 的数据,有 1 ≤ n ≤ 109

分类标签