Chef and a great voluntary Program
All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Chef likes to eat apples and bananas a lot. Today, he is doing a voluntary service by providing these fruits to needy people in a lunger (a gathering of needy people). The people form a queue to collect fruits from Chef. Chef distributes each person one of the fruits either an apple or a banana.
You are given information about the way Chef distributed fruits to the people by a string s, whose each character is either 'a' or 'b' denoting whether the corresponding person was distributed an apple or a banana.
After the event Chef wants to analyze what he could have done to make the event memorable. The event will be memorable if everyone at the end is happy. Whenever a person in the queue get an apple or a banana then he will observe the most recent K fruits distributed (including fruits he previously took, but not counting the fruit he just got) and if all of them were same as the fruit he just got, then he becomes disgruntled.
The value of K if the person is getting an apple is x, and similarly y for banana.
To make all the people happy, Chef can change the order of distributing the fruits (apple and bananas) and also can give some people extra kiwi fruits. Since the kiwis are costly, Chef would want to minimize the number of kiwis he needed to distribute. Note that a person leaves the queue as soon as Chef distributes him either an apple or a banana. So Chef should provide a person some kiwis before providing an apple or a banana, otherwise Chef won't be able to provide him kiwi as they would have already left the queue.
Help Chef in finding a way of distributing the fruits to the people that make everyone happy and requires Chef to buy as few kiwis as possible.
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains the string s.
The second line contains two space separated integers x, y.
For each test case, output a single string corresponding to the way in which the fruits should be distributed to the people. Apple fruit is denoted by 'a', banana by 'b', and kiwi by '*'. If there are more than one possible solutions, you can print any. Note that the number of apples in the output should be equal to the number of apples in the initial distributions of fruits denoted by string s. Same goes for bananas.
- 1 ≤ T ≤ 50
- 1 ≤ |s| ≤ 105
- 1 ≤ x, y ≤ |s|
- Subtask #1 (20 points): x = y = 1
- Subtask #2 (30 points): 1 ≤ |s| ≤ 103
- Subtask #3 (50 points): Original constraints
Input 6 ab 1 1 aab 1 1 aabb 1 2 aaaaab 2 1 aaaa 1 3 aaaaa 2 2 Output ab aba abba aa*abaa a*a*a*a aa*aa*a
Example 1. The way of distributing fruits already makes everyone happy.
Example 2. The second person will be disgruntled as he receives apple same as the person ahead of him. One possible way of having good impression is to distribute in the order aba.
Example 4. It's impossible for the Chef to make everyone happy without buying extra kiwi fruits. Chef will buy one extra kiwi fruit. Now, he distributes aa*abaa, i.e. apple to first and second, kiwi and apple to third, banana to fourth, and apples to fifth and sixth persons. This makes everyone happy. Notice that third person is happy because when he got an apple he checked the last 2 fruits taken which are the apple that the second person and the kiwi that he previously took, and they are not all apples so he is happy.
Example 6. at least two kiwis are needed here, if we gave the first one to third person and second one to fifth person then no one will be disgruntled, for example when the third person get an apple he will check the last two fruits distributed, they are one kiwi given to the same person previously and one apple given the second person so not all of them are apples, so it's fine with him.
|Tags||berezin, easy, greedy, oct17|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.