UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#211718#2909. numberLZDQ00ms0kbPython32.4kb2024-09-13 10:30:392024-09-13 10:30:40

answer

import sys
# import threading

# import sys
# import threading

def main():
    import sys
    # sys.setrecursionlimit(1 << 25)
    q = int(sys.stdin.readline())
    queries = []
    for _ in range(q):
        x_str, y_str = sys.stdin.readline().split()
        x = int(x_str)
        y = int(y_str)
        queries.append((x, y))

    for x, y in queries:
        visited = set()
        while x <= y and x not in visited:
            visited.add(x)
            s = sum(map(int, str(x)))
            x += s
        print(x)
        
# threading.Thread(target=main).start()
            
# threading.Thread(target=main).start()
main()



"""

def main_2():
    import sys
    sys.setrecursionlimit(1 << 25)
    q = int(sys.stdin.readline())
    queries = []
    for _ in range(q):
        x_str, y_str = sys.stdin.readline().split()
        x = int(x_str)
        y = int(y_str)
        queries.append((x, y))

    for x, y in queries:
        while x <= y:
            s = sum(map(int, str(x)))
            # Compute the minimal t to reach next change in sum of digits
            # For simplicity, we can assume t = 1 (since sum_of_digits changes frequently)
            # But to optimize, we can compute t more accurately

            # Check if adding s will exceed y
            if x + s > y:
                x += s
                break

            # Compute t_max where sum_of_digits(x + s * t) remains the same
            # We can approximate t_max as the minimal t where any digit rolls over
            min_t = float('inf')
            x_str = str(x)
            n_digits = len(x_str)
            s_int = int(s)
            for i in range(n_digits):
                digit = int(x_str[-(i+1)])
                # We want to find t such that (digit + s * t) % 10 == 0
                # Solve for t: (digit + s * t) % 10 == 0
                remainder = (10 - digit) % 10
                if s_int == 0:
                    continue  # Avoid division by zero
                t = (remainder) // s_int
                if (remainder) % s_int != 0:
                    t += 1
                if t == 0:
                    t = 10 // s_int
                if t > 0:
                    min_t = min(min_t, t)
            if min_t == float('inf'):
                min_t = 1
            x += s * min_t
            if x > y:
                break
        print(x)

# threading.Thread(target=main).start()
# main_2()
"""

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

500000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 ...

output:

2
4
4
8
8
8
8
16
16
16
16
16
16
16
16
23
23
23
23
23
23
23
28
28
28
28
28
38
38
38
38
38
38
38
38
38...

result:


Subtask #2:

score: 0
Skipped

Subtask #3:

score: 0
Time Limit Exceeded

Test #4:

score: 0
Time Limit Exceeded

input:

50
4587480273 4587480273
428862505 500400481
6920415626 7358620174
7787875953 7787884613
4542304779 ...

output:


result:


Subtask #4:

score: 0
Skipped