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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.

NOTE: The test data for this problem are stronger than the contest version. Solutions that AC there may not get AC here.


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



  • 0
    kevinlu1248  commented on Feb. 10, 2020, 3:59 p.m.

    Can someone help check my code? I ran it side by side with a brute force algorithm from 1 to 1e9 and there doesn't seem to be any bugs but I am still getting WA.