oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

idolclub Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

idolclub.html

Problem Description

Fan Pu is the manager of a new idol club!

Fan Pu desires to have exactly N members in his idol club. The idol club has 0 idols at first. To recruit idols, Fan Pu will go idol scouting over a period of time.

Below is how a typical day of idol scouting works:

1. Fan Pu wakes up in the morning and checks how many idols there are in his club. If there are exactly N idols, he terminates the scouting process and will no longer go scouting.

2. Every idol in Fan Pu's club will recruit K new idols using their influence. That is to say, the number of idols in Fan Pu's club will increase by (K + 1) times.

3. Then, Fan Pu can personally recruit some idols to his club. He can recruit as few as 0 idols, and as many as N idols.

4. Fan Pu then goes to bed and repeats the process from step 1.

As Fan Pu is a lazy manager, and convincing new idols to join his club is a tough job, he wants to personally recruit as few idols as possible.

What is the least number of idols Fan Pu needs to personally recruit, in order to have exactly N idols in his club?

Input

The first line of input contains two integers N and K, the number of idols Fan Pu desires to have, and the number of new idols each existing idol will recruit.

Output

Output a single integer, the least number of idols Fan Pu must personally scout.

Limits

Subtask 1 (21%): 1 ≤ N ≤ 10. K = 1 (i.e. the number of idols will double on step 3).

Subtask 2 (23%): 1 ≤ N ≤ 10. 1 ≤ K ≤ N - 1.

Subtask 3 (25%): 1 ≤ N ≤ 109, K = 1 (i.e. the number of idols will double on step 3).

Subtask 4 (31%): 1 ≤ N ≤ 109. 1 ≤ K ≤ N - 1.

Subtask 5 (0%): Sample Testcases

Sample Testcase 1

Input

8 1

Output

1

Explanation

To have exactly 8 idols, Fan Pu needs to do the following:

Day 1
1. There are 0 idols.
2. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are still 0 idols.
3. Fan Pu recruits 1 new idol. There is 1 idol now.
4. Fan Pu goes to bed.

Day 2
1. There is 1 idol.
2. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are 2 idols now.
3. Fan Pu recruits 0 new idols. There are still 2 idols now.
4. Fan Pu goes to bed.

Day 3
1. There are 2 idols.
2. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are 4 idols now.
3. Fan Pu recruits 0 new idols. There are still 4 idols now.
4. Fan Pu goes to bed.

Day 4
1. There are 4 idols.
2. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are 8 idols now.
3. Fan Pu recruits 0 new idols. There are still 8 idols now.
4. Fan Pu goes to bed.

Day 5
1. There are 8 idols. Fan Pu sees that he has achieved the desired number of idols and terminates the scouting process. Fan Pu has recruited 1 idol in total personally in the process.

Sample Testcase 2

Input

7 1

Output

3

Explanation

To have exactly 7 idols, Fan Pu needs to do the following:

Day 1
1. There are 0 idols.
2. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are still 0 idols.
3. Fan Pu recruits 1 new idol. There is 1 idol now.
4. Fan Pu goes to bed.

Day 2
1. There is 1 idol.
3. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are 2 idols now.
2. Fan Pu recruits 1 new idol. There are 3 idols now.
4. Fan Pu goes to bed.

Day 3
1. There are 3 idols.
2. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are 6 idols now.
3. Fan Pu recruits 1 new idol. There are 7 idols now.
4. Fan Pu goes to bed.

Day 4
1. There are 7 idols. Fan Pu sees that he has achieved the desired number of idols and terminates the scouting process. Fan Pu has recruited 3 idols in total personally in the process.

Sample Testcase 3

Input

17 2

Output

5

Explanation

To have exactly 17 idols, Fan Pu needs to do the following:

Day 1
1. There are 0 idols.
2. Each existing idol recruits 2 new idols. The number of idols increases by 3 times (i.e. triple). There are still 0 idols.
3. Fan Pu recruits 1 new idol. There is 1 idol now.
4. Fan Pu goes to bed.

Day 2
1. There is 1 idol.
2. Each existing idol recruits 2 new idols. The number of idols increases by 3 times (i.e. triple). There are now 3 idols.
3. Fan Pu recruits 2 new idols. There are 5 idols now.
4. Fan Pu goes to bed.

Day 3
1. There are 5 idols.
2. Each existing idol recruits 2 new idols. The number of idols increases by 3 times (i.e. triple). There are now 15 idols.
3. Fan Pu recruits 2 new idols. There are 17 idols now.
4. Fan Pu goes to bed.

Day 4
1. There are 17 idols. Fan Pu sees that he has achieved the desired number of idols and terminates the scouting process. Fan Pu has recruited 5 idols in total personally in the process.

Tags

Math

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
121101s256MBMinimum
223461s256MBMinimum
325301s256MBMinimum
4311161s256MBMinimum
5031s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o idolclub -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.