OJ Board

Is there any good ways of doing this problem without bruteforce?

My program takes a very very long time to check if a case is impossible, but if it is possible, then generates the solution rather quickly. For some input values, it is easy to prove mathematically that they are impossible.

I noticed that you now have a solution that runs in 0.004 seconds. May I assume that you've found the trick? Or is it a printf solution? If the former, could you shed some light?

My 'brute-forcer' finishes just in time, but I had to 'wax it up' by adding printfs for the slowest two inputs

It's just printf's. If I tried to generate all of them it also tle. It also just finishes in time if I printf the slowest cases, like the ones with base > 25.
Also I have to also figure out which ones are impossible, so I don't generate them. It seems that if it can't find a solution in 1 sec, then that case is impossible.

I see
About the impossible cases: they will not appear in the input, so once your solution is fast enough for the possible cases, you're done.

Anyone else wants to comment on a fast solution?

My system is about twice as fast as the UvA judge.

In my program where I pick the next digit I tried to both iterate both forward and backward. When I iterate forward it takes me 1654 seconds to compute the answers for all valid inputs.

When I iterate backward I can do everything except (B=27,N=24) and (B=26,N=13) in a total time of 5.3 seconds. Those two included it takes me 37.1 seconds. I'm not sure why this makes such a big difference, apparently solutions are more likely to have larger digits at the back of the numerator, but why?

I decided to precalculate everything, but I wonder if there is another trick.

Johan de Ruiter