4319: 倒水

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:197 Solved:75

Description

一天,树树买了N个容量可以认为是无限大的瓶子,初始时每个瓶子里有1水。树树发现瓶子实在太多了,于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子合并,把一个瓶子的水全部倒进另一个瓶,然后把空瓶丢弃(不能丢弃有水的瓶子)。

显然在某些情况下树树无法达到目标,比如N=3K=1.此时树树会重新买一些新的瓶子(新瓶子容量无限,开始时有1水,以达到目标。

现在树树想知道,最少需要买多少新瓶子才能达到目标呢?

Input

一行两个正整数NK1<=N<=109,K<=1000)。

Output

一个非负整数,表示最少需要买多少新瓶子。

Sample Input Copy

3 1

Sample Output Copy

1

HINT

对于30%的数据,N<=3*105;

对于100%的数据如题目。

Source/Category

加入题单

算法标签: