TLE '16 Contest 4 P6 - Essay Writing

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type
At this moment, you regret not dropping the course when you found out that Mr. B was your teacher.

Mr. B is an English teacher at Pierre Elliott Trudeau High School. He is infamous for his "questionable" teaching practices – particularly the way he marks. Sometimes, he marks assignments solely based on student favoritism. Other times, he gives his students' assignments to other teachers to mark. He might even randomly generate his students' marks!

For an upcoming essay about microwaves, which you have to finish over Christmas Holiday, your teacher Mr. B has decided to use an advanced method of marking. He will transform each essay into a hash value and determine its mark using the hash value.

Mr. B's hashing algorithm works as follows:

  • The hash value is a non-negative integer.
  • The hash value is initially 1.
  • For each lowercase English letter, multiply the hash value by a seed value, S, add the letter's value (\text{a} = 0, \text{b} = 1, \dots, \text{z} = 25) to the hash value, and mod the hash value by a mod value, M.

The final mark of the essay is the final hash value (the highest possible mark is M-1).

However, Mr. B has given you some constraints to the essay. The essay must contain exactly N space-separated strings, all unique, only composed using lowercase English letters.

Fortunately, a friend of yours has managed to find out the seed value, S, and the mod value, M, of Mr. B's hashing algorithm. All you have to do now is write the essay. Can you write an essay that will earn you a mark of K?

Constraints

0 \leq K < M

1 \le S \le M

S and M are coprime. That is, \gcd(S,M) = 1, where \gcd(x,y) denotes the greatest common divisor of x and y.

Subtask Points N S M
1 5 N = 1 S = 1 M = 1
2 5 N = 1 None M \leq 10^3
3 10 N \le 10^3 None M \leq 10^3
4 15 N = 1 S^2 \not\equiv 1 \pmod M M \le 10^5
5 20 N \le 10^3 S^2 \not\equiv 1 \pmod M M \le 10^6
6 20 N \le 10^5 For 1 \le k \le 100, S^k \not\equiv 1 \pmod M M \le 10^9
7 25 N \le 10^6 For 1 \le k \le 100, S^k \not\equiv 1 \pmod M M \le 10^9

Warning: If the size of your output is greater than 8 MB, you will receive an Output Limit Exceeded verdict.

Input Specification

The only line of input will contain four space-separated integers: N, K, S, and M.

Output Specification

Output, on a single line, an essay that will receive a mark of K. It is guaranteed that such an essay exists.

Sample Input

5 172 31 307

Sample Output

english is the worst subject

Explanation for Sample Output

The hash value initially starts at 1.

After processing the first letter, e, the hash value becomes 1 \times 31 + 4 \pmod{307} = 35.

After processing the second letter, n, the hash value becomes 35 \times 31 + 13 \pmod{307} = 177.

The final hash value, and thus the mark of the essay, is 172.


Comments


  • 1
    kobortor  commented on Dec. 24, 2016, 5:00 p.m.

    spaces don't count in the hashing algorithm right?


    • 1
      d  commented on Dec. 24, 2016, 5:00 p.m.

      Spaces are not put into the hash. However, spaces count towards the 8 MB limit.