CCC '21 S5 - Math Homework

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem types
Canadian Computing Competition: 2021 Stage 1, Senior #5

Your math teacher has given you an assignment involving coming up with a sequence of N integers A_1, \dots, A_N, such that 1 \le A_i \le 1\,000\,000\,000 for each i.

The sequence A must also satisfy M requirements, with the i^\text{th} one stating that the GCD (Greatest Common Divisor) of the contiguous subsequence A_{X_i}, \dots, A_{Y_i} (1 \le X_i \le Y_i \le N) must be equal to Z_i. Note that the GCD of a sequence of integers is the largest integer d such that all the numbers in the sequence are divisible by d.

Find any valid sequence A consistent with all of these requirements, or determine that no such sequence exists.

Input Specification

The first line contains two space-separated integers, N and M. The next M lines each contain three space-separated integers, X_i, Y_i, and Z_i (1 \le i \le M).

The following table shows how the available 15 marks are distributed.

Subtask N M Z_i
3 marks 1 \le N \le 2\,000 1 \le M \le 2\,000 1 \le Z_i \le 2 for each i
4 marks 1 \le N \le 2\,000 1 \le M \le 2\,000 1 \le Z_i \le 16 for each i
8 marks 1 \le N \le 150\,000 1 \le M \le 150\,000 1 \le Z_i \le 16 for each i

Note: an additional test case worth 1 point was added to prevent unintended solutions from passing.

Output Specification

If no such sequence exists, output the string Impossible on one line. Otherwise, on one line, output N space-separated integers, forming the sequence A_1, \dots, A_N. If there are multiple possible valid sequences, any valid sequence will be accepted.

Sample Input 1

2 2
1 2 2
2 2 6

Output for Sample Input 1

4 6

Explanation of Output for Sample Input 1

If A_1 = 4 and A_2 = 6, the GCD of [A_1, A_2] is 2 and the GCD of [A_2] is 6, as required. Please note that other outputs would also be accepted.

Sample Input 2

2 2
1 2 2
2 2 5

Output for Sample Input 2

Impossible

Explanation of Output for Sample Input 2

There exists no sequence [A_1, A_2] such that the GCD of [A_1, A_2] is 2 and the GCD of [A_2] is 5.


Comments


  • 0
    maxcruickshanks  commented on Jan. 1, 2024, 7:16 p.m.

    Since the original data were weak, an additional test case worth 1 point was added.