SNOWGAME - Snowball Game

no tags 

Farmer John's N (1 <= N <= 1018) cows went for a trip around the world. Now they are at the North Pole. They decided to play a snowball game. Each of the cows made one snowball. As it is known, heavier snowballs make more harm. FJ is sure that cows' snowballs are of the same weight except one snowball, which is heavier. FJ has one balance scale. With it he can know which of two snowball groups is heavier. Snowballs get damaged when weighed, so each snowball can take part in a weighing at most K (1 <= K <= 10000) times. Help FJ find the minimal number of weighings after which he can find the heaviest snowball.

Input

The only line of input file contains numbers N and K.

Output

The only line of output file contains minimum number of weighings.

Example

Input:
19 2

Output:
3

hide comments
lzh2016c01: 2019-10-26 05:04:23

Difficult but interesting!

Last edit: 2019-11-03 09:58:38
ompr7371: 2015-10-12 11:50:17

pl check my submission id 15348748

Kumar Anurag: 2010-05-10 23:10:12

interesting one!!

Robert Gerbicz: 2010-05-09 10:52:45

RE topcoder:
Yes, the sample testcase is correct.

nishaanth: 2010-05-09 09:53:46

is the sample testcase right??
Wont we get 4 as the answer,6*3+1,check the 3 groups and 1 more to check the heavier among the 3...please correct me if i am wrong..


Added by:Hayk Saribekyan
Date:2010-05-07
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP CPP14 C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCALA SCM guile SCM qobi ST TCL TEXT WHITESPACE
Resource:RAU School Contest 2010 (Own task)