Magical Cave And Horse
One day the little Bruce and his friends were playing in the garden.While playing Bruce fell into a well. After getting inside the well, Bruce was afraid so he started crying, but no one came.
After sometime, Bruce decided to get up and search for some way to get out of there. Bruce got a way which brought him out in woods,
There Bruce saw a cave which was magical. There are K (K>0) coins inside the cave at 0th day (day at which Bruce saw the cave). Now,everyday coins inside the cave gets doubled. If Bruce gets inside the cave then amount of coins which Bruce has increases by the amount of coins present inside the cave, but coins inside the cave don't decrease (magical nah!!!) and Bruce can't enter in cave more than once a day.See sample test case for explanation.
Now great things comes with great danger. So there is a horse near the cave which doesn't let anyone enter the cave. Alas! :-( But again, there are N bats which are ready to help Bruce (Batman).Bruce can only go inside the cave if and only if at that day any bat helps him by keeping the horse distracted. Every bat can help Bruce in a range of consecutive days (like a th day to b th day). But Bruce doesn't want to take help from more than M bats.
So Bruce wants to know what is the maximum amount of coins he can get from the cave (remember initially he has 0 coins) taking help from no more than M bats.
- First line contains T number of test cases.
- Then first line of each test case contains two integers N denoting total number of bats and M denoting maximum bats from which Bruce can take help.
- Next N line contains two integers a and b denoting the days for which i th bat can help.
- Next line contains binary representation of K denoting number of coins inside cave on 0th day.
- For each test case, output a single line containing binary representation of maximum amount of coins which Bruce can obtain from cave.
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 1000
- 1 ≤ M ≤ min(N,100)
- 0 ≤ a,b ≤ 100000 and a<=b
- 1 ≤ Length of binary representation of K ≤ 100000 and value of K >0
Subtask 1 : (10 points)
- 1 ≤ N ≤ 100
- 1 ≤ M ≤ 2
- 0 ≤ a,b ≤ 60
- 1 ≤ Length of binary representation of K ≤ 3
Subtask 2 : (20 points)
- 1 ≤ N ≤ 100
- 1 ≤ M ≤ N
- 0 ≤ a,b ≤ 50
- 1 ≤ Length of binary representation of K ≤ 10
Subtask 3 : (20 points)
- 1 ≤ Length of binary representation of K ≤ 60
Subtask 4 : (50 points)
- Original Constraint.
Example case 1.Here in order to get maximum amount of coins Bruce will choose 2nd and 3rd bats in order to get maximum possible coins.Here bats will help him from 2nd day to 4th day .Here on 0th day amount of coins present in cave is 6(110).Then-
Number of coins on 2nd day=24
Number of coins on 3rd day=48
Number of coins on 4th day=96
So here output will be 10101000 which is binary representation of 168,
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions