Arithmetic Progression in CS

Computer Science Level 5

In input (through file ), there is a positive integer $N$ . In the following $N$ rows, there will be two integers. In $i ^\text{th}$ row those will be $S_i$ and $D_i$ .

Each $S_i$ belongs to an arithmetic progression $AP_i$ .

Similarly, each $D_i$ represents the common difference of $AP_i$ .

Answer to the $i ^\text{th}$ row is a number $T_i$ . That number belongs to $AP_i$ and is the smallest positive integer of that progression.

Give your answer as $\displaystyle \sum _{ i = 1 }^{ N }{ T_i }$ .

Details and Assumptions :

$N = 5242880$ .
If $D_i = 0$ then $S_i > 0$ .
All the numbers (including the final answer) are smaller than $2^{60}$ .
The file is "AP1.txt" , textual file "Example.txt" is just an example provided.
For C/C++ solvers, my personal advice is to use fscanf() because it is significantly faster than the ifstream option.
Run time should be about 20 seconds

If something else is left unclear, feel free to ask it here .

The answer is 497210932587.

1 solution

Piotr Idzik
May 20, 2020

Here is my python solution. It turned out, that it is possible to find the values $T_i$ in a compact way.

"""
solution of:
    https://brilliant.org/problems/arithmetic-progression-in-cs-2/
"""

import time
def get_min_pos(in_s, in_d):
    """
    returns the smallest positive number, which is in
    an arithmetic sequence with the difference in_d containing in_s
    under the assumption that if in_d == 0, then in_s > 0
    """
    if in_d == 0:
        assert in_s > 0
        res = in_s
    else:
        res = in_s%in_d # be careful with writing this line in C/C++ (negative numbers)
        if res <= 0:
            res += abs(in_d)
    return res

def proc_single_line(in_line):
    """
    returns the solution for the input line
    """
    piece_list = in_line.split(' ')
    return get_min_pos(int(piece_list[0]), int(piece_list[1]))

assert get_min_pos(10, 7) == 3
assert get_min_pos(1033, 1) == 1
assert get_min_pos(256, 2) == 2
assert get_min_pos(101, 11) == 2
assert get_min_pos(314, 0) == 314
assert get_min_pos(-65, 40) == 15
assert get_min_pos(20, -3) == 2
assert get_min_pos(-11, -8) == 5

START_TIME = time.time()
RES_SUM = 0
with open('AP1.txt') as in_file:
    in_file.readline()
    RES_SUM = sum((proc_single_line(_) for _ in in_file))

print(f"result: {RES_SUM}")
END_TIME = time.time()
print(f"duration: {END_TIME-START_TIME} [S]")
assert RES_SUM == 497210932587

Arithmetic Progression in CS

If something else is left unclear, feel free to ask it here .

The answer is 497210932587.

1 solution

0 pending reports