Problem Link:
CONTEST
PRACTICE
Author- Sameer Taneja
Tester- Vipin Khushu
Editorialist- Kushank Arora
Difficulty:
Simple
Prerequisites:
Math(Rounding) https://en.wikipedia.org/wiki/Rounding
Problem:
The aim is to round up a number to the nearest multiple of ten.
Quick Explanation:
We need to find the number which is required to be added to the number to make it a multiple of 10.
Explanation:
This looks like a simple rounding problem, doesn’t it?
for x = 0 to N+20:
if N <= x:
ans = x
break
x = x + 10
However, the program written by the above logic will get TLE. The reason being, N can be as large as 1015. It is safe to assume that a loop over 108 numbers will not take less than 1 second on the CodeChef judge. And considering that the test data will have up to 109 such numbers, we cannot pass the time limit with the above solution.
The important trick here is to notice that the x is iterating upto N which is not required. If we simply find the number which could be added to our number to round it up to nearest multiple of 10 then our solution reduces to a very small extent.
To find that specific number say R, the code is:
R = 10 – (N mod 10)
But there is a flaw, the number which is already a multiple of 10, R also becomes 10. So the solution can be further optimized as:
R = (10 – (N mod 10)) mod 10
Thus our final code, will have a single line,
R = (10 – (N mod 10)) mod 10
ans = N + R
Solution
http://ideone.com/lF5DGM