It was some time ago, since I last took a look at programming challange in CodeForces, thus I have decided to take a look again. So, I chose the lowest problem of the second division just to boost up my ego, by thinking “How easy are these problems” and to do something further. The problem initially was looking quite trivial:
You are given an integer n and an integer k. In one step you can do one of the following moves:
- decrease n by 1;
- divide n by k if n is divisible by k.
For example, if n=27 and k=3 you can do the following steps: 27→26→25→24→8→7→6→2→1→0
You are asked to calculate the minimum number of steps to reach 0 from n.
So, without paying too much attention to the time limit of 1 second, I really though that a simple code like this one would work quite ok:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
while (n != 0) { if (n % k >= 1) { counter += n % k; n -= n % k; } if (n>=k) { n /= k; counter++; } } Console.WriteLine(counter); |
It was working quite ok on the input tests and I decided simply to give it a try. Well, on the second submission test it exploded with time error. The test was looking like this:
|
1 2 3 4 5 6 |
91 999999999999999999 1000000000000000000 999999999999999999 100000000000000000 999999999999999999 10000000000000000 999999999999999999 1000000000000000 ... |
Thus, it was obvious that it will not go within a second, if someone was looping through every possible value and removing 1. Something more clever had to be developed…
The solution
The solution was a bit too tough for a first question in the second division, actually. But I found a working solution, which did not have to loop through every number but adds the remainders of the division:
|
1 2 3 4 5 |
if (n % k >= 1) { counter += n % k; n -= n % k; } |
The second case, was when n is actually bigger or equal than k. The first case would always give remainder, if n is smaller thank k. Furthermore, if the first condition has passed, then if we enter the second condition, n is divisable by k without remainder:
|
1 2 3 4 5 |
if (n>=k) { n /= k; counter++; } |
Here is the complete code, which has passed correctly through the solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
static void Main() { int total = int.Parse(Console.ReadLine()); for (int i = 0; i < total; i++) { List<BigInteger> nk = ReadLineAndParseToList(); BigInteger n = nk[0]; BigInteger k = nk[1]; BigInteger counter = 0; while (n != 0) { if (n % k >= 1) { counter += n % k; n -= n % k; } if (n>=k) { n /= k; counter++; } } Console.WriteLine(counter); } } public static List<BigInteger> ReadLineAndParseToList() { return Console.ReadLine().Split().Select(BigInteger.Parse).ToList(); } |
Cheers! 🙂