Chef And Salary Pay solution codechef

Chef And Salary Pay solution codechef

Given the schedule of Chef for 3030 days (A binary string of length 3030 where '0' denotes that Chef was on leave and '1' denotes Chef was working on that day). Chef gets XX− Rs for every day he worked. As working continuously for a long time is hectic so Company introduced the following policy to give a bonus to its employees.

Chef And Salary Pay solution codechef

The company will check the longest streak for which an employee has worked and will award YY− Rs for every day of that streak as a bonus. Calculate the salary received by Chef (including the bonus).

Note: Rs represents the currency of Chefland, and if there are two or more longest streaks of the same length, only one is counted for the bonus.

Input Format

Chef And Salary Pay solution codechef

  • The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
  • The first line of each test case contains XX and YY.
  • Second line contains a binary string (i.e it contains only ‘0’ / ‘1’), where '0' denotes that Chef was on leave and '1' denotes Chef was working on that day.

Output Format

Chef And Salary Pay solution codechef

  • For each testcase, output in a single line answer to the problem. i.e The salary received by Chef (including the bonus).

Constraints

  • 1T1041≤T≤104
  • 1X9991≤X≤999
  • 1Y9991≤Y≤999
  • |S|=30|S|=30

Sample Input 1

Chef And Salary Pay solution codechef

3
6 3
111100110101100000101100011111
8 2
111010111101001010100100111101
5 6
011101010100101000001101000010

Sample Output 1 

117
152
78

Explanation

Chef And Salary Pay solution codechef

Testcase 11: Chef’s actual pay comes out 176=10217⋅6=102− Rs and the length of longest continuous working streak comes out 55 (the last 55 working days), so bonus reward becomes 53=155⋅3=15− Rs. Hence Chef’s salary comes out to be 102+15=117102+15=117− Rs.

Testcase 22: Chef’s actual pay comes out 144144− Rs and the length of longest continuous working streak comes out 44 (here there are multiple occurrences of the longest working streak, so company selects any one of them), so bonus reward becomes 88− Rs. Hence Chef’s salary comes out to be 152152− Rs.

Leave a Comment