CCO '21 P2 - Weird Numeral System

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.5s
Memory limit: 1G

Author:
Problem type
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


  • 0
    huangbo309  commented on July 12, 2021, 1:59 p.m.

    Case 13 has TLE. but my local machine only runs under 0.12s.


    • 2
      Kirito  commented on July 12, 2021, 2:44 p.m.

      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.