TSS Contest P5 - Blob Life

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

A blob of mass N has discovered it has the ability to separate itself into P parts an infinite number of times. However, the blob does not split into P equal parts, but rather every i^{th} part will contain p_i% of the blob's mass. Each split creates more blobs which also split, meaning the number of blobs multiplies every split. If the original blob of mass N splits into P parts M times, what is the mass of the k^{th} smallest blob?

Note that if the masses of the final blobs were {1, 1, 2, 3} the mass of the 2^{nd} smallest blob would be 1.

Input Specifications

The first and line of input contains four space separated integers N, M, P and k. The restrictions on these integers are as follows:

  • 1 \le N \le 10^9
  • 1 \le M \le 9
  • 2 \le P \le 5
  • k will not exceed the number of distinct blobs.

The second and last line of input will contain P integers, p_i. It is guaranteed the sum of all p_i will be 100.

Output Specifications

A single number representing the mass of the k^{th} smallest blob. This value may be a decimal.

Sample Input

100 2 2 1
40 60

Sample Output

16

Comments

There are no comments at the moment.