Canadian Computing Olympiad: 2021 Day 1, Problem 2
Alice enjoys thinking about base-
~K~ numeral systems (don't we all?).
As you might know, in the standard base-~K~ numeral system, an integer 
~n~ can
be represented as 
~d_{m-1} d_{m-2} \cdots d_1 d_0~ where:
- Each digit
~d_i~ is in the set 
~\{0, 1, \dots, K-1\}~, and
~d_{m-1} K^{m-1} + d_{m-2} K^{m-2} + \cdots + d_1 K^1 + d_0 K^0 = n~.
For example, in standard base-3, you would write 
~15~ as 1 2 0, since
~(1) \cdot 3^2 + (2) \cdot 3^1 + (0) \cdot 3^0 = 15~.
But standard base-~K~ systems are too easy for Alice.
Instead, she's thinking about weird base-~K~ systems.
A weird-base-~K~ system is just like the standard base-~K~ system,
except that instead of using the digits 
~\{0, \dots, K-1\}~, you use
~\{a_1, a_2, \dots, a_D\}~ for some value 
~D~.
For example, in a weird-base-3 system with 
~a = \{-1, 0, 1\}~, you could write
~15~ as 1 -1 -1 0, since 
~(1) \cdot 3^3 + (-1) \cdot 3^2 + (-1) \cdot 3^1 + (0) \cdot 3^0 = 15~.
Alice is wondering how to write 
~Q~ integers, 
~n_1~ through 
~n_Q~, in a
weird-base-~K~ system that uses the digits 
~a_1~ through 
~a_D~.
Please help her out!
Input Specification
The first line contains four space-separated integers, ~K~, ~Q~, ~D~, and 
~M~
~(2 \le K \le 1\,000\,000, 1 \le Q \le 5, 1 \le D \le 5\,001, 1 \le M \le 2500)~.
The second line contains ~D~ distinct integers, ~a_1~ through ~a_D~ 
~(-M \le a_i \le M)~.
Finally, the 
~i~-th of the next ~Q~ lines contains 
~n_i~ 
~(-10^{18} \le n_i \le 10^{18})~.
For 8 of the 25 available marks, 
~M = K-1 \le 400, K = D \le 801~.
Output Specification
Output ~Q~ lines, the ~i~-th of which is a weird-base-~K~ representation of ~n_i~.
If multiple representations are possible, any will be accepted.
The digits of the representation should be separated by spaces.
Note that 0 must be represented by a non-empty set of digits.
If there is no possible representation, output IMPOSSIBLE.
Sample Input 1
3 3 3 1
-1 0 1
15
8
-5
Sample Output 1
1 -1 -1 0
1 0 -1
-1 1 1
Explanation for Sample Output 1
We have:
~(1) \cdot 3^3 + (-1) \cdot 3^2 + (-1) \cdot 3^1 + (0) \cdot 3^0 = 15~,
~(1) \cdot 3^2 + (0) \cdot 3^1 + (-1) \cdot 3^0 = 8~, and
~(-1) \cdot 3^2 + (1) \cdot 3^1 + (1) \cdot 3^0 = -5~.
Sample Input 2
10 1 3 2
0 2 -2
17
Sample Output 2
IMPOSSIBLE
Comments
Case 13 has TLE. but my local machine only runs under 0.12s.
The case you are failing is case 13 of batch 2, which should correspond to the 21st input/output, which times out given even 30 seconds on my laptop.