Mock CCC '19 Contest 1 S4 - Pusheen Plays Neko Atsume

View as PDF

Submit solution

Points: 12
Time limit: 0.6s
Java 1.0s
Memory limit: 1G

Problem type

Pusheen is playing Neko Atsume! She has a lot of toys and has laid them out to maximize her fish income. She wants to know how efficient her layout will be though.

After doing a lot of critical thinking and real-time programming, Pusheen has boiled down the fish income in terms of a single variable - the beauty of the arrangement of toys. She thus defines f(x) to be the fish income given that her layout has beauty x. After some more computation, Pusheen has realized that for all x \le 0, f(x) = 1. Otherwise, f(x) = f\left(\left\lfloor \frac{x}{a} - b \right\rfloor \right) + f\left(\left\lfloor \frac{x}{c} - d \right\rfloor \right).

Pusheen has Q layouts, layout i having beauty x_i. Compute f(x_i) for many values of x_i.


1 \le x_i \le 10^9

2 \le a, c \le 10^9

0 \le b, d \le 10^9

1 \le Q \le 10^5

Input Specification

The first line contains five space-separated integers, a, b, c, d, and Q.

The next Q lines each contain a single positive integer, x_i.

Output Specification

Output Q lines, the f(x_i) values in order.

Sample Input

2 0 2 0 3

Sample Output



There are no comments at the moment.