UVa 136

From Algorithmist

Contents 1 136 - Ugly Numbers 2 Summary 3 Explanation 4 Input 5 Output 6 References

[edit] 136 - Ugly Numbers

• http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=72
• http://acm.uva.es/p/v1/136.html

[edit] Summary

Since there is no input to this problem (you only need to print a certain string), brute forcing will be fine done locally. The number will fit comfortably into a 32-bit signed integer. Instead of brute forcing it, you could use dynamic programming to build up the solution.

[edit] Explanation

This problem uses the fact that n is an ugly number if is an ugly number (with ). We can then use Dynamic Programming to fill in the rest.

[edit] Input

There is no input to this problem.

[edit] Output

There is only one output to this problem.

[edit] References

Ugly numbers are 5-smooth numbers:

• http://en.wikipedia.org/wiki/Smooth_number
• http://mathworld.wolfram.com/SmoothNumber.html

See also UVa_443