DMOPC '15 Contest 2 P3 - Origami - DMOJ: Modern Online Judge

DMOPC '15 Contest 2 P3 - Origami

Points: 7 (partial)

Time limit: 0.6s

Memory limit: 64M

Author:

Problem type

cheesecake is making origami and he needs your help! He has an arbitrarily large rectangular piece of paper that he needs to cut into $N$ $N$ pieces, whose dimensions don't matter.

cheesecake likes to be efficient. Therefore, if he can, he will stack multiple pieces of paper on top of one another and cut them all at the same time. Note that since he wants crisp origami, he will not fold any papers beforehand. For example, if he needs $4$ $4$ pieces of paper, he can cut the starting piece in $2$ $2$ , then stack the $2$ $2$ pieces together and cut them to obtain $4$ $4$ pieces. The catch is, cheesecake doesn't have very good scissors, so he can cut through at most $K$ $K$ sheets of paper at a time.

To save time, he would like for you to find out the minimum number of cuts required to obtain the $N$ $N$ pieces.

Constraints

Subtask 1 [60%]

$1 \le N, K \le 10^5$ $1 \leq N, K \leq 10^{5}$

Subtask 2 [40%]

$1 \le N, K \le 10^{18}$ $1 \leq N, K \leq 10^{18}$

Input Specification

The only line of input contains $N$ $N$ and $K$ $K$ , separated by a space.

Output Specification

One integer, the minimum number of cuts required to obtain the $N$ $N$ pieces.

Sample Input 1

Copy

4 2

Sample Output 1

Copy

Explanation for Sample Output 1

See problem description above.

Sample Input 2

Copy

100000 1

Sample Output 2

Copy

Explanation for Sample Output 2

Since cheesecake's scissors can only cut through one piece of paper at a time, he has to cut the paper $99\,999$ $99 999$ times for $100\,000$ $100 000$ pieces of paper.

Sample Input 3

Copy

100 7

Sample Output 3

Copy

Comments

-2

kevze commented on May 28, 2020, 4:31 p.m.

For the last two cases, output has to be long to prevent int overflow.

24

BucketMan commented on Nov. 10, 2015, 9:43 p.m.

True origami does not use scissors. You are not a true origami.

27

cheesecake commented on Nov. 11, 2015, 3:42 a.m. ← edited →

1

whycolt commented on Nov. 11, 2015, 1:22 a.m.

Then what do you use to cut the wood to make the paper if origami is just folding

3

Gabbyu commented on Nov. 11, 2015, 12:48 a.m.

teach me how to be an origami