We use a[n] to denote the number of empty cells for a square of size 2^n*2^n. The square of size 2^(n+1)*2^(n+1) can be built from the smaller one of size 2^n*2^n. Moreover, it can be observed that if we divide the larger square into four smaller ones, the left upper, left bottom and right bottom ones are just exactly the same copies of the smaller one, while the right upper one is fully filled. Thus, a[n+1]＝3*a[n]. Note that for the special case n=0, the answer should be 1.
At first, we find out all the independent sentences, and store them in the same order as they are given. Then, we keep merging the sentences into a message as long as its length does not exceed the requirement. Be careful that if two messages are combined together, the space between should also be counted, while if they belong to different messages, the space must be omitted.
We use rev[i] to denote the integer obtained by reversing i. Next, we use g[i] to denote the GCD of i and rev[i]. Note that i/rev[i] can be further reduced to (i/g[i])/(rev[i]/g[i]), and thus it can be observed that j must be a multiple of rev[i]/g[i].
With the above observations, we can directly enumerate x from 1 to maxx while y from 1 to maxy bit with j=j+rev[i]/g[i]. During this process, once we find that i*j=rev[i]*rev[j], we store j by using the segment tree. Then, we implement binary search to find out the smallest y so that the number of i*j=rev[i]*rev[j] is no less than w. Therefore, we can check the value of x*y and obtain the minimum answer.
Remember to calculate all g[i] and rev[i] previously; otherwise it might lead to TLE.
Comments (0)
