SMTOILET - Smelly Toilets

no tags 

There are N toilets around Duck, each of them will begin to release Oi units of odors after i units of time. For example, there are three toilets producing 20, 10, 15 units of odors respectively. The first toilet will immediately release smells, the second one will release smells after 1 seconds and the third is after 2 seconds. So at the time 1, the total amount of released odors is 20 * 1 = 20, at time 2 is 20 * 2 + 10 * 1 = 50 and at time 3 is 20 * 3 + 10 * 2 + 15 * 1 =  95. Duck can only go to toilet when the absolute difference between the total amount of released odors at a certain time and his tolerance to odors M is minimized. Please find out at what time the difference is minimized. If there are two answers, choose the larger time.

After that, Duck will enter one of the toilets randomly. Given a string S, Duck knows which cubicles are available and which are occupied, 'x' means occupied and 'o' means available. Let the time that minimizes the difference be ANS, and the smallest power of 10 that equal or larger than ANS be P. Assuming the toilet entrance is located at the position floor(ANS / P * (len(S) - 1)) of S, that is, the cubicle at that position is replaced by the entrance. You are required to select the best cubicle for Duck: available, maximizes the total distance between the nearest occupied cubicle on the left and right side as possible and it should be in the middle between the left nearest and right nearest occupied cuicle as possible (if no occupied cubicles next to the chosen range, you may assume there is an occupied cubicle on the most left and most right side and the entrance is also an occupied cubicle), and then as close to the entrance as possible. If there is more than one best choice, select the one on the right side of the entrance because Duck is always right. Please help him, he wants to excrete comfortably.

Input

The first line is the number of test cases T. (1 <= T <= 50)

For each test case, it starts with two integers N (Number of toilets) and M (Duck's tolerance to odors). (1 <= N <= 500 / N <= M <= 1018)

The next line is a string S consisting of 'x' and 'o', representing the status of cubicles (3 <= len(S) <= 100)

Following N lines are the Oi units of odors released by i th toilet (1 <= Oi <= 105)

It is guaranteed that in S, 'o' will appear at least twice, so the answer always exists.

Output

Print two integers in format 'x y' without quotes, where x is the time minimizes the absolute difference between the total amount of released odors at a certain time and M, y is the position of best cubicle counting from 0

Example

Input:
2
2 4 78 ooxoxxoooxxxxxooooxoooo 2 13 1 5 5 35 xxoooxoooxx 1 2 3 4 5
5
Output: 5 15 5 7

Explanation

In case one, the time is 5 because 2 * 5 + 13 * 4 + 1 * 3 + 5 * 2 = 75 minimizes the difference between it and 78. The length of S is 23, so the entrance is at position floor(5 / 10 * 22) = 11, and S becomes 'ooxoxxoooxxExxooooxoooo', and we can see that the cubicle at position 15 is available, as far away from the nearest occupied cubicles as possible, and as close to the entrance as possible.

In case two, at time 5, the minimized difference is 0. So S becomes 'xxoooEoooxx'. There are two best cubicles: position 3 and 7, and we choose the right one, so the answer is 7.


hide comments
Vipul Srivastava: 2018-04-16 16:20:30

Last edit: 2018-04-16 19:56:48
[Rampage] Blue.Mary: 2018-04-13 06:43:54

Please change the statement "the distance between the nearest occupied cubicle on the left and right side as possible" to "the [total] distance between the nearest occupied cubicle on the left and right side as possible". This "distance" means sum, it's a bit unclear.

traxexeuler: 2018-04-12 07:43:39

Thank you for the reply! I was wondering what happened to my comment.

I think I understand how to compare the cubicle distances now. I get the same answers for all the examples you gave.

Just one more question. Is it possible that 'E' is in fact at the same place as an 'o', and in that case should we treat is as an 'x' for the distance calculations? Or are the test cases made so that 'E' will never be located at an 'o'?

I'm currently getting NZEC because a test case has exactly one 'o' and my code calculates that the entrance position is on top of that 'o', leaving no available cubicles. I'll continue debugging a bit later. If you can double check that test case, I'd appreciate it.

RE:
E can be located at any position, you can treat it as 'x', and 'o' will appear at least twice, so best selection always exists.
I think your solution is okay and it passes, just try to submit it again.

[traxexeuler]: It passed indeed. Thanks!

Last edit: 2018-04-12 09:29:36
him0727: 2018-04-12 06:49:26

Re traxexeuler:
I have no idea why your comment disappears, but I didn't hide it
The problem statement is updated, sorry for the unclear instruction
Select the larger time if both can minimize the difference between it and M
The time can be 0, as N <= M doesn't mean M >= O[0]
For the cubicle selection, as far away from the nearest cubicles as possible means the distance between your selection and two occupied cubicles (if any) on the left and right side is maximized. For example, ooxoxxxxooooxox, your selection will be in position [8, 11]. But which one to choose depends on the position of the entrance. If the entrance is at position 3, your answer will be 9, if the entrance is at 12, then you should choose 10. Remember that your selection should be as middle in your chosen range of available cubicles as possible, so the answer is either 9 or 10.
Yes, you can assume there is a cubicle on the most left and most right, so S becomes (x)ooxoxxxxooooxox(x), but these two cubicle won't affect the length of S and the position of each cubicle, so the first available cubicle is still at position 0. Therefore, the distance between the first available cubicle and the left and right nearest occupied cubicle are 0 and 1 respectively (for the left, it is just next to the occupied one, for the right, there is one available cubicle between them so the distance is 1). You can also assume the entrance is an occupied cubicle, for example, oooEooooooxo, your selection is at 6, not 3. Because if you choose 1, the distance will be 1 + 1 = 2, and if you choose 3, the distance is 2 + 3 = 5.

Last edit: 2018-04-12 09:27:13

Added by:him0727
Date:2018-04-11
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem