COOLCON - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

A dish starts at X degrees and needs to end at Y degrees.
If its current temperature is T, it needs \frac{T}{10} seconds, rounded up, to reduce by 1.
Find the time needed to reach the desired temperature.

EXPLANATION:

The temperature can only reduce by 1 at a time.

This means the answer can be computed via the following algorithm:

answer = 0
while (x > y):
    add ceil(x/10) to answer
    subtract 1 from x
print answer

That is, simply repeatedly reduce the temperature by 1 and add the cost of doing that to the answer.
Here, \text{ceil}(r) denotes the value obtained by rounding r up to the nearest integer.

There are a few different ways to compute \text{ceil}\left(\frac{X}{10}\right).

  • Your language’s library might have a rounding function built-in which you can use.
    For instance, C++ has std::ceil and Python has math.ceil that accomplish this.
  • Alternately, another way, working purely with integers, is to compute \frac{X+9}{10} rounded down (which is what the integer division does in most languages by default, i.e. (X+9)/10 in C++/Java and (X+9)//10 in Python).

TIME COMPLEXITY:

\mathcal{O}(X-Y) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    x, y = map(int, input().split())
    
    ans = 0
    while x > y:
        ans += (x+9) // 10
        x -= 1
    print(ans)